题解 P5455 【[THUPC2018]弗雷兹的玩具商店】

· · 题解

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

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

首先每次询问就是完全背包。可以 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);
        }
    }
}