Phoenix and Bits solution codeforces – Phoenix loves playing with bits , 2021

Phoenix and Bits solution codeforces

Phoenix and Bits solution codeforces Phoenix and Bits solution codeforces Phoenix and Bits solution codeforces

Phoenix loves playing with bits — specifically, by using the bitwise operations ANDOR, and XOR. He has nn integers a1,a2,,ana1,a2,…,an, and will perform qq of the following queries:

  1. replace all numbers aiai where lairl≤ai≤r with aiai AND xx;
  2. replace all numbers aiai where lairl≤ai≤r with aiai OR xx;
  3. replace all numbers aiai where lairl≤ai≤r with aiai XOR xx;
  4. output how many distinct integers aiai where lairl≤ai≤r.

For each query, Phoenix is given llrr, and xx. Note that he is considering the values of the numbers, not their indices.

Input Phoenix and Bits solution codeforces

The first line contains two integers nn and qq (1n21051≤n≤2⋅1051q1051≤q≤105) — the number of integers and the number of queries, respectively.

The second line contains nn integers a1,a2,,ana1,a2,…,an (0ai<2200≤ai<220) — the integers that Phoenix starts with.

The next qq lines contain the queries. For each query, the first integer of each line is tt (1t41≤t≤4) — the type of query.

If t{1,2,3}t∈{1,2,3}, then three integers liliriri, and xixi will follow (0li,ri,xi<2200≤li,ri,xi<220lirili≤ri).

Otherwise, if t=4t=4, two integers lili and riri will follow (0liri<2200≤li≤ri<220).

It is guaranteed that there is at least one query where t=4t=4.

Output Phoenix and Bits solution codeforces

Print the answer for each query where t=4t=4.

Examples Phoenix and Bits solution codeforces

input Phoenix and Bits solution codeforces

Copy
5 6
5 4 3 2 1
1 2 3 2
4 2 5
3 2 5 3
4 1 6
2 1 1 8
4 8 10

output

Copy
3
2
1

input

Copy
6 7
6 0 2 3 2 7
1 0 4 3
2 6 8 4
4 0 7
3 2 5 3
1 0 1 2
4 0 3
4 2 7

output

Copy
5
1
2
Note

In the first example:

  • For the first query, 22 is replaced by 22 AND 2=22=2 and 33 is replaced with 33 AND 2=22=2. The set of numbers is {1,2,4,5}{1,2,4,5}.
  • For the second query, there are 33 distinct numbers between 22 and 552244, and 55.
  • For the third query, 22 is replaced by 22 XOR 3=13=144 is replaced by 44 XOR 3=73=7, and 55 is replaced by 55 XOR 3=63=6. The set of numbers is {1,6,7}{1,6,7}.
  • For the fourth query, there are 22 distinct numbers between 11 and 6611 and 66.
  • For the fifth query, 11 is replaced by 11 OR 8=98=9. The set of numbers is {6,7,9}{6,7,9}.
  • For the sixth query, there is one distinct number between 88 and 101099.

C++ (solution 1)

