题目大意：
给你一个长度为n的数列f，f中共有m种不同的数，每种数都有一个权值w[i]。
你可以选定一个f中的区间，定义区间的权值为这一区间只出现一次的数的权值和。
问权值最大的区间的权值是多少？
思路：
对于f中的每一个位置i，找到下一个和它相同数字的位置next[i]。
从左到右枚举区间左端点，线段树维护选取每个右端点的最大值。
去除当前左端点对答案的影响时，只需要把i~next[i]-1这一段减去w[f[i]]，然后把next[i]~next[next[i]]-1加上w[f[i]]即可。
1 #include<cstdio> 2 #include<cctype> 3 #include<algorithm> 4 typedef long long int64; 5 inline int getint() { 6 register char ch; 7 while(!isdigit(ch=getchar())); 8 register int x=ch^'0'; 9 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 10 return x; 11 } 12 const int N=1000001,M=1000001; 13 int f[N],w[M],next[N],pos[M]; 14 class SegmentTree { 15 #define _left <<1 16 #define _right <<1|1 17 private: 18 int64 max[N<<2],tag[N<<2]; 19 void push_down(const int &p) { 20 tag[p _left]+=tag[p]; 21 tag[p _right]+=tag[p]; 22 max[p _left]+=tag[p]; 23 max[p _right]+=tag[p]; 24 tag[p]=0; 25 } 26 void push_up(const int &p) { 27 max[p]=std::max(max[p _left],max[p _right]); 28 } 29 public: 30 void modify(const int &p,const int &b,const int &e,const int &l,const int &r,const int &x) { 31 if(b==l&&e==r) { 32 tag[p]+=x; 33 max[p]+=x; 34 return; 35 } 36 push_down(p); 37 const int mid=(b+e)>>1; 38 if(l<=mid) modify(p _left,b,mid,l,std::min(mid,r),x); 39 if(r>mid) modify(p _right,mid+1,e,std::max(mid+1,l),r,x); 40 push_up(p); 41 } 42 int64 query() const { 43 return max[1]; 44 } 45 #undef _left 46 #undef _right 47 }; 48 SegmentTree t; 49 int main() { 50 const int n=getint(),m=getint(); 51 for(register int i=1;i<=n;i++) { 52 f[i]=getint(); 53 } 54 for(register int i=1;i<=m;i++) { 55 w[i]=getint(); 56 pos[i]=n+1; 57 } 58 for(register int i=n;i;i--) { 59 next[i]=pos[f[i]]; 60 pos[f[i]]=i; 61 } 62 for(register int i=1;i<=m;i++) { 63 t.modify(1,1,n,pos[i],next[pos[i]]-1,w[i]); 64 } 65 int64 ans=0; 66 for(register int i=1;i<=n;i++) { 67 ans=std::max(ans,t.query()); 68 t.modify(1,1,n,i,next[i]-1,-w[f[i]]); 69 t.modify(1,1,n,next[i],next[next[i]]-1,w[f[i]]); 70 } 71 printf("%lld ",ans); 72 return 0; 73 }