E题补题题解（AI润色）

我们需要高效处理两种核心操作：对数组a的区间更新（批量增加）和对数组p的区间查询（计算p的区间内对应a中元素的总和）。由于数据规模达1e5，直接暴力处理会超时，因此采用分块算法平衡效率：将数组分为若干块，对完整块用“懒标记”批量处理，对非完整块直接暴力操作，同时通过预处理贡献关系快速维护查询所需的总和。

分块基本设置

核心数组：
- a：长度为n的初始全0数组，支持区间增加。
- p：长度为n的映射数组，p[i]表示查询时需访问a[p[i]]。
分块设计：
- 将a和p均按块长len分为cnt块，块编号从1到cnt。
- lazy[i]：a的第i块的“懒标记”，记录该块整体需要增加的值（用于完整块的批量更新）。
- sum[i]：p的第i块的总和（即p的第i块中所有a[p[j]]的和，动态维护）。

预处理：贡献关系与前缀和

由于p到a的映射固定，可提前预处理“更新对查询的贡献”，避免每次更新时重复计算：

块对块贡献f[i][j]：
定义：当a的第i块整体加1时，p的第j块的总和sum[j]增加的量（即p的第j块中，p[k]属于a的第i块的元素个数）。
ff[i][j]：
定义：当a的第i个元素加1时，p的第j块的总和sum[j]增加的量（即p的第j块中，p[k] = i的元素个数）。
前缀和处理：
对f和ff在列方向（块编号）上做前缀和，得到：
- f_prefix[i][j]：a的第1到i块整体加1时，对p的第j块的总贡献（f_prefix[i][j] = f[1][j] + ... + f[i][j]）。
- ff_prefix[i][j]：a的第1到i个元素加1时，对p的第j块的总贡献（ff_prefix[i][j] = ff[1][j] + ... + ff[i][j]）。
  作用：通过前缀和，a的区间[l, r]更新对sum[j]的贡献可在O(1)时间内计算（如a的[l, r]加x，对sum[j]的贡献为(ff_prefix[r][j] - ff_prefix[l-1][j]) * x）。

一、区间更新`a`的操作

对a的[l, r]区间加x时，需分情况处理，并同步更新sum（p的块总和）：

完整块处理（a的块[L+1, R-1]）：
- 用lazy标记批量更新：lazy[i] += x（i为a的完整块编号）。
- 同步更新sum：利用f_prefix计算贡献，对p的所有块j，sum[j] += (f_prefix[R-1][j] - f_prefix[L][j]) * x。
非完整块处理（a的[l, rx[L]]和[lx[R], r]，rx[L]为a的第L块右边界，lx[R]为第R块左边界）：
- 暴力更新a的元素：a[i] += x（i为非完整块内的元素）。
- 同步更新sum：利用ff_prefix计算贡献，对p的所有块j，sum[j] += (ff_prefix[rx[L]][j] - ff_prefix[l-1][j] + ff_prefix[r][j] - ff_prefix[lx[R]-1][j]) * x。

二、查询操作（计算`p`的`[l, r]`区间总和）

查询时需结合sum（完整块的预计算总和）和暴力计算（非完整块的单点值）：

完整块查询（p的[L+1, R-1]块）：
直接累加sum[i]（i为p的完整块编号）。
非完整块查询（p的[l, rx[L]]和[lx[R], r]）：
暴力计算每个元素：a[p[i]] + lazy[pos[p[i]]]（pos[p[i]]为p[i]在a中所属的块编号，lazy用于叠加该块的批量更新值）。

为什么块长不取根号n? 因为此题卡内存限制，需要用时间换空间，1e5数据量n^(5/3)也能通过。

alt

#include<bits/stdc++.h>
using namespace std;