#include<bits/stdc++.h>
using namespace std;
const int N=200005,f=(1<<20)-1;
int n,q,u,m,lc[N<<6],rc[N<<6],tr[N<<6],t0[N<<6],t1[N<<6],t[N<<6];
void pt(int u,int p,int x)
{
if(!u)
return;
if(x>>(p-1)&1)
swap(lc[u],rc[u]);
int v0=(t0[u]&(~x))|(t1[u]&x),v1=(t1[u]&(~x))|(t0[u]&x);
t0[u]=v0,t1[u]=v1,t[u]^=x;
}
void pd(int u,int p)
{
if(t[u])
{
pt(lc[u],p-1,t[u]);
pt(rc[u],p-1,t[u]);
t[u]=0;
}
}
void pu(int u)
{
tr[u]=tr[lc[u]]+tr[rc[u]];
t0[u]=t0[lc[u]]|t0[rc[u]];
t1[u]=t1[lc[u]]|t1[rc[u]];
}
int ins(int u,int p,int x)
{
if(!u)
u=++m;
if(!p)
{
tr[u]=1;
t0[u]=(x^f);
t1[u]=x; 
return u;
}
if(!(x>>(p-1)&1))
lc[u]=ins(lc[u],p-1,x);
else
rc[u]=ins(rc[u],p-1,x);
pu(u);
return u;
}
void split(int &u,int &v,int p,int l,int r,int a,int b)
{
if(b<=l||r<=a||!u)
{
v=0;
return;
}
if(a<=l&&r<=b)
{
v=u;
u=0;
return;
}
pd(u,p);
v=++m;
int mid=l+r>>1;
split(lc[u],lc[v],p-1,l,mid,a,b),split(rc[u],rc[v],p-1,mid,r,a,b);
pu(u),pu(v);
}
void mg(int &u,int &v,int p)
{
if(!u)
{
u=v;
return;
}
if(v==0||p==0)
return;
pd(u,p),pd(v,p);
mg(lc[u],lc[v],p-1);
mg(rc[u],rc[v],p-1);
pu(u);
}
void upd(int u,int p,int x)
{
if(!u)
return;
if(!(x&t0[u]&t1[u]))
{
pt(u,p,x&t0[u]);
return;
}
pd(u,p);
if(x>>(p-1)&1)
{
pt(lc[u],p-1,1<<(p-1));
mg(rc[u],lc[u],p-1);
lc[u]=0;
}
upd(lc[u],p-1,x);
upd(rc[u],p-1,x);
pu(u);
}
int ask(int u,int p,int l,int r,int a,int b)
{
if(b<=l||r<=a||!u)
return 0;
if(a<=l&&r<=b)
return tr[u];
pd(u,p);
int mid=l+r>>1;
return ask(lc[u],p-1,l,mid,a,b)+ask(rc[u],p-1,mid,r,a,b);
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
u=ins(u,20,x);
}
while(q--)
{
int t,l,r,v,x;
scanf("%d%d%d",&t,&l,&r);
r++;
if(t<=3)
{
scanf("%d",&x);
split(u,v,20,0,f+1,l,r);
if(t==1)
pt(v,20,f),upd(v,20,x^f),pt(v,20,f);
if(t==2)
upd(v,20,x);
if(t==3)
pt(v,20,x);
mg(u,v,20);
}
else
printf("%d\n",ask(u,20,0,f+1,l,r));
}
return 0;
}

C++ (solution 2)

Phoenix and Bits solution codeforces Phoenix and Bits solution codeforces Phoenix and Bits solution codeforces

