 # COCR107 - Editorial

Author: Nishit Sharma

Tester: Darshan Lokhande

Editorialist: Nishit Sharma

Medium.

### PREREQUISITES:

Segment tree,bitset

### PROBLEM:

Finding no of integers with odd frequency in a given range and updating values at given indices.

### OBSERVATION 1:

Tap to view

All values in the array are less than or equal to 2000.

### OBSERVATION 2:

Tap to view

We don’t need the exact count of how many times an element occurs. We only need to know the parity of the frequency of each element. This allows us to think on the lines of a boolean array that can be used to store the parity of all frequencies. But then we will have to traverse the boleen array for each query this gives us a time complexity of O(Q*2000) for answering the queries. Solution with this complexity is not intended to pass. We can get better performance if we use bitsets instead of a boolean array. Bitsets are faster and will occupy less space. Bitsets support bit operations as well , this will help us later on in building our solution.

### EXPLANATION:

Tap to view

We can build a segment tree to answer the queries and perform update operations in O(log(N)) time. Each node of the segment tree will store a bitset . Let any Node K of the segement tree represent range [L,R] then the bitset of this node will have set bits only at positions of the elements which occur odd number of times. For eg if 3,8,11 occur odd number of times then the 3rd,8th and 11th bits will be set in the bitset. With a bit more observation we can see that to combine two ranges into one i.e to combine ranges like [L,X]+[X+1,R] into [L,R] we use can use the XOR operation. While combining two ranges to get the answer for a bigger range we can see that any element can occur odd number of times in the bigger range if and only if the element occurs odd no of times in exactly one of the two smaller ranges. For eg. to combine [L,X]+[X+1,R] into [L,R] only the elements which occur odd number of times in exactly one of the two smaller ranges will also occur odd number of times in the range [L,R].

For queries of type 0 we need can just update the segment tree twice at index L and index R. This will take O(2*log(N)) time.

We can break the queries of type 1 into 2 parts:

1. L<=R: This is simple we will query the segment tree for the range [L,R] and output the number of set bits in bitset.
2. R<L: This query can be broken down into two parts first we query the segment tree for [L,N-1] and then query for [0,R]. We then combine the two queries just like we combined two ranges in the segment tree using the XOR operation and finally output the no of set bits in the bitset.

#### Bonus:

Queries where R<L can also be answered in just 1 query to the segment tree.

#### CODE:

Setter's Solution
``````#pragma GCC optimize "trapv"
#include<bits/stdc++.h>
#define ll long long int
#define fab(a,b,i) for(int i=a;i<b;i++)
#define pb push_back
#define db double
#define mp make_pair
#define endl "\n"
#define f first
#define se second
#define all(x) x.begin(),x.end()
#define MOD 1000000007
#define quick ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
int a;
bitset<2005> seg[4*200005];
void build(int node,int s,int e)
{
if(s==e)
{
seg[node].set(a[s]);
}
else
{
int mid=s+(e-s)/2;
build(2*node,s,mid);
build(2*node+1,mid+1,e);
seg[node]=seg[2*node]^seg[2*node+1];
}

}
bitset<2005> query(int node,int s,int e ,int l, int r)
{
if(s>r or e<l)
return bitset<2005>(0);
if(l<=s and e<=r)
return seg[node];

int mid=s+(e-s)/2;

return (query(2*node,s,mid,l,r)^query(2*node+1,mid+1,e,l,r));

}
void update(int node,int s,int e,int ind,int val)
{
if(s==e)
{
a[s]=val;
seg[node].reset();
seg[node].set(val);
}
else
{
int mid=s+(e-s)/2;
if(ind<=mid)
update(2*node,s,mid,ind,val);
else
update(2*node+1,mid+1,e,ind,val);
seg[node]=seg[2*node]^seg[2*node+1];
}
}

int main()
{ quick;

int t;
cin>>t;

while(t--)
{
int n;
cin>>n;

fab(0,n,i)
{
cin>>a[i];
}

build(1,0,n-1);
int q;
cin>>q;

fab(0,q,i)
{
int x,y,tp;
cin>>tp>>x>>y;

if(tp==0)
{
int val1=a[x];
int val2=a[y];
update(1,0,n-1,x,val2);
update(1,0,n-1,y,val1);

}
else
{
if(y>=x)
{
cout<<query(1,0,n-1,x,y).count()<<endl;
}

else
{
bitset<2005> ans=query(1,0,n-1,x,n-1)^query(1,0,n-1,0,y);
cout<<ans.count()<<endl;
}
}

}

fab(0,4*n+1,i)
seg[i].reset();

}
cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;

return 0;
}

