题解 P3582 【[POI2015]KIN】

## ~~不说废话~~…… 这道题目我们可以考虑先记录每种电影上一次开播时间和下一次开播时间(即以下代码中的$last$数组和$nxt$数组)，然后对于每种电影，我们可以先处理中它是否播放过对后面区间的影响情况，然后再对$n$个时间点分别考虑，我们可以枚举左端点，然后根据左端点电影的播放情况就可以确定它可以影响到的最右端点，然后不断更新，更新过程中记录最大值，最后那个最大值即为答案。 ```cpp #include<cstdio> #include<algorithm> #include<cctype> #define ll long long #define maxn 1000007 #define ls rt<<1 #define rs rt<<1|1 using namespace std; int n,m,f[maxn],nxt[maxn],last[maxn],a[maxn]; ll ans; inline int qread() { //快读，不解释…… char c=getchar();int num=0,f=1; for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f; } struct Tree { ll maxx,lazy; }tree[maxn<<2]; inline void pushdown(int rt) { //下放lazy标记。 if(tree[rt].lazy) { tree[ls].lazy+=tree[rt].lazy; tree[rs].lazy+=tree[rt].lazy; tree[rs].maxx+=tree[rt].lazy; tree[ls].maxx+=tree[rt].lazy; tree[rt].lazy=0; } } void modify(int rt,int l,int r,int L,int R,int val) { //区间修改，用于后面的更新。 if(L>r||R<l) return; if(L<=l&&r<=R) { tree[rt].lazy+=val; tree[rt].maxx+=val; return; } pushdown(rt); int mid=(l+r)>>1; modify(ls,l,mid,L,R,val),modify(rs,mid+1,r,L,R,val); tree[rt].maxx=max(tree[ls].maxx,tree[rs].maxx); } int main() { n=qread(),m=qread(); for(int i=1;i<=n;++i) f[i]=qread(); for(int i=1;i<=m;++i) a[i]=qread(); for(int i=n;i>=1;--i) nxt[i]=last[f[i]],last[f[i]]=i; //处理出nxt和last数组。 for(int i=1;i<=m;++i) { if(last[i]) { //如果这个电影已经播放过。 int zrj=nxt[last[i]]; if(zrj) modify(1,1,n,last[i],zrj-1,a[i]); //如果这不是最后一次播放这个电影，那么可以影响到的最右端点是nxt[last[i]]-1，然后last[i]就是左端点，也是第一次看，所以在这个区间加上这个电影的价值。 else modify(1,1,n,last[i],n,a[i]); //如果是最后一次，那么它将一直影响到最后。 } } for(int i=1;i<=n;++i) { ans=max(ans,tree[1].maxx); //每次更新一下最大值。 int zrj=nxt[i]; if(zrj) { //如果第二次播放。 modify(1,1,n,i,zrj-1,-a[f[i]]); //在这次和之后的一次的区间上价值减去这个电影的价值，因为相同电影看了价值为0。 if(nxt[zrj]) modify(1,1,n,zrj,nxt[zrj]-1,a[f[i]]); //第二次和第三次之间加上这个电影的价值(因为是以第二次为左端点，只看了一次)。 else modify(1,1,n,zrj,n,a[f[i]]); //不然就把第二次之后的加上这个价值。 } else modify(1,1,n,i,n,-a[f[i]]); //没有第二次播放，就从当前时间开始一直到最后，减去这个价值。 } printf("%lld\n",ans); return 0; } ```