#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
struct Node {
int cnt;
int type;
int tag;
int both;
int d;
Node *lc, *rc;
};
Node *null = new Node();
Node *newNode(int d) {
Node *t = new Node();
*t = *null;
t->d = d;
return t;
}
Node *merge(Node *, Node *);
void maintain(Node *);
void pull(Node *t) {
if (t->d == 0) {
return;
}
t->cnt = t->lc->cnt + t->rc->cnt;
t->both = t->lc->both | t->rc->both;
if (t->lc != null && t->rc != null) {
t->both |= 1 << (t->d - 1);
}
maintain(t);
}
void apply(Node *t, int type, int tag) {
if (t == null || t->d == 0) {
return;
}
t->type |= type;
t->tag |= tag & type;
t->tag &= tag | ~type;
t->tag ^= tag & ~type;
maintain(t);
}
void push(Node *t) {
if (t->type >> (t->d - 1) & 1) {
if (t->tag >> (t->d - 1) & 1) {
t->rc = merge(t->lc, t->rc);
t->lc = null;
apply(t->rc, t->type, t->tag);
} else {
t->lc = merge(t->lc, t->rc);
t->rc = null;
apply(t->lc, t->type, t->tag);
}
} else {
if (t->tag >> (t->d - 1) & 1) {
std::swap(t->lc, t->rc);
}
apply(t->lc, t->type, t->tag);
apply(t->rc, t->type, t->tag);
}
t->type = t->tag = 0;
}
void maintain(Node *t) {
if (t == null) {
return;
}
if (!(t->both & t->type)) {
return;
}
push(t);
maintain(t->lc);
maintain(t->rc);
pull(t);
}
Node *merge(Node *a, Node *b) {
if (a == null) {
return b;
}
if (b == null) {
return a;
}
if (a->d == 0) {
a->cnt = a->cnt | b->cnt;
delete b;
return a;
}
push(a);
push(b);
a->lc = merge(a->lc, b->lc);
a->rc = merge(a->rc, b->rc);
delete b;
pull(a);
return a;
}
void add(Node *&t, int v, int d) {
if (t == null) {
t = newNode(d);
}
if (d == 0) {
t->cnt = 1;
} else {
if (~v >> (d - 1) & 1) {
add(t->lc, v, d - 1);
} else {
add(t->rc, v, d - 1);
}
pull(t);
}
}
std::vector<std::pair<int, Node *>> nodes;
void modify1(Node *&t, int L, int R, int l, int r, int x, int type) {
if (L >= r || R <= l) {
return;
}
if (t == null) {
return;
}
if (L >= l && R <= r) {
Node *backup = t;
t = null;
if (type == 1) {
apply(backup, ~x, 0);
nodes.emplace_back(L & x, backup);
} else if (type == 2) {
apply(backup, x, x);
nodes.emplace_back(L | x, backup);
} else {
apply(backup, 0, x);
nodes.emplace_back(L ^ x, backup);
}
return;
}
int m = (L + R) / 2;
push(t);
modify1(t->lc, L, m, l, r, x, type);
modify1(t->rc, m, R, l, r, x, type);
pull(t);
}
void modify2(Node *&t, int l, int r, int d) {
if (t == null) {
t = newNode(d);
}
while (l < r && nodes[l].second->d == d) {
t = merge(t, nodes[l].second);
l++;
}
if (l == r) {
return;
}
int mid = l;
while (mid < r && (~nodes[mid].first >> (d - 1) & 1)) {
mid++;
}
push(t);
modify2(t->lc, l, mid, d - 1);
modify2(t->rc, mid, r, d - 1);
pull(t);
}
int query(Node *t, int L, int R, int l, int r) {
if (t == null) {
return 0;
}
if (L >= r || R <= l) {
return 0;
}
if (L >= l && R <= r) {
return t->cnt;
}
int m = (L + R) / 2;
push(t);
return query(t->lc, L, m, l, r) + query(t->rc, m, R, l, r);
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
null->cnt = null->type = null->tag = null->both = 0;
null->lc = null->rc = null;
int n, q;
std::cin >> n >> q;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
Node *root = null;
for (int i = 0; i < n; i++) {
add(root, a[i], 20);
}
while (q--) {
int op, l, r, x;
std::cin >> op >> l >> r;
r++;
if (op <= 3) {
std::cin >> x;
modify1(root, 0, 1 << 20, l, r, x, op);
std::sort(nodes.begin(), nodes.end(), [&](const auto &a, const auto &b) {
int va = a.first & ~((1 << a.second->d) - 1);
int vb = b.first & ~((1 << b.second->d) - 1);
if (va != vb) {
return va < vb;
}
return a.second->d > b.second->d;
});
modify2(root, 0, nodes.size(), 20);
nodes.clear();
} else {
std::cout << query(root, 0, 1 << 20, l, r) << "\n";
}
}
return 0;
}

C11

Phoenix and Bits solution codeforces Phoenix and Bits solution codeforces Phoenix and Bits solution codeforces

#include <stdio.h>
#include <stdlib.h>
#define N 200000
#define Q 100000
#define N_ ((N + Q * 2) * (LG + 1))
#define LG 20
#define B (1 << LG)
int ll[1 + N_], rr[1 + N_], sz[1 + N_], msk0[1 + N_], msk1[1 + N_], lz[1 + N_], _ = 1;
void put(int u, int lg, int x) {int tmp, x0, x1;if (u == 0)return;if ((x & 1 << lg - 1) != 0)tmp = ll[u], ll[u] = rr[u], rr[u] = tmp;
x0 = msk0[u] & ~x | msk1[u] & x, x1 = msk1[u] & ~x | msk0[u] & x;msk0[u] = x0, msk1[u] = x1;lz[u] ^= x;}
void pus(int u, int lg) {if (lz[u])put(ll[u], lg - 1, lz[u]), put(rr[u], lg - 1, lz[u]), lz[u] = 0;}
void pul(int u) {int l = ll[u], r = rr[u];sz[u] = sz[l] + sz[r], msk0[u] = msk0[l] | msk0[r], msk1[u] = msk1[l] | msk1[r];}
int add(int u, int lg, int a) {if (u == 0)u = _++;if (lg == 0)sz[u] = 1, msk0[u] = a ^ B - 1, msk1[u] = a;
else {if ((a & 1 << lg - 1) == 0)ll[u] = add(ll[u], lg - 1, a);else rr[u] = add(rr[u], lg - 1, a);pul(u);}return u;}
void split(int *u, int *v, int lg, int l, int r, int ql, int qr) {
int m;

if (qr <= l || r <= ql || *u == 0) {
*v = 0;
return;
}
if (ql <= l && r <= qr) {
*v = *u, *u = 0;
return;
}
pus(*u, lg), *v = _++;
m = (l + r) / 2;
split(&ll[*u], &ll[*v], lg - 1, l, m, ql, qr), split(&rr[*u], &rr[*v], lg - 1, m, r, ql, qr);
pul(*u), pul(*v);
}

void merge(int *u, int *v, int lg) {if (*u == 0) {*u = *v;return;}if (*v == 0 || lg == 0)return;pus(*u, lg), pus(*v, lg);merge(&ll[*u], &ll[*v], lg - 1), merge(&rr[*u], &rr[*v], lg - 1);pul(*u);}
void update_or(int u, int lg, int x) {
if (u == 0)
return;
if ((x & msk0[u] & msk1[u]) == 0) {
put(u, lg, x & msk0[u]);
return;
}
pus(u, lg);
if ((x & 1 << lg - 1) != 0)
put(ll[u], lg - 1, 1 << lg - 1), merge(&rr[u], &ll[u], lg - 1), ll[u] = 0;
update_or(ll[u], lg - 1, x), update_or(rr[u], lg - 1, x);
pul(u);
}

int query(int u, int lg, int l, int r, int ql, int qr) {
int m;

if (qr <= l || r <= ql || u == 0)
return 0;
if (ql <= l && r <= qr)
return sz[u];
pus(u, lg);
m = (l + r) / 2;
return query(ll[u], lg - 1, l, m, ql, qr) + query(rr[u], lg - 1, m, r, ql, qr);
}

int main() {
int n, q, i, u;

scanf("%d%d", &n, &q);
u = 0;
for (i = 0; i < n; i++) {
int a;

scanf("%d", &a);
u = add(u, LG, a);
}
while (q--) {
int type, l, r;

scanf("%d%d%d", &type, &l, &r), r++;
if (type != 4) {
int x, v;

scanf("%d", &x);
split(&u, &v, LG, 0, B, l, r);
if (type == 1)
put(v, LG, B - 1), update_or(v, LG, x ^ B - 1), put(v, LG, B - 1);
else if (type == 2)
update_or(v, LG, x);
else
put(v, LG, x);
merge(&u, &v, LG);
} else
printf("%d\n", query(u, LG, 0, B, l, r));
}
return 0;
}

Phoenix and Bits solution codeforces Phoenix and Bits solution codeforces Phoenix and Bits solution codeforces

Phoenix and Bits solution codeforces - Phoenix loves playing with bits , 2021 Splitting a String Into Descending Consecutive Values Minimum Adjacent Swaps to Reach the Kth Smallest Number Minimum Interval to Include Each Query
 
 

Leave a Comment