梦想熟练掌握平衡树

发表于 | 更新于 | 评论数： | 阅读次数：

现在菜的不行不行的，也就会个fhq_treap板子，但是还是希望能够熟练掌握平衡树

先对着kuangbin的刷刷吧

现在就只会用fhq_treap的操作

A Simple Problem with Integers POJ - 3468
这个玩意就是明确的告诉你，平衡树完全可以执行线段树的操作，代码也很简单打个lazytag

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
#include <iostream>
#include <cstdio>
#include <ctime>
using namespace std;
typedef long long ll;
const int N=300005;
long long s[N];
int l[N],r[N],rt,sz[N],rnd[N],a[N],cnt,f[N];
void up(int p)
{
	sz[p]=sz[l[p]]+sz[r[p]]+1;
	s[p]=s[l[p]]+s[r[p]]+a[p];
}
void lazy(int p)
{
	if(f[p])
	{
		s[l[p]]+=1LL*sz[l[p]]*f[p];
		s[r[p]]+=1LL*sz[r[p]]*f[p];
		f[l[p]]+=f[p];
		f[r[p]]+=f[p];
		a[l[p]]+=f[p];
		a[r[p]]+=f[p];
		f[p]=0;
	}
}
void split(int p,int k,int& x,int& y)
{
	if(!p) x=y=0;
	else
	{
		lazy(p);
		if(k>sz[l[p]])
		x=p,split(r[p],k-sz[l[p]]-1,r[p],y);
		else
		y=p,split(l[p],k,x,l[p]);
		up(p);
	}
}
int merge(int x,int y)
{
	if(!x||!y) return x+y;
	else
	{
		lazy(x),lazy(y);
		if(rnd[x]<rnd[y])
		{r[x]=merge(r[x],y),up(x);return x;}
		else
		{l[y]=merge(x,l[y]),up(y);return y;}
	}
}
int npt(ll x)
{
	a[++cnt]=x;
	sz[cnt]=1;
	rnd[cnt]=rand();
	s[cnt]=x;
	return cnt;
}
void change(int p,int x,int y,int z)
{
	int aa,b,c;
	split(rt,y,aa,c);
	split(aa,x-1,aa,b);
	f[b]+=z;
	a[b]+=z;
	rt=merge(merge(aa,b),c);
}
void sum(int p,int x,int y)
{
	int aa,b,c;
	split(rt,y,aa,c);
	split(aa,x-1,aa,b);
	printf("%lld\n",s[b]);
	rt=merge(merge(aa,b),c);
}
int main()
{
	srand(time(0));
	int n,m,x,y,z;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	scanf("%d",&x),rt=merge(rt,npt(x));
	while(m--)
	{
		char c;
		scanf(" \n%c",&c);
		if(c=='Q')
		{
			scanf("%d%d",&x,&y);
			sum(rt,x,y);
		}	
		else
		{
			scanf("%d%d%d",&x,&y,&z);
			change(rt,x,y,z);
		}
	}	
}

差点没卡过去，还是int快啊。。。。
SuperMemo POJ - 3580
真的恶心好多操作啊，感觉单拿出来都是弱鸡合在一起就变得有点恶心(虽然也是弱鸡)
区间搬运就是直接%一下乱搬就行了，这个地方注意一下我们如果对树进行过操作更新最小值的话要在up操作里面加上 

1
m[p]=a[p];

