自动搬运

查看原文

来自洛谷，原作者为

	wmrqwq 会登顶的。

搬运于2025-08-24 22:57:37，当前版本为作者最后更新于2024-04-07 20:25:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接

Link

解题思路

算法一：

暴力模拟，时间复杂度 $O(n^2q)$，可以获得 $13$ 分。

事实上常数不大的话可以获得 $20$ 分。

算法二：

发现异或和可以用前缀和维护，时间复杂度 $O(nq)$，可以获得 $48$ 分。

算法三：

我们发现可以暴力预处理每个区间的值，时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$，显然会 MLE。

于是我们只需要将每次询问离线，然后再预处理时判断是否询问到了这个区间即可，如果询问到了就将答案储存下来。

这样做时间复杂度 $O(n^2)$，空间复杂度 $O(q)$，可以获得 $100$ 分。

参考代码

#include<bits/stdc++.h>
using namespace std;
#define map unordered_map
#define forl(i,a,b) for(register long long i=a;i<=b;i++)
#define forr(i,a,b) for(register long long i=a;i>=b;i--)
#define forll(i,a,b,c) for(register long long i=a;i<=b;i+=c)
#define forrr(i,a,b,c) for(register long long i=a;i>=b;i-=c)
#define lc(x) x<<1
#define rc(x) x<<1|1
#define mid ((l+r)>>1)
#define cin(x) scanf("%lld",&x)
#define cout(x) printf("%lld",x)
#define lowbit(x) x&-x
#define pb push_back
#define pf push_front
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
#define ll long long
#define lcm(x,y) x/__gcd(x,y)*y
#define Sum(x,y) 1ll*(x+y)*(y-x+1)/2
ll t;
ll n,q,l,r,K;
ll a[100010],sum[100010],ans[1000010];
struct node{
	ll l,r,id;
}Q[1000010];
bool cmp(node x,node y){
	if(x.l==y.l)
		return x.r<y.r;
	return x.l<y.l;
}
void solve()
{
	cin>>n>>q;
	forl(i,1,n)
		cin>>a[i],sum[i]=sum[i-1]+a[i];
	forl(i,1,q)
		cin>>Q[i].l>>Q[i].r,Q[i].id=i;
	sort(Q+1,Q+1+q,cmp);
	K=1;
	forl(i,1,n)
	{
		if(i!=Q[K].l)
			continue;
		ll Sum=0;
		forl(j,i,n)
		{
			Sum^=(sum[j]-sum[i-1]);
			while(Q[K].r==j && Q[K].l==i)
				ans[Q[K].id]=Sum,K++;
			if(Q[K].l!=i)
				break;
			if(K==q+1)	
			{
				forl(i,1,q)
					cout<<ans[i]<<endl;
				return ;
			}
		}
	}
	if(K!=q+1)
		return ;
	forl(i,1,q)
		cout<<ans[i]<<endl;
}
int main()
{
	IOS;
	t=1;
//	cin>>t;
	while(t--)
		solve();
	QwQ;
}