这次是真的惨，码了将近2hours的可持久化线段树炸掉了！

而且本地拍了一万年也没发现哪里炸了。

T1 压位的入门题，话说这道题能拿个99分就可以了（100分要FFT）

对于暴力，就是暴力找所有不相同的i的个数，但是，我们发现对于这种01串的题目可以很舒服的压一下位

比如对于10011，十进制下就是19

而对于01110，十进制下是14

我们发现两个串的不同之处就是满足a[i]^b[i]=1的数对总数

因此我们可以对十进制数也进行xor，即19^14=31,31在二进制下为：11101，恰好满足以上的性质

所以我们可以直接用压位后的十进制数进行xor操作，最后统计这个数中有几个1即可

对于1的个数，可以做以下递推，对于每一个十进制数i，转化为二进制下1的个数为num[i],则

num[i]=num[i>>1]+（i&1）

然后就是压位+暴力找了

CODE

#include
    
     using namespace std;const int P=16,N=500005,M=1000005;bool a[N],b[M];int bl_a[N],bl_b[M],num[(1<
     
      '9') ch=tc();    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();}inline void write(int x){    if (x/10) write(x/10);    putchar(x%10+'0');}int main(){    register int i,j;    //freopen("A.in","r",stdin); freopen("A.out","w",stdout);    ch=tc(); while (ch=='-'||ch=='\n') ch=tc(); while (ch!=' '&&ch!='\n') a[n++]=ch-'0',ch=tc();    ch=tc(); while (ch=='-'||ch=='\n') ch=tc(); while (ch!=' '&&ch!='\n') b[m++]=ch-'0',ch=tc();    for (i=0;i<(1<
      
       >1]+(i&1);    for (i=0;i
       
        =n) break;        bl_a[i]=(bl_a[i]<<1)|a[i+j];    }    for (i=0;i
        
         =m) break;        bl_b[i]=(bl_b[i]<<1)|b[i+j];    }    read(q);    while (q--)    {        read(p1); read(p2); read(len);        p2=(p2^last)%(m-len+1);        i=ans=0;        while (i+P
        
       
      
     
    

T2 考试的时候看了很久没看懂题意

其实理解了题意还是很可做的狗的

标算也比较难，这里放一个爆搜CODE吧

#include
    
     using namespace std;const int N=100005,mod=100000007;bool f[N],t[N];int n,m,a[N][3],ans;inline char tc(void){    static char fl[100000],*A=fl,*B=fl;    return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;}inline void read(int &x){    x=0; char ch=tc(); int flag=1;    while (ch<'0'||ch>'9') { if (ch=='-') flag=-1; ch=tc(); }    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();    x*=flag;}inline bool get(int x){    if (x<0) return !f[-x]; else return f[x];}inline void check(void){    register int i;    for (i=1;i<=n;++i)    {        t[i]=get(a[i][1]);        if (a[i][0]>1) t[i]|=get(a[i][2]);    }    bool res;    for (res=t[1],i=2;i<=n;++i)    res^=t[i];    if (res) ans=ans==mod-1?0:ans+1;}inline void DFS(int now){    if (now>m) { check(); return; }    f[now]=1; DFS(now+1); f[now]=0; DFS(now+1);}int main(){    register int i,j;    //freopen("B.in","r",stdin); freopen("B.out","w",stdout);    read(n); read(m);    for (i=1;i<=n;++i)    {        read(a[i][0]);        for (j=1;j<=a[i][0];++j)        read(a[i][j]);    }    DFS(1);    printf("%d",ans);}
    

T3 这其实并不是一道大力数据结构题

离线操作,对于所有的操作4，从它的返回点向它连一条边，否则从i-1连一条边给它

然后就组成了一棵树，O(n）DFS即可，注意回溯的时候要反向操作

CODE

#include
    
     #include
     
      using namespace std;const int Q=300005,N=1005;struct edge{    int to,next;}e[Q];struct data{    int opt,x,y;    bool vis;}a[Q];bool map[N][N],tag[N];int head[Q],ans[Q],num[N],tot,n,m,q,k;inline char tc(void){    static char fl[100000],*A=fl,*B=fl;    return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;}inline void read(int &x){    x=0; char ch=tc();    while (ch<'0'||ch>'9') ch=tc();    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();}inline void write(int x){    if (x/10) write(x/10);    putchar(x%10+'0');}inline void add(int x,int y){    e[++k].to=y; e[k].next=head[x]; head[x]=k;}inline void work(int now){    if (a[now].opt==1&&!(tag[a[now].x]^map[a[now].x][a[now].y])) map[a[now].x][a[now].y]^=1,++tot,++num[a[now].x],a[now].vis=1;    if (a[now].opt==2&&tag[a[now].x]^map[a[now].x][a[now].y]) map[a[now].x][a[now].y]^=1,--tot,--num[a[now].x],a[now].vis=1;    if (a[now].opt==3) tag[a[now].x]^=1,tot+=m-num[a[now].x]*2,num[a[now].x]=m-num[a[now].x];}inline void replay(int now){    if (a[now].opt==1&&a[now].vis) map[a[now].x][a[now].y]^=1,--tot,--num[a[now].x];    if (a[now].opt==2&&a[now].vis) map[a[now].x][a[now].y]^=1,++tot,++num[a[now].x];    if (a[now].opt==3) tag[a[now].x]^=1,tot+=m-num[a[now].x]*2,num[a[now].x]=m-num[a[now].x];}inline void DFS(int now){    work(now);    ans[now]=tot;    for (register int i=head[now];i!=-1;i=e[i].next)    DFS(e[i].to);    replay(now);}int main(){    register int i;    memset(e,-1,sizeof(e));    memset(head,-1,sizeof(head));    //freopen("C.in","r",stdin); freopen("C.out","w",stdout);    read(n); read(m); read(q);    for (i=1;i<=q;++i)    {        read(a[i].opt); read(a[i].x);        if (a[i].opt<=2) read(a[i].y);        if (a[i].opt!=4) add(i-1,i); else add(a[i].x,i);    }    DFS(0);    for (i=1;i<=q;++i)    write(ans[i]),putchar('\n');    return 0;}