最近状态有点颓，刷刷水题找找自信。
首先每次询问就是完全背包。可以 $O(m^2)$。
由于每个物品都可以用无数次，所以对于价格相同的物品，我们只用考虑愉悦度最高的。
直接上线段树。$val[i]$ 表示这个区间中价格为 $i$ 的物品中最大的愉悦度。如果没有这样的物品就是 -INF。
询问就把这个区间的所有 $val$ 取出来，做个完全背包就好了。
两种修改操作用个标记随便搞搞。分别是区间的每个数组平移，和区间加。
复杂度 $O(nmlog n+q(m^2+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 ",s1,s2); } } }