自动搬运

查看原文

来自洛谷，原作者为

	AThousandSuns Simultaneous release!

搬运于2025-08-24 22:10:55，当前版本为作者最后更新于2019-07-13 10:32:19，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

在我的博客园食用效果更佳：点这里

最近状态有点颓，刷刷水题找找自信。

首先每次询问就是完全背包。可以 $O(m^2)$。

由于每个物品都可以用无数次，所以对于价格相同的物品，我们只用考虑愉悦度最高的。

直接上线段树。$val[i]$ 表示这个区间中价格为 $i$ 的物品中最大的愉悦度。如果没有这样的物品就是 -INF。

询问就把这个区间的所有 $val$ 取出来，做个完全背包就好了。

两种修改操作用个标记随便搞搞。分别是区间的每个数组平移，和区间加。

复杂度 $O(nm\log n+q(m^2+m\log n))$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200020,INF=1e9;
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
	char ch=getchar();int x=0,f=0;
	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return f?-x:x;
}
int n,m,q,c[maxn],v[maxn],tmp[66],ctag[maxn*4],vtag[maxn*4];
ll f[66];
struct node{
	int val[66];
	bool vis[66];
	node operator+(const node &nd)const{
		node ans;
		ans.val[0]=-INF;
		FOR(i,1,m) ans.val[i]=max(val[i],nd.val[i]);
		return ans;
	}
}seg[maxn*4];
inline void setc(int o,int v){
	FOR(i,1,m) tmp[(i+v-1)%m+1]=seg[o].val[i];
	FOR(i,1,m) seg[o].val[i]=tmp[i];
	ctag[o]=(ctag[o]+v)%m;
}
inline void setv(int o,int v){
	FOR(i,1,m) seg[o].val[i]+=v;
	vtag[o]+=v;
}
inline void pushdown(int o){
	if(ctag[o]){
		setc(o<<1,ctag[o]);
		setc(o<<1|1,ctag[o]);
		ctag[o]=0;
	}
	if(vtag[o]){
		setv(o<<1,vtag[o]);
		setv(o<<1|1,vtag[o]);
		vtag[o]=0;
	}
}
void build(int o,int l,int r){
	if(l==r){
		FOR(i,0,m) seg[o].val[i]=-INF;
		seg[o].val[c[l]]=v[l];
		return;
	}
	int mid=(l+r)>>1;
	build(lson);build(rson);
	seg[o]=seg[o<<1]+seg[o<<1|1];
}
void updatec(int o,int l,int r,int ql,int qr,int v){
	if(l>=ql && r<=qr) return void(setc(o,v));
	pushdown(o);
	int mid=(l+r)>>1;
	if(mid>=ql) updatec(lson,ql,qr,v);
	if(mid<qr) updatec(rson,ql,qr,v);
	seg[o]=seg[o<<1]+seg[o<<1|1];
}
void updatev(int o,int l,int r,int ql,int qr,int v){
	if(l>=ql && r<=qr) return void(setv(o,v));
	pushdown(o);
	int mid=(l+r)>>1;
	if(mid>=ql) updatev(lson,ql,qr,v);
	if(mid<qr) updatev(rson,ql,qr,v);
	seg[o]=seg[o<<1]+seg[o<<1|1];
}
node query(int o,int l,int r,int ql,int qr){
	if(l>=ql && r<=qr) return seg[o];
	pushdown(o);
	int mid=(l+r)>>1;
	if(mid<ql) return query(rson,ql,qr);
	if(mid>=qr) return query(lson,ql,qr);
	return query(lson,ql,qr)+query(rson,ql,qr);
}
int main(){
	n=read();m=read();
	FOR(i,1,n) c[i]=read();
	FOR(i,1,n) v[i]=read();
	build(1,1,n);
	q=read();
	while(q--){
		int op=read(),l=read(),r=read();
		if(op==1) updatec(1,1,n,l,r,read());
		else if(op==2) updatev(1,1,n,l,r,read());
		else{
			node ans=query(1,1,n,l,r);
			FOR(i,0,m) f[i]=0;
			FOR(i,1,m) FOR(j,0,i) f[i]=max(f[i],f[i-j]+max(0,ans.val[j]));
			ll s1=0,s2=0;
			FOR(i,1,m) s1+=f[i],s2^=f[i];
			printf("%lld %lld\n",s1,s2);
		}
	}
}