标签：线段树
题目
Description
共有m部电影，编号为1~m，第i部电影的好看值为w[i]。
在n天之中（从1~n编号）每天会放映一部电影，第i天放映的是第f[i]部。
你可以选择\(l,r(1\leq l\leq r\leq n)\)，并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。
所以你希望最大化观看且仅观看过一次的电影的好看值的总和。
Input
第一行两个整数\(n,m(1\leq m\leq n\leq 1000000)\)。
第二行包含n个整数\(f[1],f[2],…,f[n](1\leq f[i]\leq m)\)。
第三行包含m个整数\(w[1],w[2],…,w[m](1\leq w[j]\leq 1000000)\)。
Output
输出观看且仅观看过一次的电影的好看值的总和的最大值。
Sample Input
9 4
2 3 1 1 4 1 2 4 1
5 3 6 6
Sample Output
15
样例解释
观看第2,3,4,5,6,7天内放映的电影，其中看且仅看过一次的电影的编号为2,3,4。
分析
pre[i]表示与当前位置上的数字相同的前一个数的下标
枚举右端点，每次假如一个数，那么修改\(pre[i]+1->i\)这段位置上的权值\(+val[i]\)
\(pre[pre[i]] + 1->pre[i]\)这段位置的权值\(-val[i]\)，然后查询\([1, i]\)的最大值即可
不知道这题有没有大爷能给出\(O(n)\)的做法，线段树这么大的常数跑1e6感觉有点慢……
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//**********head by yjjr**********
#define mid ((l+r)>>1)
#define lson (x<<1)
#define rson (x<<1|1)
const int maxn=1e6+6;
int n,m,a[maxn],b[maxn],pre[maxn],last[maxn];ll ans=0;
struct Seg_Tree{ll val,flag;}tree[maxn<<2];
void pushup(int x){tree[x].val=max(tree[lson].val,tree[rson].val);}
void pushdown(int x){
if(tree[x].flag){
tree[lson].val+=tree[x].flag;tree[lson].flag+=tree[x].flag;
tree[rson].val+=tree[x].flag;tree[rson].flag+=tree[x].flag;
tree[x].flag=0;
}
}
void modify(int x,int l,int r,int ql,int qr,int val){
if(ql<=l&&r<=qr){
tree[x].val+=val;
tree[x].flag+=val;
return;
}
pushdown(x);
if(ql<=mid)modify(lson,l,mid,ql,qr,val);
if(qr>mid)modify(rson,mid+1,r,ql,qr,val);
pushup(x);
}
inline ll query(int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return tree[x].val;
pushdown(x);
ll re=0;
if(ql<=mid)re=max(re,query(lson,l,mid,ql,qr));
if(qr>mid)re=max(re,query(rson,mid+1,r,ql,qr));
return re;
}
int main()
{
n=read(),m=read();
rep(i,1,n)a[i]=read();
rep(i,1,m)b[i]=read();
rep(i,1,n)pre[i]=last[a[i]],last[a[i]]=i;
rep(i,1,n){
modify(1,1,n,pre[i]+1,i,b[a[i]]);
if(pre[i])modify(1,1,n,pre[pre[i]]+1,pre[i],-b[a[i]]);
ans=max(ans,query(1,1,n,1,i));
}
cout<<ans<<endl;
return 0;
}
