BZOJ 3524 Couriers

发表于 | 更新于

Link

Solution

我想出的优秀做法： 外层区间线段树，内层值域线段树，查询的时候线段树合并，在合并出的线段树上查询最大值与r−l+12\dfrac {r-l+1}2比较 想出来之后，一看Solved：700+？POI的题有这么多人做？有那么好写吗？ 当我看到正解之后惊呆了 一切尽在代码中

Tips

给了这样的限制也许就可以得到有用的性质啊。。不分析限制直接暴力想对于所有的范围不可取啊。。

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
#include "lucida"
const int MAXN=500000+11;
namespace _ChmTree_ {
	const int SIZE=1e7;
	struct Node *null;
	struct Node {
		Node *son[2];
		int cnt;
		Node() {
			son[0]=son[1]=null;
			cnt=0;
		}
		Node(Node* old) {
			*this=*old;
		}
		void Up() {
			cnt=son[0]->cnt+son[1]->cnt;
		}
		void *operator new(size_t) {
			static Node *Pool=(Node*)malloc(SIZE*sizeof(Node)),*Me=Pool;
			return Me++;
		}
	}*_null=null=new Node;
	struct ChmTree {
	//private:
		Node *root[MAXN];
		int minv,maxv,rc;
		int Access(Node *rl,Node *rr,int L,int R,int c) {
			if(L==R)
				return rr->cnt-rl->cnt>=c?L:0;
			else {
				int Mid=(L+R)>>1;
				if(rr->son[0]->cnt-rl->son[0]->cnt>=c)
					return Access(rl->son[0],rr->son[0],L,Mid,c);
				else
					return Access(rl->son[1],rr->son[1],Mid+1,R,c);
			}
		}
		void Edit(Node *&pos,int L,int R,int goal) {
			pos=new Node(pos);
			if(L==R)
				pos->cnt++;
			else {
				int Mid=(L+R)>>1;
				if(goal<=Mid)
					Edit(pos->son[0],L,Mid,goal);
				else
					Edit(pos->son[1],Mid+1,R,goal);
				pos->Up();
			}
		}
	//public:
		ChmTree(int minv,int maxv):minv(minv),maxv(maxv) {
			root[rc=0]=null->son[0]=null->son[1]=null;
		}
		void Insert(int x) {
			++rc;
			Edit(root[rc]=root[rc-1],minv,maxv,x);
		}
		int Query(int l,int r,int k) {
			return Access(root[l-1],root[r],minv,maxv,k);
		}
	};
}using _ChmTree_::ChmTree;
int main() {
//	freopen("input","r",stdin);
	int n,m;is>>n>>m;
	ChmTree seg(1,n);
	for(int i=1;i<=n;++i) {
		int x;is>>x;
		seg.Insert(x);
	}
	for(int i=1;i<=m;++i) {
		int l,r;
		is>>l>>r;
		os<<seg.Query(l,r,(r-l+1)/2+1)<<'\n';
	}
	return 0;
}