这样就行了，我最初还以为tmd要dfs遍历修改一下结果TLE，这样就能过了。
这里出现了两个lazy但是我感觉也没有啥先后顺序吧，翻转和加和谁在前面好像没差啊 

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
#include <cstdio>
#include <iostream>
#include <ctime>
#include <cstring>
using namespace std;
const int N=500005;
int l[N],r[N],cnt,rt,f1[N],f2[N],a[N],m[N],rnd[N],sz[N];
char ss[105];
void lazy(int p)
{
	if(f2[p])
	{
		swap(l[p],r[p]);
		f2[l[p]]^=1;
		f2[r[p]]^=1;
		f2[p]=0;
	}
	if(f1[p])
	{
		f1[l[p]]+=f1[p];
		f1[r[p]]+=f1[p];
		a[l[p]]+=f1[p];
		a[r[p]]+=f1[p];
		m[l[p]]+=f1[p];
		m[r[p]]+=f1[p];
		f1[p]=0;
	}
}
void out(int p)
{
//	lazy(p);
	if(l[p])
	out(l[p]);
	cout<<a[p]<<" ";
	if(r[p])
	out(r[p]);
}
void up(int p)
{
	sz[p]=sz[l[p]]+sz[r[p]]+1;
	m[p]=a[p];
	if(l[p])
	m[p]=min(m[p],m[l[p]]);
	if(r[p])
	m[p]=min(m[p],m[r[p]]); 
//	cout<<p<<" "<<m[p]<<"\n";
}
void split(int p,int k,int& x,int& y)
{
	if(!p) x=y=0;
	else
	{
		lazy(p);
		if(k>sz[l[p]])
		x=p,split(r[p],k-sz[l[p]]-1,r[p],y);
		else
		y=p,split(l[p],k,x,l[p]);
		up(p);
	}
}
int merge(int x,int y)
{
	if(!x||!y) return x+y;
	else
	{
		lazy(x),lazy(y);
		if(rnd[x]<rnd[y])
		{r[x]=merge(r[x],y),up(x);return x;}
		else
		{l[y]=merge(x,l[y]),up(y);return y;}
	}
}
int npt(int x)
{
	a[++cnt]=x;
	rnd[cnt]=rand();
	sz[cnt]=1;
	m[cnt]=x;
	return cnt;
}
void add(int x,int y,int z)
{
	int aa,bb,cc;
	split(rt,y,aa,cc);
	split(aa,x-1,aa,bb);
	f1[bb]+=z;
	a[bb]+=z;
	m[bb]+=z;
	rt=merge(merge(aa,bb),cc);
}
void reve(int x,int y)
{
	int aa,bb,cc;
	split(rt,y,aa,cc);
	split(aa,x-1,aa,bb);
	f2[bb]^=1;
	rt=merge(merge(aa,bb),cc);
}
void revo(int x,int y,int z)
{
	int aa,bb,cc,dd;
	split(rt,y,aa,cc);
	split(aa,x-1,aa,bb);
	split(bb,y-x+1-z,bb,dd);
	rt=merge(merge(aa,merge(dd,bb)),cc);
}
void ins(int x,int y)
{
	int aa,bb;
	split(rt,x,aa,bb);
	rt=merge(merge(aa,npt(y)),bb);
}
void del(int x)
{
	int aa,bb,cc;
	split(rt,x,aa,cc);
	split(aa,x-1,aa,bb);
	rt=merge(aa,cc);
}
void minn(int x,int y)
{
	int aa,bb,cc;
	split(rt,y,aa,cc);
	split(aa,x-1,aa,bb);
	//cout<<aa<<" "<<bb<<" "<<cc<<"\n";
	printf("%d\n",m[bb]);
	rt=merge(merge(aa,bb),cc);
}
int main()
{
	srand(19260817);
	int n,x,mm,y,z;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&x),rt=merge(rt,npt(x));
	scanf("%d",&mm);
	while(mm--)
	{
		scanf("%s",ss+1);
		if(ss[1]=='A')
		{
			scanf("%d%d%d",&x,&y,&z);
			add(x,y,z);
		}
		else if(ss[1]=='R'&&ss[4]=='E')
		{
			scanf("%d%d",&x,&y);
			reve(x,y);
		}
		else if(ss[1]=='R'&&ss[4]=='O')
		{
			scanf("%d%d%d",&x,&y,&z);
			z%=(y-x+1);
			if(z==0)
			continue;
			revo(x,y,z);
		}
		else if(ss[1]=='I')
		{
			scanf("%d%d",&x,&y);
			ins(x,y);
		}
		else if(ss[1]=='D')
		{
			scanf("%d",&x);
			del(x);
		}
		else
		{
			scanf("%d%d",&x,&y);
			minn(x,y);
		}
	}
}
/*
10
1 2 3 4 5 6 7 8 9 10
15
ADD 4 8 3
MIN 5 7
MIN 7 10
REVERSE 2 5
MIN 2 6
MIN 2 3
INSERT 3 4
MIN 3 4
MIN 5 10
DELETE 6
MIN 3 5
MIN 4 4
REVOLVE 3 6 7
MIN 5 8
MIN 7 10
*/

