Description
共有m部电影，编号为1~m，第i部电影的好看值为w[i]。在n天之中（从1~n编号）每天会放映一部电影，第i天放映的是第f[i]部。你可以选择l,r(1<=l<=r<=n)，并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。
输入输出格式
Input
第一行两个整数n,m(1<=m<=n<=1000000)。第二行包含n个整数f[1],f[2],…,fn。第三行包含m个整数w[1],w[2],…,wm。
Output
输出观看且仅观看过一次的电影的好看值的总和的最大值。
Solution
预处理出下一个于某天放同样电影的日子，然后从右往左枚举L，线段树中i位置存的数表示选当前L到i位置的所有电影的贡献，然后区间加减来维护即可
代码:
#include<cstdio>
#include<algorithm>
using namespace std;template<typename T>inline void read(T &x){T f=1;char ch=getchar();for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';x*=f;
}typedef long long LL;
const int maxn=1000010;
struct Segment_Tree{#define lc x<<1#define rc x<<1|1int L[maxn<<2],R[maxn<<2];LL mx[maxn<<2],add[maxn<<2];void Build(int x,int l,int r){mx[x]=add[x]=0;if((L[x]=l)==(R[x]=r))return;int mid=(l+r)>>1;Build(lc,l,mid);Build(rc,mid+1,r);}void pushdown(int x){if(add[x]){mx[lc]+=add[x];add[lc]+=add[x];mx[rc]+=add[x];add[rc]+=add[x];add[x]=0;}}void Add(int x,int l,int r,LL val){if(L[x]>=l&&R[x]<=r)return mx[x]+=val,add[x]+=val,void();pushdown(x);int mid=(L[x]+R[x])>>1;if(l<=mid)Add(lc,l,r,val);if(r>mid)Add(rc,l,r,val);mx[x]=max(mx[lc],mx[rc]);}LL Query(int x,int l,int r){if(L[x]>=l&&R[x]<=r)return mx[x];pushdown(x);int mid=(L[x]+R[x])>>1;LL ans=0;if(l<=mid)ans=max(ans,Query(lc,l,r));if(r>mid)ans=max(ans,Query(rc,l,r));return ans;}
}tree;
int n,m,f[maxn],w[maxn],suf[maxn],nxt[maxn];
LL ans;int main(){read(n);read(m);for(int i=1;i<=n;i++)read(f[i]);for(int i=1;i<=m;i++)read(w[i]);for(int i=n;i>=1;i--){if(!nxt[f[i]])suf[i]=n+1;else suf[i]=nxt[f[i]];nxt[f[i]]=i;}suf[n+1]=n+1;tree.Build(1,1,n);for(int i=n;i>=1;i--){tree.Add(1,i,suf[i]-1,w[f[i]]);if(suf[i]<=n)tree.Add(1,suf[i],suf[suf[i]]-1,-w[f[i]]);ans=max(ans,tree.Query(1,i,n));}printf("%lld\n",ans);return 0;
}