共有m部电影，编号为1~m，第i部电影的好看值为w[i]。
在n天之中（从1~n编号）每天会放映一部电影，第i天放映的是第f[i]部。
你可以选择l,r(1<=l<=r<=n)，并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。
这道题是一道很经典的线段树题目了；
题目没有给定询问区间，如果给定询问区间的话那就是用类似采花的做法就行了；
我们考虑从后往前枚举左端点，那么我们相当于只需要查询右端点的最值；
我们考虑记nxt[i]，表示下一个跟i同颜色的位置，那么从后往前枚举左端点的话，
右端点在[i,nxt[i]-1]间的贡献会+w,然后我们需要求的是仅出现一次的，
那么原来在[nxt[i],nxt[nxt[i]]-1]的右端点的贡献需要-w，至于[nxt[nxt[i]],nxt[nxt[nxt[i]]]]的右端点必定在之前处理过了不用管；
所以我们相当于区间修改和查询最大值即可，用线段树来实现；
//MADE BY QT666
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define lson x<<1
#define rson x<<1|1
using namespace std;
typedef long long ll;
const int N=1500050;
int n,m,w[N],f[N],nxt[N],last[N];
ll tr[N*4],lazy[N*4];
void update(int x,int l,int r,int xl,int xr,int v){
if(xl>xr) return;
if(xl<=l&&r<=xr){
tr[x]+=v;lazy[x]+=v;return;
}
int mid=(l+r)>>1;
if(xr<=mid) update(lson,l,mid,xl,xr,v);
else if(xl>mid) update(rson,mid+1,r,xl,xr,v);
else update(lson,l,mid,xl,mid,v),update(rson,mid+1,r,mid+1,xr,v);
tr[x]=max(tr[lson],tr[rson])+lazy[x];
}
ll query(int x,int l,int r,int xl,int xr,int la){
if(xl<=l&&r<=xr) return tr[x]+la;
int mid=(l+r)>>1;la+=lazy[x];
if(xr<=mid) return query(lson,l,mid,xl,xr,la);
else if(xl>mid) return query(rson,mid+1,r,xl,xr,la);
else return max(query(lson,l,mid,xl,mid,la),query(rson,mid+1,r,mid+1,xr,la));
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&f[i]);
for(int i=1;i<=m;i++) scanf("%d",&w[i]);
for(int i=n;i;i--) nxt[i]=last[f[i]],last[f[i]]=i;
ll ans=0;
for(int i=n;i;i--){
if(!nxt[i]) update(1,1,n,i,n,w[f[i]]);
else {
update(1,1,n,i,nxt[i]-1,w[f[i]]);
if(nxt[nxt[i]]) update(1,1,n,nxt[i],nxt[nxt[i]]-1,-w[f[i]]);
else update(1,1,n,nxt[i],n,-w[f[i]]);
}
ans=max(ans,query(1,1,n,i,n,0));
}
printf("%lld\n",ans);
return 0;
}
原文：http://www.cnblogs.com/qt666/p/7622813.html