# VIDYA-EDITORIAL

Author: valiant_vidit
Editorialist: valiant_vidit
Tester: dragno99

# PROBLEM:

Given an array of length N consisting of various not necessarily distinct numbers , and Q different queries .

An operation on array is defined as follows:

You can choose any index i (L≤i≤R), where L and R are defined according to query(definition given below) and change a_i=c, where c (1≤c≤10^{18}) is any number of your choice in the given range.

A query is defined as L R k

After calculating frequencies of every distinct a_i (L≤i≤R) . Let the no. of elements with odd frequencies be x and no. of elements with even frequencies be y.

You have to find how many minimum operations you can perform to convert the value of x equal to k or determine it is not possible.

# PREREQUISITES:

• Mo’s Algorithm
• Number Theory
• Little amount of Brain

EASY-MEDIUM

# EXPLANATION:

The basic idea is to solve this problem for a single query and then process all offline queries from left to right using Mo’s algo as the overall complexity will be T*Q*sqrt(N)*f(x). Here the computation of f(x) is in constant time, so
10*10^4*sqrt(10^5)*f(x)\approx 5*10^7, which can easily run in 2 seconds.

The various conditions to keep in mid for reaching the soln are as follows:

1. The ans is possible only if k<=r-l+1.

2. We can easily proof by mathematical induction that ans is ONLY possible if k and (r-l+1) have same parity.

3. Then we have to make sure of 4 types of values before processing a single query (for better understanding of solution. ) :

• a1 (count of numbers having odd frequencies with length =1),
• am (count of numbers having odd frequencies with length >1),
• b2 (count of numbers having even frequencies with length =2),
• bm (count of numbers having even frequencies with length >2).

Here we can see that a1+am=x and b2+bm=y.

4. if (k<x) then the soln. will be (a1+am-k)/2 because here after performing 1 single operation we can dec the value of x by 2.

5. if (k>=x) then there will be 2 cases :-

• Case 1: if (x+2*(y)>=k) then the ans will be (k-(a1+am))/2 .

As here we can see that after changing a single value from the numbers with even frequencies we can increase the value of x by 2, so if we perform all operation such that the desired value of x is achieved and still there is >=0 value left of y, then we will reach the ans as shown.

• Case 2: In this case, our ans will be k-(x+y).

As here if value of y is less to achieve our desired k ,then first of all we will make y=0 by maximizing our answer at that point so till now, our ans=y,
and xx+2*y; ( a1a1+2*b2+bm), (amam+bm).

Now let’s understand how the next few operations work:

Now we have updated values of a1,am, and b2=0, and bm=0;
now if we change a value from a1 ( i.e. change a number whose freq is 1 then it will not be an optimal strategy as after this operation our x will decrease by 0 or 1 and our operation will be wasted) , so we will change a value from am ( i.e. we will change a number whose frequency is odd of length >1).

After this operation a1a1+1, and amam-1, bm/b2bm/b2+1. then in next operation we will dec the value of bm ( i.e. we will change a number whose frequency is even of length >2) then after this our a1a1+1, amam+1 .

We can see that hereafter performing 2 operations, a1a1+1 from the initial value and amam+1 from initial value… so to summarize this here we can see that 2 operations are changing the value of xx+2…( this also supports our proof in point 2. so in total if we see. ansans+(k-x-2*y) (where x and y have value as before Case 2 occurs) .
ans= y+k-x-2*y=k-x-y=k-(x+y).

So, from Case 2 our final answer will be k-(x+y).

And here, my Explanation ends. Hope you have understood my logic and do tell me whether you liked it or not

# SOLUTION:

Setter's Solution in C++
``````#include "bits/stdc++.h"
#define ll long long int
#define forr(i,n) for(int i=0;i<n;i++)
#define bhaago ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(x) x.begin(),x.end()
#define unique(v) sort(all(v)); v.resize(distance(v.begin(),unique(all(v))))
#define eb emplace_back

using namespace std;

const ll blk=550;

struct node{
ll l,r,ind,k;
friend bool operator < (const node &a,const node &b){
if(a.l/blk != b.l/blk) return a.l/blk < b.l/blk;
return a.r < b.r;
}
};

ll m[200005];
ll odd1,oddg1,even2,eveng2,cnt;

if(m[x]==0) odd1++;
else if(m[x]==1) odd1--,even2++;
else if(m[x]==2) even2--,oddg1++;
else if(m[x]&1) oddg1--,eveng2++;
else eveng2--,oddg1++;
m[x]++;
if(m[x]&1) cnt++;
else cnt--;
}
void remove(const ll x){
if(m[x]==1) odd1--;
else if(m[x]==2) even2--,odd1++;
else if(m[x]==3) oddg1--,even2++;
else if(m[x]&1) oddg1--,eveng2++;
else eveng2--,oddg1++;
m[x]--;
if(m[x]&1) cnt++;
else cnt--;
}

