PROBLEM LINK:
Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest
Setter: Ashish Vishal
Tester: Jatin Yadav, Aditya Kumar Singh
DIFFICULTY:
MEDIUM
PREREQUISITES:
Data Structure, Bitsmask
PROBLEM:
Given an array of integers, you have to perform 3 types of query on the array:-
Type 1:- 1 X:- If the integer of the array at index X is even, then move the
Array element to the beginning, otherwise move it to the end of the array.
Type 2:- 2 X P:- Update the array element at position X to P.
Type 3:- 3 L R K:- Find the count of numbers of the array from index L to R
(including both L and R) having K set bits.
QUICK EXPLANATION:
The important process that is required here is to move elements of the array to begin and the end of the array and then shift some of the elements of the array. According to the given constraints, We can’t shift because of high time complexity. This process can be optimized
by using the Fenwick tree of size [2][N+2Q+1] (i.e int BIT[2][N+2Q+1] ). We have taken an extra 2Q size for the optimization process.
Fill the first BIT with array element(A) starting from position Q+1, to Q+N ( that is BIT[0]
[Q+i]=A[i], for 1<=i<=N, assume 1-based indexing.
Fill the second BIT with 1 from index Q+1 to Q+N, denoting that the element is present in the array at that position. (BIT[1][Q+i]=1, for 1<=i<=N, assume 1-based indexing.
Maintain two pointers p1,p2. where p1=Q, p2=Q+N+1. P1 and P2 will be used later for moving elements to the beginning and the end of the array.
Now, if element at index X is moved to beginning:-
- Find the minimum position(P) in the second BIT such that the sum of elements from 1 to that position P is X.
- Update the second BIT at position P with 0. and at position p1 with 1.
- Update first BIT at position P1 with Pth element of first BIT(i.e BIT[0][P]), and again update first BIT position P with 0.
- Decrease p1 by 1(p1=p1-1).
Similarly, if element at index X is moved to the end then:
- Find the minimum position P in the second BIT such that the sum of element from 1 to that position(P) is X.
- Update the second BIT at position P with 0. and at position p2 with 1.
- Update first BIT at position P2 with Pth element of first BIT(i.e BIT[0][P]), and again update first BIT position P with 0.
- Increase p2 by 1(p2=p2+1).
With this, we can find any kth element of the array just by finding
the minimum position P in the second BIT such that the sum of element from 1 to that position P is k. and, the corresponding position P in the first BIT gives the kth array element.
This process makes us able to perform the 1st and 2nd query in logarithmic time.
For the 3rd query, we need to make another 33 binary index trees array(i.e TREE[33][N+2*Q])
as the total number of set bits according to the problem will be from (0-32). Then, we will perform a similar operation and store these 33 arrays with 1 or 0. A value of 1 in the ith binary indexed tree at jth position denotes that an element exists which have (i) set bits and it is present at the jth position in that first BIT. The value of these 33 arrays will change according to the
1st and 2nd queries.
For queries of L to R, find the equivalent position of L and R according to the second BIT by
finding the minimum position(L’ and R’) in the second BIT such that the sum of element from
1 to that position (L’ and R’) is L and R respectively. Then, perform the sum query for the kth
binary index trees array from position L’ to R’ (which can be performed in logarithmic time).
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fr(n) for(long long i=0;i<n;i++)
#define rep(i,a,b) for(long long i=a;i<b;i++)
#define ALL(x) (x).begin(), (x).end()
typedef long long int ll;
typedef vector<ll> vi;
const ll N=34,ii=33;
ll n,q,siz,t,x,p,l,r,k,sp,ep;
vi arr,tree[N];
void update(ll id,ll ind,ll val)
{
for(ind;ind<siz;ind+=(ind&-ind))
tree[id][ind]+=val;
}
ll query(ll id,ll ind)
{
ll sum=0;
while(ind>0)
{
sum+=tree[id][ind];
ind-=(ind&-ind);
}
return sum;
}
ll find_ind(ll id,ll x)
{
ll sum=0,si=0;
for(int i=22;i>=0;i--)
{
ll ind=si+(1<<i);
if(ind<siz)
{
if((sum+tree[id][ind])<x)
{
si=ind;
sum+=tree[id][ind];
}
}
}
return si+1;
}
ll count_bit(ll k)
{
ll cnt=0;
rep(i,0,32)
if(k&(1<<i))
cnt++;
return cnt;
}
void solve()
{
cin>>n>>q;
siz=n+2*q+1;
sp=q,ep=q+n+1;
arr.clear();
rep(i,0,N)tree[i].clear();
rep(i,0,N)tree[i].resize(siz,0);
arr.resize(siz);
rep(i,1,n+1)
{
cin>>arr[q+i];
ll sb=count_bit(arr[q+i]);
update(ii,q+i,1);
update(sb,q+i,1);
}
fr(q)
{
cin>>t;
if(t==1)
{
cin>>x;
ll ind=find_ind(ii,x);
ll sb=count_bit(arr[ind]);
update(ii,ind,-1);
update(sb,ind,-1);
if(arr[ind]%2==0)
{
update(ii,sp,1);
update(sb,sp,1);
arr[sp]=arr[ind];
sp--;
}
else
{
update(ii,ep,1);
update(sb,ep,1);
arr[ep]=arr[ind];
ep++;
}
arr[ind]=0;
}
else if(t==2)
{
cin>>x>>p;
ll ind=find_ind(ii,x);
ll sb=count_bit(arr[ind]);
update(sb,ind,-1);
arr[ind]=p;
sb=count_bit(arr[ind]);
update(sb,ind,1);
}
else if(t==3)
{
cin>>l>>r>>k;
l=find_ind(ii,l-1);
r=find_ind(ii,r);
cout<<query(k,r)-query(k,l)<<endl;
}
}
}
int32_t main()
{
fast;
ll t=1;
cin>>t;
while(t--)
solve();
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#endif
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l<=x && x<=r))cerr<<l<<"<="<<x<<"<="<<r<<endl;
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd, char minc = 'a', char maxc = 'z'){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
assert(g >= minc && g <= maxc);
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r, char minc = 'a', char maxc = 'z'){
return readString(l,r,'\n', minc, maxc);
}
string readStringSp(int l,int r, char minc = 'a', char maxc = 'z'){
return readString(l,r,' ', minc, maxc);
}
template<class T>
vector<T> readVector(int n, long long l, long long r){
vector<T> ret(n);
for(int i = 0; i < n; i++){
ret[i] = i == n - 1 ? readIntLn(l, r) : readIntSp(l, r);
}
return ret;
}
template<class T>
struct BIT{
int n;
vector<T> F;
BIT(){}
BIT(int n) : n(n), F(n + 1){};
void add(int i, T w){
i++;
for(; i <= n; i += (i & (-i))) F[i] += w;
}
T get(int i){
i++;
T ret = 0;
for(; i; i -=(i & (-i))) ret += F[i];
return ret;
}
T get(int i, int j){ return get(j) - get(i - 1);}
int getKth(T k){
int lo = 0, hi = n - 1;
while(lo < hi){
int mid = (lo + hi) >> 1;
if(get(mid) >= k) hi = mid;
else lo = mid + 1;
}
return lo;
}
};
const int INF = 1000'000'000;
int main(){
BIT<int> bit(5);
bit.add(2, 1);
int t = readIntLn(1, 5);
while(t--){
int n = readIntSp(1, 100000), q = readIntLn(1, 100000);
vector<int> A = readVector<int>(n, 0, INF);
vector<BIT<int>> fenw(33, BIT<int>(n + 2 * q));
BIT<int> active(n + 2 * q);
int L = q, R = q + n - 1;
vector<int> B(n + 2 * q);
for(int i = L; i <= R; i++){
active.add(i, 1);
fenw[__builtin_popcount(B[i] = A[i - L])].add(i, 1);
}
int _q = q;
while(q--){
int type = readIntSp(1, 3);
if(type == 1){
int X = readIntLn(1, n);
int pos = active.getKth(X);
active.add(pos, -1);
int k = __builtin_popcount(B[pos]);
fenw[k].add(pos, -1);
if(B[pos] & 1){
++R;
B[R] = B[pos];
active.add(R, 1);
fenw[k].add(R, 1);
} else{
--L;
B[L] = B[pos];
active.add(L, 1);
fenw[k].add(L, 1);
}
} else if(type == 2){
int X = readIntSp(1, n), P = readIntLn(0, INF);
int pos = active.getKth(X);
fenw[__builtin_popcount(B[pos])].add(pos, -1);
fenw[__builtin_popcount(B[pos] = P)].add(pos, 1);
} else{
int L = readIntSp(1, n), R = readIntSp(L, n), k = readIntLn(0, 32);
int posL = active.getKth(L), posR = active.getKth(R);
cout << fenw[k].get(posL, posR) << "\n";
}
}
}
}
