自动搬运

查看原文

来自洛谷，原作者为

	nullqtr_pwp 我注意到有些人一直在做各种地方的cnoi题，但是并没有什么b用，可能是因为一直在舒适区里面舒服的卷，虐杀自己擅长的东西并获得成就感。

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

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

以下是正文

考虑把背包看成一个黑盒：支持 $\mathcal O(m)$ 插入物品，以及给出两个背包 $A,B$，以 $\mathcal O(m^2)$ 进行完全的合并，$\mathcal O(m)$ 对位相加信息，$\mathcal O(m)$ 查询合并后的一个点值，以及存储并回退。完全的背包合并因为 $m^2$ 所以不能使用。因为模 $m$ 意义，所以不能删除已有物品。

如果只需要处理所有 $f(S-\{i\})$，可以进行分治，每次递归时已经加入 $[1,l-1]\cup [r+1,n]$ 的物品即可，时间复杂度 $\mathcal O(nm\log n)$。还有一个问题是总对数是 $n^2$ 的，但是我们只需要求一个矩形区域的和，这个其实可以对背包数组对位相加然后整体维护，这样避免了合并。

考虑 $l_1=r_1,l_2=r_2$，查询单组 $(x,y)$ 值的做法：此时对 $(x,y)$ 进行猫树分治离线，挂到对应的 $[l,r]$ 上，维护 $[1,l-1]$ 的背包 $F$，$[r+1,n]$ 的背包 $G$，两侧分别做一次缺一分治，以 $F/G$ 为基础求出 $[1,mid]-\{i\}$ 以及 $[mid+1,n]-\{i\}$ 的背包信息，左右侧合并只需要查询合并后 $0$ 的点值，复杂度是 $\mathcal O(mn\log^2n+qm)$。

拓展这个猫树分治做法，将所有询问套路化的差分为 $\mathcal O(1)$ 对 $(x,y)$ 询问 $[1,x],[y,n]$ 的答案，保证 $x<y$。这时变成了求和。依然将其分为 $\leq mid,>mid$ 的物品，这时会涉及 $[1,l-1],[l,x]$ 以及 $[y,r],[r+1,n]$。那么贡献分为 $2\times 2=4$ 对，分类讨论一下：

• $x'\in[1,l-1],y'\in[r+1,n]$：处理出 $[1,l-1]$ 内所有 $i\in[1,l-1]$ 的 $f([1,l-1]-\{i\})$ 之和，令这个是 $g_{l-1}$，那么从 $g_t\to g_{t+1}$ 时只需要插入 $t+1$ 以及对 $[1,t]$ 的背包信息求对位和。对于后缀同理。这样求出 $pre_{l-1},suf_{r+1}$，整体分别加入 $[l,mid],[mid+1,r]$ 的所有物品，得到 $pre',suf'$ 的对位和，这时求一下 $pre'\times suf'$ 的常数项即可。
• $x'\in[1,l-1],y'\in[y,r]$（对于 $x'\in[l,x],y'\in[r+1,n]$ 同理）：分治求出 $[1,mid],[mid+1,r]$ 分别针对每个 $[l,mid],[mid+1,r]$ 的缺一信息，求前后缀和 $f,g$，与 $pre',suf'$ 分别求一下 $L\times R$ 的常数项即可。
• $x'\in[l,x],y'\in[y,r]$：针对 $f_x,g_y$ 做合并即可。

事实上并不需要拆成 $4$ 个，只需要 $f_x,g_y$ 分别与 $[1,l-1],[r+1,n]$ 预先合并即可。

综上，我们可以使用 $\mathcal O(n\log^2n)$ 次背包的基本操作就解决本题。时间复杂度 $\mathcal O(mn\log^2n+qm)$。本题的精髓在于对背包的对位加以实现求整体信息，以及分治算法的运用。其实可以理解成多项式的 $(\times,+)$ 运算，然后把分配律倒过来将他合并了。

