BZOJ 3747: [POI2015]Kinoman 【线段树】

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],…,f[n](1<=f[i]<=m)。

第三行包含m个整数w[1],w[2],…,w[m](1<=w[j]<=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。

思路：很神的题，一直在想O（n）的算法然后没有结果然后查了解题想了线段树的思路才想出来了

枚举区间左端点然后线段树可以维护以这个点为左端点的最大值然后就可以了

#include<cstdio>

#include<string.h>

#include<algorithm>

#define maxn 1000000

#define ll long long

using namespace std;

int a[maxn],w[maxn],nex[maxn],las[maxn];

ll lazy[maxn*4],tree[maxn*4];

void add(int node,int l,int r,int ql,int qr,ll w)

{

if(ql<=l&&r<=qr){lazy[node]+=w;return;}

int mid=(l+r)>>1;

if(lazy[node]!=0){

tree[node]+=lazy[node];lazy[node*2]+=lazy[node];

lazy[node*2+1]+=lazy[node];lazy[node]=0;

}

if(ql<=mid)add(node*2,l,mid,ql,qr,w);

if(qr>mid)add(node*2+1,mid+1,r,ql,qr,w);

tree[node]=max(tree[node*2]+lazy[node*2],tree[node*2+1]+lazy[node*2+1]);

}

ll query(int node,int l,int r,int ql,int qr){

ll ans=0;

if(lazy[node]!=0){

tree[node]+=lazy[node];lazy[node*2]+=lazy[node];

lazy[node*2+1]+=lazy[node];lazy[node]=0;

}

if(ql<=l&&r<=qr)return tree[node];int mid=(l+r)>>1;

if(ql<=mid)ans=max(ans,query(node*2,l,mid,ql,qr));

if(mid<qr)ans=max(ans,query(node*2+1,mid+1,r,ql,qr));

return ans;

}

int main(){

int n,m;ll ans=0;scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)scanf("%d",&a[n-i+1]);for(int i=1;i<=m;i++)scanf("%d",&w[i]);

for(int i=1;i<=n;i++)nex[i]=las[a[i]],las[a[i]]=i;

for(int i=1;i<=n;i++){

add(1,1,n+1,nex[i]+1,i+1,w[a[i]]);

if(nex[i]!=0)add(1,1,n+1,nex[nex[i]]+1,nex[i]+1,-w[a[i]]);

ans=max(ans,query(1,1,n+1,1,i+1));

}

printf("%lld\n",ans);return 0;

}

巴特西

BZOJ 3747: [POI2015]Kinoman 【线段树】

最新文章

热门文章