题目描述
共有m部电影，编号为1~m，第i部电影的好看值为w[i]。在n天之中（从1~n编号）每天会放映一部电影，第i天放映的是第f[i]部。你可以选择l,r(1<=l<=r<=n)，并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。
输入格式
输出格式
输出观看且仅观看过一次的电影的好看值的总和的最大值。
输入输出样例
输入 #1
9 4 2 3 1 1 4 1 2 4 1 5 3 6 6
输出 #1
15
说明/提示
共有m部电影，编号为1~m，第i部电影的好看值为w[i]。
在n天之中（从1~n编号）每天会放映一部电影，第i天放映的是第f[i]部。
你可以选择l,r(1<=l<=r<=n)，并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。
有两种写法：
https://www.luogu.org/problemnew/solution/P3582
求最大连续子段 保证相同的场次最多只有2个 前一个为-w 后一个为w
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// const int N=2e6+10; ll t[N<<2],lmax[N<<2],rmax[N<<2],sum[N<<2]; void up(int pos) { sum[pos]=sum[pos<<1]+sum[pos<<1|1]; lmax[pos]=max(lmax[pos<<1],sum[pos<<1]+lmax[pos<<1|1]); rmax[pos]=max(rmax[pos<<1|1],sum[pos<<1|1]+rmax[pos<<1]); t[pos]=max(max(t[pos<<1],t[pos<<1|1]),rmax[pos<<1]+lmax[pos<<1|1]); } void upnode(int x,int v,int l,int r,int pos) { if(l==r){sum[pos]=lmax[pos]=rmax[pos]=t[pos]=1ll*v;return;} int m=(l+r)>>1; if(x<=m)upnode(x,v,l,m,pos<<1); else upnode(x,v,m+1,r,pos<<1|1); up(pos); } int n,m,w[N],f[N],fi[N],se[N]; int main() { scanf("%d%d",&n,&m); rep(i,1,n)scanf("%d",&f[i]); rep(i,1,m)scanf("%d",&w[i]); ll ans=0; rep(i,1,n) { if(!fi[f[i]])fi[f[i]]=i,upnode(i,w[f[i]],1,n,1); else if(!se[f[i]])se[f[i]]=i,upnode(fi[f[i]],-w[f[i]],1,n,1),upnode(i,w[f[i]],1,n,1); else upnode(fi[f[i]],0,1,n,1),upnode(se[f[i]],-w[f[i]],1,n,1),upnode(i,w[f[i]],1,n,1),fi[f[i]]=se[f[i]],se[f[i]]=i; ans=max(ans,t[1]); } cout<<ans; return 0; }