题目

题目描述

有些时候，出题人真的不想写背景（？？？）
总而言之，天照现在有一个长度为$N$序列，她有$M$次询问，对于第$i$次询问$l_i,r_i,x_i$你需要回答：
$(A_l+x_i)~xor~(A_{l+1}+x_i)~xor \cdots xor~(A_r+x_i)$
其中$xor$代表按位异或，我们会用一些手段来保证强制在线

输入格式

第一行为两个整数$N,M,type$，代表序列的长度和询问的个数以及数据的类型
第二行为$N$个数字，其中第$i$个数字代表$A_i$
接下来$M$行，每行代表一个询询问$l_i,r_i,x_i$，其中真实的$l_i,r_i,x_i$需要异或$type \times lastans$，其中$lastans$为上一次询问的答案，初始为$0$

输出格式

共$M$行，代表每次询问的答案。

样例

样例输入

样例输出

1
2

5
4

数据范围与提示

对于此题，有五个测试点：
A（$5$分）$N,M \leqslant 2000$
B（$16$分）$type=0,l_i=1,r_i=n$
C（$20$分）$type=0$
D（$18$分）$l_i=1,r_i=n$
E（$41$分）$N,M \leqslant 10^5$

题解

对于答案的第$k$位（从大到小考虑），大于$k$的位都是没啥用，把$A$和$x$数组大于$k$的位都去掉
首先，我们先考虑$x_i=0$的情况
如果$x_i=0$，那第$i$位是$1$的数只能是$(100\cdots 0)_2\sim (111\cdots 1)_2$之间，是一段连续的区间
接着，我们来考虑$x_i>0$的情况
$x_i>0$，那第$i$位是$1$的数还是一段连续的区间，我们可以求出这一段区间的范围
所以我们只需要求出$A_{l_i}\sim A_{r_i}$中有多少个数字在这一段区间中
用主席树（可持久化线段树）维护$A_i$就可以了
附上代码：

#include<algorithm>
#include<cstdio>
using namespace std;
int n,m,type,tot,ans,a[100010],root[32][100010];
struct HJT 
{
    int ls,rs;
    bool sum;
}t[30000010];
void change(int u,int v,int l,int r,int x)
{
    if(l==r){t[v].sum=(t[u].sum^1);return;}
    int mid=(l+r)/2;
    if(x<=mid) t[v].ls=++tot,t[v].rs=t[u].rs,change(t[u].ls,t[v].ls,l,mid,x);
    else t[v].rs=++tot,t[v].ls=t[u].ls,change(t[u].rs,t[v].rs,mid+1,r,x);
    t[v].sum=(t[t[v].ls].sum^t[t[v].rs].sum);
}
int ask(int u,int v,int l,int r,int L,int R)
{
    if(l>R||r<L) return 0;
    if(l>=L&&r<=R) return (t[v].sum^t[u].sum);
    int mid=(l+r)/2;
    return (ask(t[u].ls,t[v].ls,l,mid,L,R)^ask(t[u].rs,t[v].rs,mid+1,r,L,R));
}
int main()
{
    freopen("amaterasu.in","r",stdin);
    freopen("amaterasu.out","w",stdout);
    scanf("%d%d%d",&n,&m,&type);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) for(int j=20;j>=0;j--){
        root[j][i]=++tot,change(root[j][i-1],root[j][i],0,(1<<(j+2))-1,a[i]);
        if(a[i]&(1<<j)) a[i]-=(1<<j);
    }
    for(int i=1,l,r,x;i<=m;i++){
        scanf("%d%d%d",&l,&r,&x),l^=(type*ans),r^=(type*ans),x^=(type*ans),ans=0;
        for(int j=20,temp1,temp2;j>=0;j--){
            temp1=ask(root[j][l-1],root[j][r],0,(1<<(j+2))-1,max((1<<j)-x,0),(1<<(j+1))-x-1);
            temp2=ask(root[j][l-1],root[j][r],0,(1<<(j+2))-1,(1<<(j+1))+(1<<j)-x,(1<<(j+2))-x-1);
            ans+=(temp1^temp2)*(1<<j);
            if(x&(1<<j)) x-=(1<<j);
        }
        printf("%d\n",ans);
    }
}