Description：

末尾加入一个 $0/1$ ，询问区间前缀与非和的异或和。

$1\leqslant $ 插入操作 $\leqslant 3900000,1\leqslant$ 询问操作 $\leqslant 100000$

Solution：

首先 $a\text{ nand }b=1-a\times b$ ，异或相当于是二进制下的加法，那么我们就可以强行把二进制操作当成加法和乘法操作，然后把区间的那个询问按照上面那个式子全部展开就会发现其实是一个询问区间所有子序列的积的和，不过第一/二个数要特判，然后这个可以用线段树维护前缀积的和，后缀积的和，子序列的积的和，但是这样复杂度 $O(n\log n)$ 还是不行，所以我们预处理所有长度为 $10$ 的序列的那三个值，然后只用线段树维护块就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

    register int res = 0,f = 1;register char c = getchar();

    while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

    while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

    return res * f;

}

int n;

#define MAXN 4000010

#define N 400000

int a[MAXN],tot = 0,st[MAXN];

int nand(int a,int b){return ((a & b) ^ 1);}

struct state

{

    int mul,msum,lsum,rsum;

    state(int k = 0){mul = msum = lsum = rsum = k;}

    void set(int k){mul = msum = lsum = rsum = k;return;}

}v[1 << 10];

state operator + (state lc,state rc)

{

    state rt;

    rt.mul = lc.mul & rc.mul;

    rt.msum = lc.msum ^ rc.msum ^ (lc.rsum & rc.lsum);

    rt.lsum = lc.lsum ^ (rc.lsum & lc.mul);

    rt.rsum = rc.rsum ^ (lc.rsum & rc.mul);

    return rt;

}

struct node

{

    int lc,rc;state s;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

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

{

    rt = newnode();

    if(l == r)return;

    build(t[rt].lc,l,mid);

    build(t[rt].rc,mid + 1,r);

    return;

}

void clear(int rt,int l,int r)

{

    if(l != r)

    {

        clear(t[rt].lc,l,mid);

        clear(t[rt].rc,mid + 1,r);

    }

    memset(&t[rt],0,sizeof(&t[rt]));

    return;

}

void set(int rt,int p,state ss,int l,int r)

{

    if(l == r){t[rt].s = ss;return;}

    if(p <= mid)set(t[rt].lc,p,ss,l,mid);

    else set(t[rt].rc,p,ss,mid + 1,r);

    t[rt].s = t[t[rt].lc].s + t[t[rt].rc].s;

    return;

}

state query(int rt,int L,int R,int l,int r)

{

    if(L <= l && r <= R)return t[rt].s;

    if(R <= mid)return query(t[rt].lc,L,R,l,mid);

    if(L > mid)return query(t[rt].rc,L,R,mid + 1,r);

    return query(t[rt].lc,L,R,l,mid) + query(t[rt].rc,L,R,mid + 1,r);

}

state calc(int l,int r)

{

    if(l == r)return (state){a[l]};

    return calc(l,mid) + calc(mid + 1,r);

}

state query(int l,int r)

{

    int idl = (l - 1) / 10 + 1,idr = (r - 1) / 10 + 1;

    if(idl == idr)return calc(l,r);

    else if(idr - idl == 1)return calc(l,idl * 10) + calc(idl * 10 + 1,r);

    else return calc(l,idl * 10) + query(root,idl + 1,idr - 1,1,N) + calc(idr * 10 - 9,r);

}

int main()

{

    scanf("%d",&n);

    int opt,l,r,x;

    int lastans = 0;

    for(int i = 0;i < (1 << 10);++i)

    {

        build(root,1,10);

        for(int j = 1;j <= 10;++j)set(root,j,(state){(i >> (10 - j)) & 1},1,10);

        v[i] = t[root].s;

        clear(root,1,10);

        ptr = root = 0;

    }

    build(root,1,N);

    while(n--)

    {

        scanf("%d",&opt);

        if(opt == 1)

        {

            scanf("%d",&x);

            x ^= lastans;

            a[++tot] = x;

            st[st[0]] = st[st[0]] << 1 | x;

            if(tot % 10 == 0)

            {

                set(root,st[0],v[st[st[0]]],1,N);

                ++st[0];

            }

        }

        else

        {

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

            if(lastans == 1)

            {

                l = tot - l + 1;r = tot - r + 1;

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

            }

            if(l == r)printf("%d\n",lastans = a[l]);

            else if(r - l == 1)printf("%d\n",lastans = (a[l] ^ nand(a[l],a[r])));

            else

            {

                state res = query(l + 2,r);

                int ans = (r - l) & 1;

                ans = ans ^ res.msum;

                int val = a[l] & a[l + 1];

                ans = ans ^ (res.lsum & val);

                ans = ans ^ val;

                ans = ans ^ a[l];

                lastans = ans;

                printf("%d\n",ans);

            }

        }

    }

    return 0;

}