【BZOJ 3747】[POI2015] Kinoman

Qizy Segment Tree, 数据结构, 解题报告

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3747
数据生成器：http://paste.ubuntu.com/15389317/

这题真的是吼啊！来，大家跟我一起喊：“POI赛高！”

考虑固定左端点：
对于每一个元素，第一次出现的位置权值为正
其第二次出现的权值为负，第三次及以后的权值为0
这时不难发现，其实就是求前缀和的最大值
这个O(n)的暴力大家都会

现在来考虑将左端点向右移动1个位置
不难发现是对之前的前缀和数组进行区间加减，并且求最值
这样的话，就可以用线段树来维护辣！

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<set>
#define LL long long
using namespace std;

const int MAXN = 2000000 + 9;

int n,m,t[MAXN/2],w[MAXN/2],aft[MAXN/2],vis[MAXN/2];
LL buf[MAXN/2],vout;

namespace SegmentTree{
	int root, cnt, ls[MAXN], rs[MAXN], ch[MAXN][2];
	LL mx[MAXN], tag[MAXN];
	
	inline void maintain(int w){mx[w] = max(mx[ch[w][0]], mx[ch[w][1]]);}
	inline void pushdown(int w){
		if (!ch[w][0] || !tag[w]) return;
		else {
			for (int i=0; i<2; i++) tag[ch[w][i]] += tag[w], mx[ch[w][i]] += tag[w];		
			tag[w] = 0;
		} 
	}
	
	void build(int &w, int l, int r){
		w = ++cnt; ls[w] = l; rs[w] = r;
		if (l == r) mx[w] = buf[l];
		else {
			int mid = (l + r + 1) / 2;
			build(ch[w][0], l, mid-1);
			build(ch[w][1], mid, r);
			maintain(w);
		}
	}
	
	void modify(int w, int l, int r, int delta){
		if (l <= ls[w] && rs[w] <= r) mx[w] += (LL)delta, tag[w] += delta;
		else {
			pushdown(w);
			int mid = (ls[w] + rs[w] + 1) / 2;
			if (l < mid) modify(ch[w][0], l, r, delta);
			if (mid <= r) modify(ch[w][1], l, r, delta);
			maintain(w);
		}
	}void modify(int l, int r, int delta){modify(root, l, r, delta);} 
	
	LL ans_tmp;
	void query(int w, int l, int r){
		if (l <= ls[w] && rs[w] <= r) ans_tmp = max(ans_tmp, mx[w]);
		else {
			pushdown(w);
			int mid = (ls[w] + rs[w] + 1) / 2;
			if (l < mid) query(ch[w][0], l, r);
			if (r >= mid) query(ch[w][1], l, r);
		}
	} inline LL query(int l, int r) {ans_tmp=0;query(root, l, r);return ans_tmp;}
};

void init(){
	set<int> Q;
	for (int i=1;i<=n;i++){
		buf[i] = buf[i-1];
		if (!Q.count(t[i])) buf[i] += (LL)w[t[i]], Q.insert(t[i]);
		else if (!vis[t[i]]) buf[i] -= (LL)w[t[i]], vis[t[i]] = 1;
	}
}

int main(){
	using namespace SegmentTree;
	cin>>n>>m;
	for (int i=1;i<=n;i++) scanf("%d",&t[i]);
	for (int i=1;i<=m;i++) scanf("%d",&w[i]);
	for (int i=n;i;i--) {if (vis[t[i]]) aft[i] = vis[t[i]]; vis[t[i]] = i;}
	for (int i=1;i<=m;i++) vis[i] = 0;
	init(); build(root, 1, n);
	
	vout = 0;
	for (int i=1;i<=n;i++){
		vout = max(vout, query(i, n));
		modify(i, (aft[i])?aft[i]-1:n, -w[t[i]]);
		if (aft[i]) modify(aft[i], (aft[aft[i]])?aft[aft[i]]-1:n, w[t[i]]);
	} printf("%lld",vout);
	
	return 0;
}

13 thoughts to “【BZOJ 3747】[POI2015] Kinoman”

  1. 822347 812901You produced some respectable points there. I looked on the internet for the issue and found many people will go along with together with your internet site. 787678

    Reply

  5. 996807 962791Thanks for some other wonderful post. Where else could just anyone get that type of information in such an ideal indicates of writing? Ive a presentation next week, and Im at the search for such info. 896564

    Reply

  7. 625449 518669Most beneficial gentleman speeches and toasts are created to enliven supply accolade up towards the wedding couple. Newbie audio system the attention of loud crowds really should always consider typically the wonderful norm off presentation, which is their private. greatest man speaches 854835

    Reply

  10. 120553 195427Why didnt I think about this? I hear exactly what youre saying and Im so happy that I came across your blog. You actually know what youre talking about, and you created me feel like I ought to learn a lot more about this. Thanks for this; Im officially a huge fan of your weblog 575531

    Reply

  13. 483260 87734As I web internet site possessor I believe the content material matter here is rattling magnificent , appreciate it for your hard work. You need to keep it up forever! Finest of luck. 121596

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *