BZOJ 2733 永无乡

发表于 | 更新于

Link

Solution

很模板的题目了。。想试试能不能以最快的速度写出来并且A掉。20min写完之后RE了，结果发现是数组开小了。。 线段树只有建立一棵树的时候节点数才能用n<<2n<<2，否则即使不可持久化也可能是nlognn \log n。多么显然。。我居然没想到。。

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
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=100000+10;
using std::swap;
using std::sort;
using std::lower_bound;
using std::unique;
namespace Seg
{
	const int SIZE=MAXN*25,TL=1;
	int TR;
	struct Node
	{
		Node *son[2];
		int cnt,id;
		Node(){son[0]=son[1]=0;cnt=id=0;}
		void up(){cnt=son[0]->cnt+son[1]->cnt;}
		bool isleaf(){return son[0]==son[1];}
	}*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL,*null=new(ME++) Node;
	Node *newNode()
	{
		static Node *cur;cur=ME++;
		cur->son[0]=cur->son[1]=null;
		cur->cnt=cur->id=0;return cur;
	}
	void Edit(Node *&pos,int L,int R,int goal,int cnt,int id)
	{
		if(pos==null) pos=newNode();
		if(L==R) pos->cnt=cnt,pos->id=id;
		else
		{
			int MID=(L+R)>>1;
			if(goal<=MID) Edit(pos->son[0],L,MID,goal,cnt,id);
			else Edit(pos->son[1],MID+1,R,goal,cnt,id);
			pos->up();
		}
	}
	int Access(Node *pos,int L,int R,int K)
	{
		if(pos==null) return -1;//assert(1);
		if(L==R) return pos->id;
		else
		{
			int MID=(L+R)>>1;
			if(K<=pos->son[0]->cnt) return Access(pos->son[0],L,MID,K);
			else return Access(pos->son[1],MID+1,R,K-pos->son[0]->cnt);
		}
	}
	Node *Merge(Node *p1,Node *p2)
	{
		if(p1==null) return p2;
		if(p2==null) return p1;
		//merge leaf is not in need
		p1->son[0]=Merge(p1->son[0],p2->son[0]);
		p1->son[1]=Merge(p1->son[1],p2->son[1]);
		p1->up();
		return p1;
	}
}using namespace Seg;
Seg::Node *root[MAXN];
namespace DJU
{
	int fa[MAXN];
	int Root(int x){return fa[x]?fa[x]=Root(fa[x]):x;}
}using namespace DJU;
void Join(int p1,int p2)
{
	p1=Root(p1),p2=Root(p2);
	if(p1==p2) return;
	if(root[p1]->cnt<root[p2]->cnt) swap(p1,p2);//把p2并到p1
	root[p1]=Merge(root[p1],root[p2]);fa[p2]=p1;
}
int main()
{
	static int a[MAXN],t[MAXN];
	int n,m;get(n),get(m);TR=n;
	for(int i=1;i<=n;i++) get(a[i]),t[i]=a[i];
	sort(t+1,t+1+n);
	for(int i=1;i<=n;i++)
		Edit(root[i]=null,TL,TR,a[i]=lower_bound(t+1,t+1+n,a[i])-t,1,i);
	for(int i=1;i<=m;i++)
	{
		int x,y;get(x),get(y);
		Join(x,y);
	}
	int Q;get(Q);
	for(int i=1;i<=Q;i++)
	{
		char opt;while(!isalpha(opt=getchar()));
		int x,y;get(x),get(y);
		if(opt=='Q') printf("%d\n",Access(root[Root(x)],TL,TR,y));
		else Join(x,y);
	}
	return 0;
}
/* AC Record(Bugs) *
 * RE sizeof array too small;;
 *		n log n->n*4 只有一棵树的时候才能用n<<2，
 *		否则即使不可持久化也可能是n log n
 * * * * * * * * * */