不会主席树怎么办？来尝试分块吧。

这题不带修我不是很认可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10,M=1010;
int a[N],a1[N],s1[N],n,B;
void pushup(int x)
{
	int l=(x-1)*B+1,r=min(n,x*B);
	for(int i=l;i<=r;i++)a1[i]=a[i];
	sort(a1+l,a1+r+1);
	s1[l]=a1[l];for(int i=l+1;i<=r;i++)s1[i]=s1[i-1]+a1[i];
}
int query(int l,int r,int x)
{
	int bl=(l-1)/B+1,br=(r-1)/B+1,ans=0;
	if(bl==br)
	{
		for(int i=l;i<=r;i++)
			if(a[i]<=x)ans+=a[i];
	}
	else
	{
		for(int i=l;i<=bl*B;i++)
			if(a[i]<=x)ans+=a[i];
		for(int i=(br-1)*B+1;i<=r;i++)
			if(a[i]<=x)ans+=a[i];
		for(int i=bl+1;i<br;i++)
		{
			if(a1[(i-1)*B+1]>x)continue;
			int l=1,r=B,res=1;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				if(a1[(i-1)*B+mid]<=x)l=mid+1,res=mid;
				else r=mid-1;
			}
			ans+=s1[(i-1)*B+res];
		}
	}
	return ans;
}
signed main()
{
	int q,lst=0;cin>>n;B=sqrt(n);
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=(n-1)/B+1;i++)pushup(i);
	cin>>q;
	while(q--)
	{
		int l,r,x;cin>>l>>r>>x;
		l^=lst,r^=lst,x^=lst;
		int ans=query(l,r,x);
		cout<<ans<<'\n';
		lst=ans;
	}
	return 0;
}