网站空间800m,镇江网站建设优化排名,东莞市保安公司排名,郑州重点工程建设项目1.XOR的艺术
题意
给定一个长度为 n n n的、只含有数字 0 , 1 0,1 0,1的字符串和两种操作。
对于每种操作#xff0c;给定 o p , l , r op,l,r op,l,r#xff1a; o p 0 op0 op0表示将字符串的 [ l , r ] [l, r] [l,r]区间内的 0 0 0变成 1 1 1#xff0c; 1 1 1变成 0 …1.XOR的艺术
题意
给定一个长度为 n n n的、只含有数字 0 , 1 0,1 0,1的字符串和两种操作。
对于每种操作给定 o p , l , r op,l,r op,l,r o p 0 op0 op0表示将字符串的 [ l , r ] [l, r] [l,r]区间内的 0 0 0变成 1 1 1 1 1 1变成 0 0 0。 o p 1 op1 op1表示询问字符串的 [ l , r ] [l, r] [l,r]区间内有多少个字符 1 1 1。
思路
一段区间中非 0 0 0即 1 1 1那么该区间中 1 1 1的个数其实就是区间求和考虑使用线段树解决这个问题。
对于 o p 0 op0 op0这个取反操作设区间左右端点分别为 l , r l,r l,r原来的 1 1 1个数为 s u m sum sum取反一次原来 1 1 1的位置有 s u m sum sum处变成 0 0 0而原来为 0 0 0的位置有 ( r − l 1 ) − s u m (r-l1)-sum (r−l1)−sum处变成 1 1 1相当于现在 1 1 1的个数 s u m ′ ( r − l 1 ) − s u m sum(r-l1)-sum sum′(r−l1)−sum
知道了怎么更新区间了就好办了但是为了节省时间就要引入懒标记 t a g tag tag
可以令其表示区间要被处理的次数在下次修改或查询时当次数为奇数时才 p u s h d o w n pushdown pushdown下放因为翻转两次就相当于没反转
也可以直接让 t a g 0 tag0 tag0或 1 1 1来表示需不需要执行翻转操作每次更新就异或一次 1 1 1
线段树就只需要维护区间和 s u m sum sum即可。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ls u1
#define rs u1|1
const ll N2e59;
ll n,m,a[N];
char c[N];
struct SegT
{struct node{ll sum,tag;}T[N4];void pushup(ll u){T[u].sumT[ls].sumT[rs].sum;}void pushdown(ll u,ll l,ll r){if(T[u].tag){ll mid(lr)1;T[ls].sum(mid-l1)-T[ls].sum;T[rs].sum(r-mid)-T[rs].sum;}T[ls].tag^T[u].tag;T[rs].tag^T[u].tag;T[u].tag0;}void build(ll u,ll l,ll r){if(lr){T[u].suma[l];return;}ll mid(lr)1;build(ls,l,mid);build(rs,mid1,r);pushup(u);}void modify(ll u,ll l,ll r,ll ql,ll qr){if(qrl||rql)return;if(qllrqr){T[u].sum(r-l1)-T[u].sum;T[u].tag^1;return;}pushdown(u,l,r);ll mid(lr)1;if(qlmid)modify(ls,l,mid,ql,qr);if(qrmid)modify(rs,mid1,r,ql,qr);pushup(u);}ll query(ll u,ll l,ll r,ll ql,ll qr){if(qrl||rql)return 0;if(qllrqr)return T[u].sum;pushdown(u,l,r);ll mid(lr)1,ret0;if(qlmid)retquery(ls,l,mid,ql,qr);if(qrmid)retquery(rs,mid1,r,ql,qr);return ret;}
}A;
int main()
{scanf(%lld%lld%s,n,m,c1);for(int i1;in;i)a[i]c[i]-0;A.build(1,1,n);while(m--){ll op,l,r;scanf(%lld%lld%lld,op,l,r);if(op0)A.modify(1,1,n,l,r);if(op1)printf(%lld\n,A.query(1,1,n,l,r));}return 0;
}2.XOR on Segment
题意
给定 n n n个数的序列 a a a。 m m m次操作操作有两种
对于每种操作给定 o p , l , r op,l,r op,l,r o p 1 op1 op1表示要求区间 [ l , r ] [l,r] [l,r]内所有数的和 o p 2 op2 op2时给定 x x x并将区间 [ l , r ] [l,r] [l,r]所有数异或上 x x x 1 ≤ n ≤ 1 0 5 , 1 ≤ m ≤ 5 × 1 0 4 , 1 ≤ x , a i ≤ 1 0 6 1\le n\le 10^5,\ 1\le m\le 5\times10^4,\ 1\le x,a_i\le 10^6 1≤n≤105, 1≤m≤5×104, 1≤x,ai≤106
思路
对比上一题本题将 0 0 0和 1 1 1的序列推广到 [ 1 , 1 0 6 ] [1,10^6] [1,106]大了不少。
但能否和上一题产生关联呢
当然是可以的可以考虑用 0 , 1 0,1 0,1表示序列中每个数的二进制因为 1 ≤ a i ≤ 1 0 6 1\le a_i\le 10^6 1≤ai≤106所以二进制最多有 ⌈ log 2 1 0 6 ⌉ 20 \left \lceil \log_2{10^6} \right \rceil 20 ⌈log2106⌉20位。可以开 20 20 20棵线段树来维护 20 20 20个进制位做法和上一题大差不差了。
修改的时候如果 x x x与当前第 i i i位的“基底” 2 i 2^i 2i作且操作即 x a n d 2 i 0 x\ and\ 2^i 0 x and 2i0时那就无需对这一位更新因为异或 0 0 0相当于不用异或。
最后预处理 2 2 2的幂然后逐位相加就能得到查询的答案。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ls u1
#define rs u1|1
const int N1e59,M20;
int n,m,a[N];
int _2[M];
void init()
{_2[0]1;for(int i1;iM;i)_2[i]_2[i-1]*2;
}
struct SegT
{struct node{ll sum;int tag;}T[N2];void pushup(int u){T[u].sumT[ls].sumT[rs].sum;}void pushdown(int u,int l,int r){if(T[u].tag){int mid(lr)1;T[ls].sum(mid-l1)-T[ls].sum;T[rs].sum(r-mid)-T[rs].sum;T[ls].tag^T[u].tag;T[rs].tag^T[u].tag;T[u].tag0;}}void build(int u,int l,int r,int ws){if(lr){T[u].sum(ll)(a[l]_2[ws]?1:0);return;}int mid(lr)1;build(ls,l,mid,ws);build(rs,mid1,r,ws);pushup(u);}void modify(int u,int l,int r,int ql,int qr){if(qrl||rql)return;if(qllrqr){T[u].sum(ll)(r-l1)-T[u].sum;T[u].tag^1;return;}pushdown(u,l,r);int mid(lr)1;if(qlmid)modify(ls,l,mid,ql,qr);if(qrmid)modify(rs,mid1,r,ql,qr);pushup(u);}ll query(int u,int l,int r,int ql,int qr){if(qrl||rql)return 0;if(qllrqr)return T[u].sum;pushdown(u,l,r);int mid(lr)1;ll ret0;if(qlmid)ret(ll)query(ls,l,mid,ql,qr);if(qrmid)ret(ll)query(rs,mid1,r,ql,qr);return ret;}
}A[M];
int main()
{init();scanf(%d,n);for(int i1;in;i)scanf(%d,a[i]);for(int i0;iM;i)A[i].build(1,1,n,i);scanf(%d,m);while(m--){int op,l,r;scanf(%d%d%d,op,l,r);if(op1){ll ans0;for(int i0;iM;i)ans1ll*_2[i]*A[i].query(1,1,n,l,r);printf(%lld\n,ans);}else {int x;scanf(%d,x);for(int i0;iM;i)if(x_2[i])A[i].modify(1,1,n,l,r);}}return 0;
}
