Bzoj3747 [poi2015]kinoman

用线段树解决区间问题

阅读全文大概需要 1分钟
本文总阅读量
Posted by yjjr's blog on April 10, 2018

标签:线段树

题目

题目传送门

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;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr