PROBLEM LINK: LINK
Author: Nishit Sharma
Tester: Darshan Lokhande
Editorialist: Nishit Sharma
DIFFICULTY:
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:
- 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.
- 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.
Overall Time Complexity:O((N+Q)log(N))
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[100005];
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[100005];
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.