共有m部电影，编号为1~m，第i部电影的好看值为w[i]。
在n天之中（从1~n编号）每天会放映一部电影，第i天放映的是第f[i]部。
你可以选择l,r(1<=l<=r<=n)，并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。
15
样例解释：
观看第2,3,4,5,6,7天内放映的电影，其中看且仅看过一次的电影的编号为2,3,4。
思路{
和HH的项链树状数组做法的思想类似.
有重复的颜色记录出$ Nxt [ i ] $为下一个和$ i $ 颜色相同的位置.
那么从左往右扫区间右端点,相当于一个取$ Max $的操作.用线段树维护.
考虑更改,删除当前点{
删除区间[ i , Nxt [ i ] ] 贡献,
新增区间 [ Nxt [ i ] ,Nxt [ i ] ] 贡献
}
用线段树搞就可以了.
}
#include<bits/stdc++.h>
#define il inline
#define RG register
#define ll long long
#define db double
#define N 1000010
using namespace std;
int w[N],f[N],n,m,last[N],nxt[N],fir[N];
namespace Tree{
ll Max[N*4],lazy[N*4];
#define rs ((o<<1)|1)
#define ls (o<<1)
#define mid ((l+r)>>1)
void up(int o){
Max[o]=max(Max[rs],Max[ls]);
}
void down(int o){
if(lazy[o]){
Max[rs]+=lazy[o];lazy[rs]+=lazy[o];
Max[ls]+=lazy[o];lazy[ls]+=lazy[o];
lazy[o]=0;
}
}
void Insert(int o,int l,int r,int L,int R,ll num){
if(l!=r)down(o);
if(l>=L&&r<=R){Max[o]+=num,lazy[o]+=num;return;}
if(mid<L)Insert(rs,mid+1,r,L,R,num);
else if(mid>=R)Insert(ls,l,mid,L,R,num);
else Insert(rs,mid+1,r,mid+1,R,num),Insert(ls,l,mid,L,mid,num);
up(o);
}
ll Query(int o,int l,int r,int L,int R){
if(l!=r)down(o);
if(l>=L&&r<=R)return Max[o];
if(mid<L)return Query(rs,mid+1,r,L,R);
else if(mid>=R)return Query(ls,l,mid,L,R);
else return max(Query(rs,mid+1,r,L,R),Query(ls,l,mid,L,R));
}
}
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=1;i<=n;++i){
if(last[f[i]])nxt[last[f[i]]]=i;
last[f[i]]=i;
}
memset(last,0,sizeof(last));
for(int i=n;i;i--){
if(last[f[i]])fir[last[f[i]]]=i;
last[f[i]]=i;
}
for(int i=1;i<=n;++i)
if(!fir[i]){
if(nxt[i])Tree::Insert(1,1,n,i,nxt[i]-1,w[f[i]]);
else Tree::Insert(1,1,n,i,n,w[f[i]]);
}
ll Ans(0);
for(int i=1;i<=n;++i){
Ans=max(Ans,Tree::Query(1,1,n,i,n));
if(nxt[i]){
Tree::Insert(1,1,n,i,nxt[i]-1,-w[f[i]]);
if(nxt[nxt[i]])Tree::Insert(1,1,n,nxt[i],nxt[nxt[i]]-1,w[f[i]]);
else Tree::Insert(1,1,n,nxt[i],n,w[f[i]]);
}
else Tree::Insert(1,1,n,i,n,-w[f[i]]);
}cout<<Ans;
return 0;
}
原文：http://www.cnblogs.com/zzmmm/p/7512973.html