ll get(const ll k,const ll len){
if((abs(cnt-k)&1) || k>len) return -1;
if(k == cnt) return 0;
else if( k < cnt ) return (cnt-k)/2;
else{
int delta = k - cnt;
if( delta<=2*(even2 + eveng2)) return delta/2;
else return delta - eveng2 - even2;
}
return 0;
}

void __sol(){
ll n,q; cin >> n >> q;
ll a[n];
vector<ll> temp;
forr(i,n) cin >> a[i], temp.eb(a[i]);
unique(temp);
forr(i,temp.size()) m[i] = 0;
forr(i,n) a[i] = lower_bound(all(temp),a[i]) - temp.begin();
node qry[q];
forr(i,q){
cin >> qry[i].l >> qry[i].r >> qry[i].k;
qry[i].l-- , qry[i].r--;
qry[i].ind = i;
}
sort(qry,qry+q);
ll lp=0,rp=-1;
cnt = odd1 = oddg1 = even2 = eveng2 = 0;
ll ans[q];
forr(i,q){
ll l = qry[i].l;
ll r = qry[i].r;
while(lp<l)  remove(a[lp]),lp++;
while(rp>r) remove(a[rp]),rp--;
ans[qry[i].ind] = get(qry[i].k,r-l+1);
}
forr(i,q) cout << ans[i] << endl;
return;
}

int main(){

bhaago;
ll tc=1; cin >> tc;
while(tc--) __sol();
return 0;
}
``````
Testers's Solution in Java
``````import java.util.*;

public class Main {
static int blk = 550;
static int[] m = new int[200005];
static int odd1, oddg1, even2, eveng2, cnt;

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int cases = sc.nextInt();
while (cases-- > 0) {
int n = sc.nextInt();
int q = sc.nextInt();
int[] a = new int[n];
ArrayList<Integer> temp = new ArrayList<>();

for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
Set<Integer> set = new HashSet<>(temp);
temp.clear();
Collections.sort(temp);
for (int i = 0; i < temp.size(); i++)
m[i] = 0;
for (int i = 0; i < n; i++)
a[i] = Collections.binarySearch(temp, a[i]);

Node qry[] = new Node[q];
for (int i = 0; i < q; i++) {
qry[i] = new Node();
qry[i].l = sc.nextInt();
qry[i].r = sc.nextInt();
qry[i].k = sc.nextInt();
qry[i].l--;
qry[i].r--;
qry[i].ind = i;
}
Arrays.sort(qry, new Comparator<Node>() {
public int compare(Node a, Node b) {
if (a.l / blk != b.l / blk)
return (int)(b.l / blk - a.l / blk);
return (int)(b.r - a.r);
}
});
int lp = 0;
int rp = -1;
cnt = odd1 = oddg1 = even2 = eveng2 = 0;
int[] ans = new int[q];
for (int i = 0; i < q; i++) {
int l = qry[i].l;
int r = qry[i].r;
while (lp < l) {
remove(a[lp]);
lp++;
}
while (l < lp) {
lp--;
}
while (rp < r) {
rp++;
}
while (rp > r) {
remove(a[rp]);
rp--;
}
ans[qry[i].ind] = get(qry[i].k, r - l + 1);
}
for (int i = 0; i < q; i++)
System.out.println(ans[i]);
}
}

public static void add(int x) {
if(m[x]<0){
m[x]++;
return;
}
if (m[x] == 0)
odd1++;
else if (m[x] == 1) {
odd1--;
even2++;
} else if (m[x] == 2) {
even2--;
oddg1++;
} else if (m[x] % 2 == 1) {
oddg1--;
eveng2++;
} else {
eveng2--;
oddg1++;
}
m[x]++;
if (m[x] % 2 == 1)
cnt++;
else
cnt--;
}

static void remove(int x) {
if(m[x]<=0){
m[x]--;
return;
}
if (m[x] == 1)
odd1--;
else if (m[x] == 2) {
even2--;
odd1++;
} else if (m[x] == 3) {
oddg1--;
even2++;
} else if (m[x] % 2 == 1) {
oddg1--;
eveng2++;
} else {
eveng2--;
oddg1++;
}
m[x]--;
if (m[x] % 2 == 1)
cnt++;
else
cnt--;
}

static int get(int k,int len) {
if ((Math.abs(cnt - k) & 1) != 0 || k > len)
return -1;
if (k == cnt)
return 0;
else if (k < cnt)
return (cnt - k) / 2;
else {
int delta = k - cnt;
if (delta <= 2 * (even2 + eveng2))
return delta / 2;
else
return delta - eveng2 - even2;
}
}
}

class Node {
int blk = 550;
int l, r, k;
int ind;
}
``````
7 Likes