``````
Tester's Solution
``````#include<bits/stdc++.h>
#define boost ios::sync_with_stdio(false); cin.tie(0)
#define ll              long long int
#define ld              long double
#define mk              make_pair
#define pb              push_back
#define f               first
#define s               second
#define fo(i,a,b)       for(i=a;i<b;i++)
#define foe(i,a,b)      for(i=a;i<=b;i++)
#define all(x)          x.begin(),x.end()
#define vi               vector<int>
#define vl              vector <long long int>
#define pii          pair <int,int>
#define pll             pair <long long int, long long int>
#define vpii         vector< pair<int,int> >
#define vpll            vector < pair <long long int,long long int> >
#define MOD             1000000007
using namespace std;
const int inf = INT_MAX;
const ll inf64 = LLONG_MAX;

ll arr;
vector <bitset<2005>> st(400005);

int getMid(int s, int e) {  return s + (e - s) / 2;  }

void updateValue(int curr , int ss, int se, int ind , int val)
{
if (ss == se) {
arr[ss] = val;
st[curr].reset();
st[curr].set(val);
}
else {
int mid = getMid(ss, se);
if (ind <= mid)
updateValue(2 * curr + 1, ss, mid, ind, val);
else
updateValue(2 * curr + 2, mid + 1, se, ind, val);
st[curr] = st[2 * curr + 1 ] ^ st[2 * curr + 2];
}
}

bitset<2005> getXorUtil( int ss, int se, int qs, int qe, int si)
{
if (qs <= ss && qe >= se) return st[si];
if (se < qs || ss > qe) return bitset<2005>(0);

int mid = getMid(ss, se);
return getXorUtil( ss, mid, qs, qe, 2 * si + 1) ^ getXorUtil( mid + 1, se, qs, qe, 2 * si + 2);
}

bitset<2005> getXor( int n, int qs, int qe)
{
if (qs < 0 || qe > n - 1 || qs > qe) {
printf("Invalid Input");
return -1;
}

return getXorUtil( 0, n - 1, qs, qe, 0);
}

bitset<2005> build(int ss, int se, int si)
{
if (ss == se) {
st[si].set(arr[ss]);
return st[si];
}
int mid = getMid(ss, se);
st[si] =  build(ss, mid, si * 2 + 1) ^  build(mid + 1, se, si * 2 + 2);
return st[si];
}

void clearst() {
ll i;
fo(i, 0, st.size())st[i].reset();
}

int main()
{
boost;
ll t;
cin >> t;
while (t--)
{
ll n, q, i;
cin >> n;
bitset<2005> all;
fo(i, 0, n) {
bitset<2005> temp;
cin >> arr[i];
temp.set(arr[i]);
all ^= temp;
}
ll all_cnt = all.count();
build(0, n - 1, 0);
cin >> q;
while (q--) {
ll x, l, r;
cin >> x >> l >> r;
if (x == 0) {
ll lval = arr[l], rval = arr[r];
updateValue(0, 0, n - 1, l, rval);
updateValue(0, 0, n - 1, r, lval);
}
else {
ll ans;
if (l <= r) {
if (l == 0 and r == n - 1)ans = all_cnt;
else ans = getXor(n, l, r).count();
}
else {
// ans = (getXor(n, l, n - 1) ^ getXor(n, 0, r)).count();
if (r == l - 1)ans = all_cnt;
else ans = (getXor(n, r + 1 , l - 1)^all).count();
}
cout << ans << '\n';
}
}
clearst();
}
return 0;
}
``````

If anything is unclear please let me know in the comments, it will help me improve.

6 Likes

Hey great editorial!
I get your point that Q*2000, is not intended to pass, but instead of getting TLE, I received WA on my implementation .
Here is my approach
We have an array of ordered sets of size 2000, where ith set contains indices of all occurences of i in our given array.
Now for query type 1 (swap)
I have to erase and insert in ordered sets a[l], a[r]
For query 2, count of odds
I run through all sets 0-2000 and using policy based data structures, I count for elements in the range l,r and hence report the answer .
Also: for l>r in second query , I have subtracted (r+1,l-1) from total

Here is my Implementation
Can you tell me some testcase where my logic is failing .
Thanks

Hi I found a testcase where your code fails.
1
15
2 4 7 0 6 0 2 0 7 3 0 7 1 0 7
3
0 10 3
0 10 0
1 12 3
Your output is 2 whereas the correct output is 3.

1 Like

Thanks a lot !
I got my error in implementation. When a[l]=a[r] in swap query, i need to delete first and then insert. Now I got TLE(as expected) .