[XJOI]noip44 T3还有这种操作

还有这种操作

ttt 最近在学习二进制，他想知道小于等于N的数中有多少个数的二进制表示中有偶数个1。

但是他想了想觉得不够dark，于是他增加了若干次操作，每次操作会将一个区间内的0变1 ， 1变0，

现在在每次操作之后，他都想知道原来的那个问题的答案。

输入格式：

第一行：一个01序列表示N的二进制表示
第二行：操作次数 m
接下来的m行每行两个数，表示要操作的区间。

输出格式：

输出m+1行，第一行表示初始的答案，第二行到第m+1行输出每次操作后的答案
答案对1e9 + 7 取模

样例输入：

样例输出：

1

1

数据范围：

设 n为 N 的位数

10%, n <= 20, m <= 100
30%, n <= 60, m <= 10000
60%, n <= 1000, m <= 10000
100%, n <= 1000000, m <= 100000

解题思路：

在看到n<=2^1000000时，我的内心是震惊的，想着或者是字典树，线段树

于是想着线段树方向想，但是怎么统计答案又成为了一个问题...

加之题目并没有说l<=r，于是这道题就愉快的爆零了

***下面是正题

我们想用一个线段树，维护每一位的翻转次数，以及每一位的答案的值

那么我们就可以用nlogn的时间建出它，并用mlogn的时间来查询。

好线段树部分讲完了

***下面是关于统计答案的

我们首先可以发现

[0,1)内有2^0=1个

[0,10)内有2^0=1个

[0,100)内有2^1=2个

[0,1000)内有2^2=4个（以上数均为二进制表示）

...

那么我们可以总结了，[0,100..00（n个0）)内有2^（n-1）个数满足，此时n>=1（为什么下面会讲）

但是知道这个有什么用么？

我们想一个 1010=1000+10

答案就为[0,1000)+[0,10)+check(1010是否满足)

这个结论的证明留给读者去完成

***于是这个程序基本就成型了

注意：（1）l是可能大于r的

（2）在对于最后一位处理，需要特殊处理，否则，对于最后一位是1的数，会出现1的差别，

例如：101 如按原先方法计算，答案为2+1+check（101）=4，而正确答案是3

因此在遇到原串符合条件，且最后一位是1时，要对答案减一

 #include<bits/stdc++.h>

 using namespace std;

 const int N=5e6+,p=1e9+;

 struct xint {int l,r;}a[N];

 int val[N],sum[N],pw[N],bo[N],n[N],m,l,r;

 char s[N]; bool flag;

 void pushup(int rt,int len){

     val[rt]=(1ll*val[rt<<]*pw[len]+val[rt<<|])%p;

     sum[rt]=sum[rt<<]^sum[rt<<|];

 }

 void opera(int rt){

     bo[rt]^=; val[rt]=((pw[a[rt].r-a[rt].l+]--val[rt])%p+p)%p;

     sum[rt]=((a[rt].r-a[rt].l+)&)^sum[rt];

 }

 void pushdown(int rt){

     if (bo[rt]) opera(rt*),opera(rt*+),bo[rt]=;

 }

 //--------------------------------

 void build(int l,int r,int rt){

     if (l>r) return; a[rt].l=l; a[rt].r=r;

     if (l==r){

         val[rt]=sum[rt]=n[l]; return;

     }

     int mid=(l+r)>>;

     build(l,mid,rt<<); build(mid+,r,rt<<|);

     pushup(rt,r-mid);

 }

 void update(int l,int r,int rt){

     if (l>r) return;

     if (a[rt].l==l&&a[rt].r==r){

         opera(rt); return;

     }

     int mid=(a[rt].l+a[rt].r)>>; pushdown(rt);

     if(r<=mid) update(l,r,rt<<);

         else if (l>mid) update(l,r,rt<<|);

         else update(l,mid,rt<<),update(mid+,r,rt<<|);

     pushup(rt,a[rt].r-mid);

 }

 int query(){

     return (val[]+bool(!sum[]||flag))%p;

 }

 //------------------------------

 int main(){

     scanf("%s%d",s+,&m); int len=strlen(s+);

     for (int i=len;i>=;--i) n[i]=s[i]-''; pw[]=;

     for (int i=;i<=len;++i) pw[i]=pw[i-]*%p;

     build(,len-,); flag=n[len]; printf("%d\n",query());

     while (m--){

         scanf("%d%d",&l,&r);

         if (l>r) swap(l,r);

         if (r==len) r--,flag^=;

         update(l,r,); printf("%d\n",query());

     }

 }

总结：个人觉得这是一道很好的线段树题目，当然对于我这种蒟蒻，线段树还不能熟练掌握的还要加油

***虽说联赛不考

巴特西