//const int mod=998244353;
//const int inv2=mod-mod/2;
//#define int __int128
//#define double long double
#define int long long
#define x first
#define y second
using u16=unsigned short;
using u32=unsigned int;
using u64=unsigned long long;
using pii=pair<int,int>;
using pipii=pair<int,pii>;
using piipi=pair<pii,int>;
using piipii=pair<pii,pii>;
using vi=vector<int>;
using vc=vector<char>;
using vpii=vector<pii>;
using vvi=vector<vector<int>>;
using vvc=vector<vector<char>>;

void solve()
{
	int n,m;cin>>n>>m;
	vi a(n+1),p(n+1),h[n+1];
	for(int i=1;i<=n;i++)
	{
		cin>>p[i];
		h[p[i]].push_back(i);//反向映射 
	}
	
	int len=pow(n,2.0/3.0);//块长
	int cnt=(n+len-1)/len;//块数
	
	vi lx(cnt+1),rx(cnt+1),pos(n+1),lazy(cnt+1),sum(cnt+1);
	for(int i=1;i<=n;i++)pos[i]=(i+len-1)/len;
	for(int i=1;i<=cnt;i++)lx[i]=(i-1)*len+1,rx[i]=min(n,i*len);
	
	vvi f(cnt+1,vi(cnt+1));//O(n*sqrt(n))复杂度预处理f[i][j]:a的第i块整体+1时对p的第j块整体的贡献
	for(int i=1;i<=cnt;i++)
		for(int j=1;j<=cnt;j++)
			for(int k=lx[j];k<=rx[j];k++)
				if(p[k]>=lx[i] && p[k]<=rx[i])f[i][j]++;
	
	vvi ff(n+1,vi(cnt+1));//O(n)复杂度预处理ff[i][j]:a的第i个数+1时对p的第j块整体的贡献
	for(int i=1;i<=n;i++)
		for(int j:h[i])ff[i][pos[j]]++;	 
	
	for(int i=1;i<=cnt;i++)
		for(int j=1;j<=cnt;j++)f[i][j]+=f[i-1][j];//列方向前缀和
		
	for(int i=1;i<=n;i++)
		for(int j=1;j<=cnt;j++)ff[i][j]+=ff[i-1][j];//列方向前缀和
	
	int pre_ans=0;
	while(m--)
	{
		int op;cin>>op;
		if(op==1)//区间加
		{
			int l,r,x;cin>>l>>r>>x;
			l^=pre_ans,r^=pre_ans,x^=pre_ans;
			int L=pos[l],R=pos[r];
			if(L==R)//同一块中
			{
				for(int i=l;i<=r;i++)a[i]+=x;
				for(int j=1;j<=cnt;j++)sum[j]+=(ff[r][j]-ff[l-1][j])*x;
			}
			else
			{
				for(int i=l;i<=rx[L];i++)a[i]+=x;
				for(int i=lx[R];i<=r;i++)a[i]+=x;
				for(int j=1;j<=cnt;j++)sum[j]+=(ff[rx[L]][j]-ff[l-1][j]+ff[r][j]-ff[lx[R]-1][j])*x;//点对块更新 
				
				for(int i=L+1;i<=R-1;i++)lazy[i]+=x;
				for(int j=1;j<=cnt;j++)sum[j]+=(f[R-1][j]-f[L][j])*x;//块对块更新 
			}
		}
		else//区间查询
		{
			int l,r;cin>>l>>r;
			l^=pre_ans,r^=pre_ans;
			int L=pos[l],R=pos[r],ans=0;
			if(L==R)for(int i=l;i<=r;i++)ans+=a[p[i]]+lazy[pos[p[i]]];//同一块中 
			else
			{
				for(int i=l;i<=rx[L];i++)ans+=a[p[i]]+lazy[pos[p[i]]];
				for(int i=lx[R];i<=r;i++)ans+=a[p[i]]+lazy[pos[p[i]]];
				for(int i=L+1;i<=R-1;i++)ans+=sum[i];
			}
			cout<<ans<<'\n';
			pre_ans=ans;
		}
	}
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	solve();
	return 0;
}

题解 | #Onewan的疑惑#