PROBLEM LINK:
Practice Link
Vidit and Simple Queries
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
DIFFICULTY:
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:
-
The ans is possible only if k<=r-l+1.
-
We can easily proof by mathematical induction that ans is ONLY possible if k and (r-l+1) have same parity.
-
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.
-
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.
-
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 x → x+2*y; ( a1 → a1+2*b2+bm), (am → am+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 a1 → a1+1, and am → am-1, bm/b2 → bm/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 a1 → a1+1, am → am+1 .
We can see that hereafter performing 2 operations, a1 → a1+1 from the initial value and am → am+1 from initial value… so to summarize this here we can see that 2 operations are changing the value of x → x+2…( this also supports our proof in point 2. so in total if we see. ans → ans+(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;
void add(const ll x){
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(l<lp) add(a[lp-1]),lp--;
while(rp<r) rp++,add(a[rp]);
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();
temp.add(a[i]);
}
Set<Integer> set = new HashSet<>(temp);
temp.clear();
temp.addAll(set);
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) {
add(a[lp - 1]);
lp--;
}
while (rp < r) {
rp++;
add(a[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;
}