int ans[QR],n,m,zsy,a[maxn],b[maxn];
#define poly vector<int>
poly mrg(poly x,poly y){
	poly res(m);
	F(i,0,m-1)res[i]=add(x[i],y[i]);
	return res;
}
poly ins(poly x,int pos){
	poly res=x;
	F(i,0,m-1)inc(res[i+a[pos]>=m?i+a[pos]-m:i+a[pos]],x[i]);
	F(i,0,m-1)inc(res[i+b[pos]>=m?i+b[pos]-m:i+b[pos]],x[i]);
	return res;
}
void init(poly &x){
	x.resize(m);
	F(i,0,m-1)x[i]=(i==0);
}
void init1(poly &x){
	x.resize(m);
	for(int &i:x)i=0;
}
int qry(poly &x,poly &y){
	int ans=0;
	F(i,0,m-1)inc(ans,1ll*x[i]*y[i==0?0:m-i]%mod);
	return ans;
}
vector<array<int,4>>qu[maxn<<2];
void ins_query(int o,int l,int r,int ql,int qr,int coef,int id){
	if(ql>qr||ql<1||qr>n)return;
	const int mid=(l+r)>>1;
	if(ql<=mid&&mid<qr)return qu[o].push_back({ql,qr,coef,id}),void();
	if(qr<=mid)ins_query(o<<1,l,mid,ql,qr,coef,id);
	if(ql>mid)ins_query(o<<1|1,mid+1,r,ql,qr,coef,id);
}
poly pre[maxn],suf[maxn],psum[maxn],ssum[maxn],f[maxn],dp[maxn];
void dfs(int o,int l,int r){
	if(l==r)return;
	const int mid=(l+r)>>1;
	dfs(o<<1,l,mid),dfs(o<<1|1,mid+1,r);
	if(qu[o].empty())return;
	poly F;
	auto sol=[&](auto &self,int L,int R){
		if(L==R)return f[L]=F,void();
		int mid=(L+R)>>1;
		poly tmp=F;
		F(i,L,mid)F=ins(F,i);
		self(self,mid+1,R);
		F=tmp;
		F(i,mid+1,R)F=ins(F,i);
		self(self,L,mid);
	};
	F=psum[l-1],sol(sol,l,mid);
	F=ssum[r+1],sol(sol,mid+1,r);
	poly lef=pre[l-1],rig=suf[r+1];
	F(i,l,mid)lef=ins(lef,i);
	F(i,mid+1,r)rig=ins(rig,i);
	dp[l-1]=lef,dp[r+1]=rig;
	F(i,l,mid)dp[i]=mrg(dp[i-1],f[i]);
	dF(i,r,mid+1)dp[i]=mrg(dp[i+1],f[i]);
	for(auto&[ql,qr,coef,id]:qu[o]){
		int val=qry(dp[ql],dp[qr]);
		if(coef<0)dec(ans[id],val);
		else inc(ans[id],val);
	}
}
void solve(){
	cin>>n>>m>>zsy;
	F(i,1,n)cin>>a[i]>>b[i];
	init(psum[0]),init(ssum[n+1]);
	F(i,1,n)psum[i]=ins(psum[i-1],i);
	dF(i,n,1)ssum[i]=ins(ssum[i+1],i);
	init1(pre[0]),init1(suf[n+1]);
	F(i,1,n)pre[i]=mrg(ins(pre[i-1],i),psum[i-1]);
	dF(i,n,1)suf[i]=mrg(ins(suf[i+1],i),ssum[i+1]);
	F(i,1,zsy){
		int l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2;
		ins_query(1,1,n,r1,l2,1,i);
		ins_query(1,1,n,r1,r2+1,-1,i);
		ins_query(1,1,n,l1-1,l2,-1,i);
		ins_query(1,1,n,l1-1,r2+1,1,i);
	}
	dfs(1,1,n);
	F(i,1,zsy)cout<<ans[i]<<'\n';
}