题解：P10401 「XSOI-R1」区间操作

封面

思路：

使用前缀和，考虑到输入的询问范围可能会有 ll 相同，所以先用一个结构体把输入的 ll 和 rr 和输入的顺序存起来，然后进行排序哪个左端点更小，如果同时左端点相同，那么比较哪个右端点更小。

在 ll 相等时，我们可以直接按照上一个的答案往下搜这样重复的部分就不用重复计算历遍了。

为什么可以直接按照上一个的答案往下搜，因为我们在一开始排过序，只要这个结构体排完序后在前一个结构体后面，并且 ll 相同，那么后面的结构体的 rr 一定大于等于前面的结构体的 rr，所以可以直接按照上一个的答案往下搜。

当 ll 不相等时，就正常地直接历遍，然后存答案就可以了。

完整代码：

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define LL long long
ull tamp;
const int MAXN=10001;
const int MAXQ=1000001;
ull n,q;
ull sum[MAXN];
ull a[100010];
struct node{
	ull l,r,id,ans;// 存左、右端点和输入顺序和答案 
}wt[MAXQ];
bool cmp_id(node x,node y){// 通过输入顺序还原后再输出 
	return x.id<y.id;
}
bool cmp_lr(node x,node y){// 排序哪个先开始如果同时开始那么比较哪个先结束 
	if(x.l==y.l)return x.r<y.r;// 如果左端点也就是 l 相同那么比较右端点 
	return x.l<y.l;// 如果 l 不相同比较那个的 l 更前面 
}
void find(){
	ull su;
	for(ull i=1;i<=q;i++){//q 个问题 
		if(wt[i].l!=wt[i-1].l){// 上一个结构体的 l 和这个结构体的 l 不相同 
			su=a[wt[i].l];//su 赋值为 a[wt[i].l]
			for(int j=wt[i].l+1;j<=wt[i].r;j++){// 从 wt[i].l+1 历遍到 wt[i].r 的答案 
				su^=(sum[j]-sum[wt[i].l-1]);
			}
			wt[i].ans=su;// 答案赋值 
		}
		else{
			if(wt[i].l==wt[i-1].l&&wt[i].r==wt[i-1].r){// 如果和上一个结构体的 l 和 r 相同说明答案也相同 
				wt[i].ans=su;// 直接赋值 
			}
			else{
				for(ull j=wt[i-1].r+1;j<=wt[i].r;j++){// 因为 l 相同且后面的结构体的 r 一定大于等于前面的结构体的 r 所以直接从前面的结构体的 r 的后面开始历遍 
					su^=(sum[j]-sum[wt[i].l-1]);
				}
				wt[i].ans=su;// 答案赋值 
			}
		}
		
	}
}
int main(){
	cin>>n>>q;
	for(ull i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];// 计算前缀和 
	}
	for(ull i=1;i<=q;i++)cin>>wt[i].l>>wt[i].r,wt[i].id=i;// 输入问题的 l 和 r 并标记输入顺序 
	sort(wt+1,wt+1+q,cmp_lr);// 按 l 和 r 排序
	find();
	sort(wt+1,wt+1+q,cmp_id);// 按输入顺序排序
	for(ull i=1;i<=q;i++)cout<<wt[i].ans<<"\n";// 输出答案 
	return 0;
}