Bzoj3600 没有人的算术

, ,

Description

https://www.luogu.com.cn/problem/P6272

Solution

好像是替罪羊树维护序列集合偏序关系板子题。但是一直不会。

直接递归比较两个串的大小是困难的，注意到所有串之间的偏序关系是有传递性的，如果我们能把每个串，哈希成一个实数，然后放在线段树上直接比较即可。

我们考虑维护一个有序的集合，集合中的每个元素对应一个串，而根据这个元素在集合中的位置来维护这个串对应元素的哈希值。

我们只需要支持插入这个操作。假设我们已经有了这样一个集合，我们现在要插入一个新串 $(x,y)$。$x,y$ 都是已经在集合中出现过的元素。考虑 $x,y$ 直接对应成集合中的哈希值 $h_x,h_y$，然后插入到为止 $p$，给他赋值成 $h_{p-1},h_{p+1}$ 之间的任意一个数。不妨赋值成中位数。

容易想到用平衡树来维护。而如果要旋转的话，需要把整棵树重新赋值。所以这时候用暴力重构的替罪羊树维护即可。复杂度 $O(n\log n)$。

实现细节上，线段树每个节点维护平衡树上对应的下标，由于重构只会改变 $a_i$ 的哈希值而不改变任何相对关系，这样重构就不用在线段树上修改了。

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
131
132
133
134
135
136
137
138
139
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 500005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
double a[maxn];
struct yyy {
	int x,y;
	bool operator <(const yyy tmp) const {
		if (x==tmp.x) return a[y]<=a[tmp.y];
		else return a[x]<=a[tmp.x];
	}
	bool operator ==(const yyy tmp) const {
		return x==tmp.x&&y==tmp.y;
	}
};
int pos[maxn];//每个点指向哪个 a
int root;
namespace bst {
	yyy val[maxn];//偏序集合上指向哪个 a
	struct node {
		int ls,rs,siz;
	}f[maxn];
	int arr[maxn],tot,cnt;
	const double alpha=0.7;
	void dfs(int rt) {
		if (!rt) return ;
		dfs(f[rt].ls);
		arr[++tot]=rt;
		dfs(f[rt].rs);
	}
	int build(int l,int r,double L,double R) {
		if (l>r) return 0;
		int mid=l+r>>1;
		double MID=(L+R)/2;
		int rt=arr[mid];a[rt]=MID;
		f[rt].siz=1;
		f[rt].ls=build(l,mid-1,L,MID);
		f[rt].rs=build(mid+1,r,MID,R);
		f[rt].siz=f[f[rt].ls].siz+f[f[rt].rs].siz+1;
		return rt;
	}
	int rebuild(int rt,double L,double R) {
		tot=0;
		dfs(rt);
		return build(1,tot,L,R);
	}
	bool check(int rt) {
		return max(f[f[rt].ls].siz,f[f[rt].rs].siz)>f[rt].siz*alpha;
	}
	int insert(int &rt,double L,double R,yyy k) {
		double MID=(L+R)/2;
		if (!rt) {
			rt=++cnt;
			// gdb(rt,L,R,MID,k.x,k.y);
			f[cnt].siz=1;val[cnt]=k;a[cnt]=MID;
			return cnt;
		}
		if (k==val[rt]) return rt;
		int tmp=0;
		if (k<val[rt]) tmp=insert(f[rt].ls,L,MID,k);
		else tmp=insert(f[rt].rs,MID,R,k);
		if (check(rt)) rt=rebuild(rt,L,R);
		f[rt].siz=f[f[rt].ls].siz+f[f[rt].rs].siz+1;
		return tmp;
	}
}
int n,m;
namespace seg {
	int f[maxn<<2];
	void Update(int l,int r,int rt,int head) {
		if (l==r) return f[rt]=l,void();
		int mid=l+r>>1;
		if (head<=mid) Update(l,mid,rt<<1,head);
		else Update(mid+1,r,rt<<1|1,head);
		if (a[pos[f[rt<<1]]]>=a[pos[f[rt<<1|1]]]) f[rt]=f[rt<<1];
		else f[rt]=f[rt<<1|1];
	}
	int Query(int l,int r,int rt,int head,int tail) {
		if (head<=l&&r<=tail) return f[rt];
		int mid=l+r>>1;
		if (head<=mid&&mid<tail) {
			int tmp1=Query(l,mid,rt<<1,head,tail);
			int tmp2=Query(mid+1,r,rt<<1|1,head,tail);
			if (a[pos[tmp1]]>=a[pos[tmp2]]) return tmp1;
			else return tmp2;
		}
		else if (head<=mid) return Query(l,mid,rt<<1,head,tail);
		else if (tail>mid)  return Query(mid+1,r,rt<<1|1,head,tail);
		return assert(0),0;
	}
}
signed main(void){
	int i,l,r,k,x;char ch;
	read(n);read(m);
	a[0]=-1;
	bst::insert(root,0,1,(yyy){0,0});
	for (i=1;i<=n;i++) pos[i]=1,seg::Update(1,n,1,i);
	while (m--) {
		ch=getchar();while (ch!='C'&&ch!='Q') ch=getchar();
		read(l);read(r);
		if (ch=='C') {
			read(x);
			pos[x]=bst::insert(root,0,1,(yyy){pos[l],pos[r]});
			seg::Update(1,n,1,x);
		}
		else {
			printf("%d\n",seg::Query(1,n,1,l,r));
		}
	}
	return 0;
}
//i=begin && g++ $i.cpp -o $i -std=c++14 && ./$i