与非 乱搞233

题目大意：
初始时你有一个空序列，之后有N个操作。
操作分为一下两种：
1. x：在序列末尾插入一个元素x(x=0或1)。
2.LR:定义nand[L,R]为序列第L个元素到第R个元素的与非和，询问nand[L,L]^nand[L,L+1]^nand[L,L+2]^……^nand[L,R]。
Nand就是先与，再取反
f[n]=nand(1,i); sum[n]=∑ni=1f(i)
询问时
nand(l,r)=…(!(a[l]&a[l+1])&…)…
f(r)=…(!(f[l]&a[l+1])&…)…
∴当f[l]=a[l]时,nand(l,r)=f(r)
一直往后找就好了..
好像还能二分什么的优化,但我也不会..
有兴趣的读者自己思考…(滑稽)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 4000005
using namespace std;
int n,tot,a[N],f[N],sum[N];
int query(int l,int r){
    int now=l,s=!(a[l]&a[l+1]),ans=a[l];
    while(s!=f[now+1]&&now<r){
        ans^=s;
        now++;
        s=!(s&a[now+1]);
    }
    ans^=sum[r]^sum[now];
    return ans;
}
int main(){
    scanf("%d",&n);
    int ans=0;
    int opt,x,l,r;
    while(n--){
        scanf("%d",&opt);
        if(opt==1){
            scanf("%d",&x);
            x^=ans; a[++tot]=x;
            f[tot]=!(f[tot-1]&x);
            sum[tot]=sum[tot-1]^f[tot];
            if(tot==1) f[1]=sum[1]=x;
        }
        else{
            scanf("%d%d",&l,&r);
            if(ans==1){l=tot-l+1;r=tot-r+1;swap(l,r);}
            ans=query(l,r);
            printf("%d
",ans);
        }
    }
    return 0;
}