Play with Chain HDU - 3487
水题比起上一题来说真的是放水不少了。。。就是有一个地方他会卡PE。。。
我们在中序遍历平衡树的时候注意最后不要有多余的空格然后就A了

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
#include <bits/stdc++.h>
using namespace std;
const int N=600005;
int sz[N],l[N],r[N],f[N],rnd[N],a[N],cnt,rt,jk,n;
char s[N];
int npt(int x)
{
	a[++cnt]=x;
	rnd[cnt]=rand();
	sz[cnt]=1;
	f[cnt]=l[cnt]=r[cnt]=0;
	return cnt;
}
void lazy(int p)
{
	if(f[p])
	{
		swap(l[p],r[p]);
		f[l[p]]^=1;
		f[r[p]]^=1;
		f[p]=0;
	}
}
void out(int p)
{
	lazy(p);
	if(l[p])
	out(l[p]);
	jk++;
	printf("%d%c",a[p],jk==n?'\n':' ');
	if(r[p])
	out(r[p]);
}
void up(int p)
{
	sz[p]=sz[l[p]]+sz[r[p]]+1;
}
void split(int p,int k,int& x,int& y)
{
	if(!p) x=y=0;
	else
	{
		lazy(p);
		if(k>sz[l[p]])
		x=p,split(r[p],k-sz[l[p]]-1,r[p],y);
		else
		y=p,split(l[p],k,x,l[p]);
		up(p);
	}
} 
int merge(int x,int y)
{
	if(!x||!y) return x+y;
	else
	{
		lazy(x),lazy(y);
		if(rnd[x]<rnd[y])
		{r[x]=merge(r[x],y),up(x);return x;}
		else
		{l[y]=merge(x,l[y]),up(y);return y;}
	}
}
void cut(int x,int y,int z)
{
	int aa,bb,cc,dd,re,re1;
	split(rt,y,aa,cc);
	split(aa,x-1,aa,bb);
	re=merge(aa,cc);
	split(re,z,re,re1);
	rt=merge(merge(re,bb),re1);
}
void rev(int x,int y)
{
	int aa,bb,cc;
	split(rt,y,aa,cc);
	split(aa,x-1,aa,bb);
	f[bb]^=1;
	rt=merge(merge(aa,bb),cc);
}
int main()
{
	srand(19260817);
	int m,x,y,z;
	while(~scanf("%d%d",&n,&m))
	{
		if(n==m&&n==-1)
		break;
		rt=cnt=jk=0;
		for(int i=1;i<=n;i++)	
		rt=merge(rt,npt(i));
		while(m--)
		{
			scanf("%s",s+1);
			if(s[1]=='C')
			{
				scanf("%d%d%d",&x,&y,&z);
				cut(x,y,z);
			}
			else
			{
				scanf("%d%d",&x,&y);
				rev(x,y);
			}
		}
		out(rt);
	} 
}
就算是一分钱，也是对作者极大的支持
------ 本文结束 ------

版权声明

Baccano by baccano is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由baccano创作并维护的Baccano博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。
本文首发于baccano 博客（ http://baccano.fun ），版权所有，侵权必究。

小游戏

---小游戏:要不要来选择一下自己可能的老婆？---

简易发声器

---简易的七键钢琴插件---

可以使用鼠标点击琴键也可以使用主键盘1-7或者小键盘的1-7来操作

那么现在开始吧

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
0%