【传送门：】

---

简要题意：

　　共有m部电影，编号为1到m，第i部电影的好看值为w[i]。

　　在n天之中（从1到n编号）每天会放映一部电影，第i天放映的是第f[i]部

　　你可以选择l,r(1<=l<=r<=n)，并观看第l,l+1,…,r天内所有的电影

　　如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值

　　所以你希望最大化观看且仅观看过一次的电影的好看值的总和

---

题解：

　　线段树

　　next[i]表示与第i天播放同一部电影的下一天，如果没有则为n+1（待会解释）

　　因为如果l,r之间有相同电影，那么这部电影则没有好看值，所以第i天的电影的好看值只贡献于第i天到第next[i]-1天（所以为什么上一步next[i]=n+1）

　　然后枚举l，用线段树维护每一天的好看总值

　　枚举时，先把l到next[l]-1减掉l位置电影的好看值，然后如果next[next[l]]!=0，就把next[l]到next[next[l]]-1加上减掉l位置电影的好看值，然后l++，然后求出l到n的最大值，然后维护整体最大值即可

　　注意加long long

---

参考代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long LL;struct node{    int l,r,lc,rc;LL c,lazy;}tr[2100000];int trlen;void bt(int l,int r){    int now=++trlen;    tr[now].l=l;tr[now].r=r;tr[now].c=tr[now].lazy=0;    tr[now].lc=tr[now].rc=-1;    if(l
          
           mid) change(rc,l,r,c); else change(lc,l,mid,c),change(rc,mid+1,r,c); tr[now].c=max(tr[lc].c,tr[rc].c);}LL findc(int now,int l,int r){ if(tr[now].l==l&&tr[now].r==r) return tr[now].c; int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2; if(r<=mid) return findc(lc,l,r); else if(l>mid) return findc(rc,l,r); else return max(findc(lc,l,mid),findc(rc,mid+1,r));}int t[1100000],next[1100000];int ft[1100000],f[1100000];LL w[1100000];int main(){ int n,m; scanf("%d%d",&n,&m); memset(t,0,sizeof(t)); memset(next,0,sizeof(next)); memset(ft,0,sizeof(ft)); for(int i=1;i<=n;i++) { scanf("%d",&f[i]); if(t[f[i]]==0) ft[f[i]]=i; next[t[f[i]]]=i; t[f[i]]=i; } for(int i=1;i<=n;i++) if(next[i]==0) next[i]=n+1; for(int i=1;i<=m;i++) scanf("%lld",&w[i]); trlen=0;bt(1,n); for(int i=1;i<=m;i++) if(ft[i]!=0) change(1,ft[i],next[ft[i]]-1,w[i]); LL ans=findc(1,1,n); int l=1; while(l