题目来源：
题目描述
AKN觉得第一题太水了，不屑于写第一题，所以他又玩起了新的游戏。在游戏中，他发现，这个游戏的伤害计算有一个规律，规律如下
1、 拥有一个伤害串为长度为n的01串。
2、 给定一个范围[l,r]，伤害为伤害串的这个范围内中1的个数
3、 会被随机修改伤害串中的数值，修改的方法是把[l,r]中的所有数xor上1
AKN想知道一些时刻的伤害，请你帮助他求出这个伤害
输入输出格式
输入格式：
第一行两个数n,m,表示长度为n的01串，有m个时刻
第二行一个长度为n的01串，为初始伤害串
第三行开始m行，每行三个数p,l,r
若p为0，则表示当前时刻改变[l,r]的伤害串，改变规则如上
若p为1，则表示当前时刻AKN想知道[l,r]的伤害
输出格式：
对于每次询问伤害，输出一个数值伤害，每次询问输出一行
输入输出样例
输入样例#1：
10 610111010010 2 41 1 50 3 71 1 100 1 41 2 6
输出样例#1：
361
说明
样例解释：
1011101001
1100101001
询问[1,5]输出3
1111010001
询问[1,10]输出6
0000010001
询问[2,6]输出1
数据范围：
10%数据2≤n,m≤10
另有30%数据2≤n,m≤2000
100%数据2≤n,m≤2*10^5
By:worcher
解析：
水题快乐！
这道题的关键在lazytag的处理上。
我们不难发现01数列区间所有数值对1异或的规律：
给出一条长为n的01数列，若其1的数量为k，则其对1异或后的1的数量为为n-k；
例如：一条长为10的01数列:1011101001,1的数量为6，其对1111111111异或后得到数列：0100010110,1的数量为4；
得到如下pushdown操作：
1 t[p<<1].att=(t[p<<1].r-t[p<<1].l+1)-t[p<<1].att;2 t[(p<<1)|1].att=(t[(p<<1)|1].r-t[(p<<1)|1].l+1)-t[(p<<1)|1].att;
其他的还是差不多。
参考代码：
#include#include #include #include #include #include #include #include #include #define INF 0x3f3f3f3f#define PI acos(-1.0)#define N 200010#define MOD 2520#define E 1e-12using namespace std;struct segmentree{ int l,r; int att; bool flag;}t[N*4];void spread(int p){ if(t[p].flag) { t[p<<1].flag^=1; t[(p<<1)|1].flag^=1; t[p<<1].att=(t[p<<1].r-t[p<<1].l+1)-t[p<<1].att; t[(p<<1)|1].att=(t[(p<<1)|1].r-t[(p<<1)|1].l+1)-t[(p<<1)|1].att; t[p].flag=0; }}void built(int p,int l,int r){ t[p].l=l;t[p].r=r; if(l==r){ scanf("%1d",&t[p].att);//当然也可以使用字符串读入，且速度更快，不过这个读入比较冷门且写法简单 return; } int mid=(l+r)>>1; built(p<<1,l,mid); built((p<<1)|1,mid+1,r); t[p].att=t[p<<1].att+t[(p<<1)|1].att;}void change(int p,int l,int r){ if(l<=t[p].l&&t[p].r<=r){ t[p].att=(t[p].r-t[p].l+1)-t[p].att; t[p].flag^=1;//注意这里必须是^1，才能保证延迟标记的准确性 return; } spread(p); int mid=(t[p].l+t[p].r)>>1; if(l<=mid) change(p<<1,l,r); if(r>mid) change((p<<1)|1,l,r); t[p].att=t[p<<1].att+t[(p<<1)|1].att;}int ask(int p,int l,int r){ if(l<=t[p].l&&t[p].r<=r) return t[p].att; spread(p); int mid=(t[p].l+t[p].r)>>1; int val=0; if(l<=mid) val+=ask(p<<1,l,r); if(r>mid) val+=ask((p<<1)|1,l,r); return val;}int main(){ int n,m,flag; scanf("%d%d",&n,&m); built(1,1,n); int l,r; while(m--) { scanf("%d",&flag); scanf("%d%d",&l,&r); if(flag==0) change(1,l,r); else{ printf("%d\n",ask(1,l,r)); } } return 0;}
2019-05-13 18:32:10