BZOJ 3747 Kinoman

发表于 | 更新于

Link

Solution

比较常见的技巧吧。 枚举右端点，在线段树的每个节点pp维护序列中点pp到右端点的和，然后就是一个区间修改和区间查询了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include "lucida"
const int MAXN=1000000+11;
using std::max;
namespace _SegTree_ {
	const int SIZE=MAXN<<2;
	struct Node {
		Node *son[2];
		int64 maxv,add;
		Node();
		void Down();
		void Up();
		void Add(int64);
		void *operator new(size_t);
	}*null=new Node;
	Node::Node(){
		maxv=add=0;
		son[0]=son[1]=null;
	}
	void *Node::operator new(size_t) {
		static Node *Pool=(Node*)malloc(SIZE*sizeof(Node)),*Me=Pool;
		return Me++;
	}
	void Node::Down() {
		if(add) {
			son[0]->Add(add);
			son[1]->Add(add);
			add=0;
		}
	}
	void Node::Up() {
		maxv=max(son[0]->maxv,son[1]->maxv);
	}
	void Node::Add(int64 adv) {
		if(this==null) 
			return;
		add+=adv;
		maxv+=adv;
	}
	struct SegTree {
		Node *root;int L,R;
		SegTree(){}
		SegTree(int,int);
		void Build(Node*&,int,int);
		void Edit(Node*,int,int,int,int,int64);
		void Edit(int,int,int64);
		int64 Access(Node*,int,int,int,int);
		int64 Access(int,int);
	};
	SegTree::SegTree(int L,int R):L(L),R(R) {
		root=null;
		Build(root,L,R);
	}
	void SegTree::Build(Node *&pos,int L,int R) {
		pos=new Node;
		if(L!=R) {
			int Mid=(L+R)>>1;
			Build(pos->son[0],L,Mid);
			Build(pos->son[1],Mid+1,R);
		}
	}
	void SegTree::Edit(Node *pos,int L,int R,int l,int r,int64 add) {
		if(L==l && R==r)
			pos->Add(add);
		else {
			int Mid=(L+R)>>1;
			pos->Down();
			if(r<=Mid)
				Edit(pos->son[0],L,Mid,l,r,add);
			else if(Mid+1<=l)
				Edit(pos->son[1],Mid+1,R,l,r,add);
			else {
				Edit(pos->son[0],L,Mid,l,Mid,add);
				Edit(pos->son[1],Mid+1,R,Mid+1,r,add);
			}
			pos->Up();
		}
	}
	void SegTree::Edit(int l,int r,int64 add) {
		if(!l || !r || l>r)
			return;
		Edit(root,L,R,l,r,add);
	}
	int64 SegTree::Access(Node *pos,int L,int R,int l,int r) {
		if(L==l && R==r)
			return pos->maxv;
		else {
			int Mid=(L+R)>>1;
			pos->Down();
			if(r<=Mid)
				return Access(pos->son[0],L,Mid,l,r);
			else if(Mid+1<=l)
				return Access(pos->son[1],Mid+1,R,l,r);
			else
				return max(Access(pos->son[0],L,Mid,l,Mid),Access(pos->son[1],Mid+1,R,Mid+1,r));
		}
	}
	int64 SegTree::Access(int l,int r) {
		return Access(root,L,R,l,r);
	}
}using _SegTree_::SegTree;
int main() {
//	freopen("input","r",stdin);
	static int movie[MAXN],w[MAXN];
	int n,m;is>>n>>m;
	for(int i=1;i<=n;++i)
		is>>movie[i];
	for(int i=1;i<=m;++i)
		is>>w[i];
	SegTree seg(1,n);
	static int next[MAXN],pre[MAXN],now[MAXN];
	for(int i=1;i<=n;++i) {
		pre[i]=now[movie[i]];
		next[now[movie[i]]]=i;
		now[movie[i]]=i;
		//pre[i]=pre[i]?pre[i]:1;
	}
	for(int i=1;i<=m;++i)
		next[now[i]]=n+1;//now[m]...
	int64 Ans=0;
	for(int i=1;i<=n;++i) {
		int mv=movie[i];
		//seg.Edit(pre[i],i-1,-w[mv]);
		//seg.Edit(i,next[i]-1,w[mv]);
		seg.Edit(pre[pre[i]]+1,pre[i],-w[mv]);
		seg.Edit(pre[i]+1,i,w[mv]);
		chkmx(Ans,seg.Access(1,i));
	}
	os<<Ans<<'\n';
	return 0;
}