SBT

数据结构, SBT
  1. 1 【bzoj 3224】Tyvj 1728 普通平衡树
  2. 2 【bzoj 1208】[HNOI2004]宠物收养所
  3. 3 【bzoj 1588】[HNOI2002]营业额统计
  4. 4 【bzoj 1056/1862】[Zjoi2006][HAOI2008]排名系统
  5. 5 【bzoj 1503】[NOI2004]郁闷的出纳员
  6. 6 【bzoj 2761】[JLOI2011]不重复数字
  7. 7 【bzoj 3173】[Tjoi2013]最长上升子序列

开始学平衡树

模板 

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
#include<cstdio>
using namespace std;
const int N=100001;
int n,tot,root,key[N],lefts[N],rights[N],size[N];
void Left_Rotate(int &x)
{
	int y=rights[x];
	rights[x]=lefts[y];
	lefts[y]=x;
	size[y]=size[x];
	size[x]=size[lefts[x]]+size[rights[x]]+1;
	x=y;
}
void Right_Rotate(int &x)
{
	int y=lefts[x];
	lefts[x]=rights[y];
	rights[y]=x;
	size[y]=size[x];
	size[x]=size[lefts[x]]+size[rights[x]]+1;
	x=y;
}
void Maintain(int &x,bool flag)
{
	if(!flag)
	{
		if(size[lefts[lefts[x]]]>size[rights[x]])
		  Right_Rotate(x);
		else if(size[rights[lefts[x]]]>size[rights[x]])
		  Left_Rotate(lefts[x]),Right_Rotate(x);
		else return;
	}
	else
	{
		if(size[rights[rights[x]]]>size[lefts[x]])
		  Left_Rotate(x);
		else if(size[lefts[rights[x]]]>size[lefts[x]])
		  Right_Rotate(rights[x]),Left_Rotate(x);
		else return;
	}
	Maintain(lefts[x],0);
	Maintain(rights[x],1);
	Maintain(x,1);
	Maintain(x,0);
}
void Insert(int &x,int y)
{
	if(!x)
	{
		x=++tot;
		key[x]=y;
		lefts[x]=rights[x]=0;
		size[x]=1;
		return;
	}
	size[x]++;
	if(y<=key[x]) Insert(lefts[x],y);
	else Insert(rights[x],y);
	Maintain(x,y>key[x]); 
}
int Delete(int &x,int y)
{
	size[x]--;
	if(y==key[x]||(y<key[x]&&!lefts[x])||(y>key[x]&&!rights[x]))
	{
		int ans=key[x];
		if(!lefts[x]||!rights[x]) x=lefts[x]+rights[x];
		else key[x]=Delete(lefts[x],key[x]+1);
		return ans;
	}
	if(y<key[x]) return Delete(lefts[x],y);
	else return Delete(rights[x],y);
}
bool Find(int &x,int y)
{
	if(!x) return 0;
	if(y<=key[x]) return (y==key[x])||Find(lefts[x],y);
	else return Find(rights[x],y);
}
int Rank(int &x,int y)
{
	if(!x) return 1;
	if(y<=key[x]) return Rank(lefts[x],y);
	else return size[lefts[x]]+1+Rank(rights[x],y);
}
int Select(int &x,int y)
{
	if(y==size[lefts[x]]+1) return key[x];
	if(y<=size[lefts[x]]) return Select(lefts[x],y);
	else return Select(rights[x],y-size[lefts[x]]-1);
}
int Pred(int &x,int y)
{
	if(!x) return y;
	if(y<=key[x]) return Pred(lefts[x],y);
	else
	{
		int ans=Pred(rights[x],y);
		if(y==ans) return key[x];
		else return ans;
	}
}
int Succ(int &x,int y)
{
	if(!x) return y;
	if(y>=key[x]) return Succ(rights[x],y);
	else
	{
		int ans=Succ(lefts[x],y);
		if(y==ans) return key[x];
		else return ans;
	}
}
void Inorder(int x)
{
	if(x)
	{
		Inorder(lefts[x]);
		printf("%d ",key[x]);
		Inorder(rights[x]);
	}
}
int main()
{
	freopen("sbt.in","r",stdin);
	scanf("%d",&n);
	for(int i=1,x,y;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		if(x==1) Insert(root,y);//插入 
		else if(x==2) Delete(root,y);//删除 
		else if(x==3) printf("%d\n",Find(root,y));//权值为y的点是否存在 
		else if(x==4) printf("%d\n",Rank(root,y));//权值为y的点的排名 
		else if(x==5) printf("%d\n",Select(root,y));//排名为y的数 
		//最小值 Select(root,1); 最大值 Select(root,size[root]);
		else if(x==6) printf("%d\n",Pred(root,y));//前驱 
		else printf("%d\n",Succ(root,y));//后继 
		Inorder(root);printf("\n\n");//遍历 
	}
}

Delete：若不存在，删除后一个；若大于总数，删除最后一个
Rank：若不存在，返回后一个；若大于最大值，返回总数+1
Select：若大于总数，返回0
Pred：返回小于它的最大值；若小于最小值，返回本身
Succ：返回大于它的最小值；若大于最大值，返回本身

1 【bzoj 3224】Tyvj 1728 普通平衡树

维护一些数，其中需要提供以下操作：
1.插入x数
2.删除x数(若有多个相同的数，因只删除一个)
3.查询x数的排名(若有多个相同的数，因输出最小的排名)
4.查询排名为x的数
5.求x的前驱(前驱定义为小于x，且最大的数)
6.求x的后继(后继定义为大于x，且最小的数)

太水了我就不贴代码了，基本和模板差不多

2 【bzoj 1208】[HNOI2004]宠物收养所

被遗弃的宠物过多时，来一个领养者特点值为a，那么它将会领养一只目前未被领养的宠物中特点值最接近a的一只宠物。如果有两只满足要求的宠物，即存在两只宠物他们的特点值分别为a-b和a+b，那么领养者将会领养特点值为a-b的那只宠物。反之相同。
一个领养者领养了一个特点值为a的宠物，而它本身希望领养的宠物的特点值为b，那么这个领养者的不满意程度为abs(a-b)。求∑min{abs(a−b)}\sum min\lbrace abs(a-b)\rbrace.

写主函数就好了，比较懒。。。
注意加上-inf和inf，不然两头的就会返回原值
然后把函数改一下，在前驱和后继里求的数就可以相同了 

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
int Pred(int &x,int y)
{
	if(!x) return inf;//一个用不到的数就可以
	if(y<key[x]) return Pred(left[x],y);
	else
	{
		int ans=Pred(right[x],y);
		if(ans==inf) return key[x];
		else return ans;
	}
}
int Succ(int &x,int y)
{
	if(!x) return inf;
	if(y>key[x]) return Succ(right[x],y);
	else
	{
		int ans=Succ(left[x],y);
		if(ans==inf) return key[x];
		else return ans;
	}
}
int main()
{
	scanf("%d",&n);
	Insert(root,-inf);Insert(root,inf);
	for(int i=1,x,y;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		if(x==mark||!m)
		  mark=x,m++,Insert(root,y);
		else
		{
			int a=Pred(root,y),b=Succ(root,y);
			if((long long)y-a<=(long long)b-y) 
			  ans=(ans+y-a)%mod,Delete(root,a);
			else ans=(ans+b-y)%mod,Delete(root,b);
			m--;
		}
	}
	printf("%d",ans);
}

3 【bzoj 1588】[HNOI2002]营业额统计

∑1nmin{abs(a[now]−a[pre])}\sum_1^n min \lbrace abs(a[now]-a[pre]) \rbrace

注意如果之前存在值相同的点就不用再算了
或者把函数改成上一题的样子也行 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main()
{
    scanf("%d",&n);
    Insert(root,-inf);
    Insert(root,inf);
    for(int i=1;i<=n;i++)
    {
        int x=0;scanf("%d",&x);
        if(i==1) ans+=x;
        else
        {
            int a=Pred(root,x),b=Succ(root,x);
            if((long long)x-a<=(long long)b-x) ans+=x-a;
            else ans+=b-x;
        }
        Insert(root,x);
    }
    printf("%d",ans);
}

4 【bzoj 1056/1862】[Zjoi2006][HAOI2008]排名系统

维护排名，分数大的在前，分数相同时先上传的在前。
支持：1、上传或修改；2、查询某个人的；3、查询某个区间

两个题一样，23333，一次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
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
#include<cstring>
#include<cstdio>
#include<map>
using namespace std;
map<unsigned,int> m;
const int N=250010;
const int base=29;
int n,root,tot,totnum,tottime,time[N];
int t[N],name[N],lefts[N],rights[N],size[N];
long long k[N],key[N];
char s[20],sname[N][11];
void Left_Rotate(int &x)
{
	int y=rights[x];
	rights[x]=lefts[y];
	lefts[y]=x;
	size[y]=size[x];
	size[x]=size[lefts[x]]+size[rights[x]]+1;
	x=y;
}
void Right_Rotate(int &x)
{
	int y=lefts[x];
	lefts[x]=rights[y];
	rights[y]=x;
	size[y]=size[x];
	size[x]=size[lefts[x]]+size[rights[x]]+1;
	x=y;
}
void Maintain(int &x,bool flag)
{
	if(!flag)
	{
		if(size[lefts[lefts[x]]]>size[rights[x]])
		  Right_Rotate(x);
		else if(size[rights[lefts[x]]]>size[rights[x]])
		  Left_Rotate(lefts[x]),Right_Rotate(x);
		else return;
	}
	else
	{
		if(size[rights[rights[x]]]>size[lefts[x]])
		  Left_Rotate(x);
		else if(size[lefts[rights[x]]]>size[lefts[x]])
		  Right_Rotate(rights[x]),Left_Rotate(x);
		else return;
	}
	Maintain(lefts[x],0);
	Maintain(rights[x],1);
	Maintain(x,1);
	Maintain(x,0);
}
int Rank(int &x,int y,long long v)
{
	if(!x) return 0;
	if(v==k[x])
	{
		if(y==t[x]) return size[lefts[x]]+1;
		else if(y<t[x]) return Rank(lefts[x],y,v);
		else return size[lefts[x]]+1+Rank(rights[x],y,v);
	}
	if(v>k[x]) return Rank(lefts[x],y,v);
	else return size[lefts[x]]+1+Rank(rights[x],y,v);
}
int Findrank(int &x,int y)
{
	if(y==size[lefts[x]]+1) return name[x];
	if(y<=size[lefts[x]]) return Findrank(lefts[x],y);
	else return Findrank(rights[x],y-size[lefts[x]]-1);
}
void Insert(int &x,int y,long long v)
{
	if(!x)
	{
		x=++tot;
		k[x]=v;t[x]=time[y];name[x]=y;
		lefts[x]=rights[x]=0;
		size[x]=1;
		return;
	}
	size[x]++;
	if(v>k[x]) Insert(lefts[x],y,v);
	else Insert(rights[x],y,v);
	Maintain(x,v<=k[x]);
}
void Delete(int &x,int y,long long v)  //y->time v->key
{
	if((v>k[x]&&!lefts[x])||(v<k[x]&&!rights[x])) return;
	size[x]--;
	if(v==k[x])
	{
		if(y==t[x])
		{
			int ans=k[x];
		    if(!lefts[x]||!rights[x]) x=lefts[x]+rights[x];
		    else
		    {
		    	int u=lefts[x];
		    	while(rights[u]) u=rights[u];
			    k[x]=k[u];name[x]=name[u];t[x]=t[u];
			    Delete(lefts[x],t[u],k[u]);
		    }
		    return;
		}
		else if(y<t[x]) return Delete(lefts[x],y,v);
		else return Delete(rights[x],y,v);
	}
	if(v>k[x]) return Delete(lefts[x],y,v);
	else return Delete(rights[x],y,v);
}
int main()
{
	freopen("rank.in","r",stdin);
	freopen("rank.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s);
		if(s[1]>'9'||s[1]<'0')
		{
			unsigned a=0;
			for(int i=1;i<strlen(s);i++)  a=a*base+s[i]-'A'+1;
			if(s[0]=='+')
			{
				long long j;scanf("%lld",&j);
				if(!m[a])
				{
					m[a]=++totnum;
					for(int i=1;i<strlen(s);i++)  sname[totnum][i-1]=s[i];
				} 
				else Delete(root,time[m[a]],key[m[a]]);
				key[m[a]]=j;time[m[a]]=++tottime;
				Insert(root,m[a],j);
			}
			else
			{
				if(!m[a]) printf("0\n");
				else printf("%d\n",Rank(root,time[m[a]],key[m[a]]));
			}
		}
		else
		{
			int a=0;
			for(int i=1;i<strlen(s);i++)  a=a*10+s[i]-'0';
			for(int i=a;i<=a+9&&i<=size[root];i++)
			{
				int j=Findrank(root,i);
				if(i!=a) printf(" ");
				printf("%s",sname[j]);
			}  
			printf("\n");
		}
	}
}

5 【bzoj 1503】[NOI2004]郁闷的出纳员

好像还比较水
注意立刻离开公司意味着不算进总人数

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
#include<cstdio>
using namespace std;
int n,minn,k,tot,root,ans;
int key[100001],left[100001],right[100001],size[100001];
char s[1];
void Left_Rotate(int &x)
{
	int y=right[x];
	right[x]=left[y];
	left[y]=x;
	size[y]=size[x];
	size[x]=size[left[x]]+size[right[x]]+1;
	x=y;
}
void Right_Rotate(int &x)
{
	int y=left[x];
	left[x]=right[y];
	right[y]=x;
	size[y]=size[x];
	size[x]=size[left[x]]+size[right[x]]+1;
	x=y;
}
void Maintain(int &x,bool flag)
{
	if(!flag)
	{
		if(size[left[left[x]]]>size[right[x]])
		  Right_Rotate(x);
		else if(size[right[left[x]]]>size[right[x]])
		  Left_Rotate(left[x]),Right_Rotate(x);
		else return;
	}
	else
	{
		if(size[right[right[x]]]>size[left[x]])
		  Left_Rotate(x);
		else if(size[left[right[x]]]>size[left[x]])
		  Right_Rotate(right[x]),Left_Rotate(x);
		else return;
	}
	Maintain(left[x],0);
	Maintain(right[x],1);
	Maintain(x,1);
	Maintain(x,0);
}
int Select(int &x,int y)
{
	if(y==size[left[x]]+1) return key[x];
	if(y<=size[left[x]]) return Select(left[x],y);
	else return Select(right[x],y-size[left[x]]-1);
}
void Insert(int &x,int y)
{
	if(!x)
	{
		x=++tot;
		key[x]=y;
		left[x]=right[x]=0;
		size[x]=1;
		return;
	}
	size[x]++;
	if(y>=key[x]) Insert(left[x],y);
	else Insert(right[x],y);
	Maintain(x,y<key[x]);
}
int Delete(int &x,int y)
{
	size[x]--;
	if((y>key[x]&&!left[x])||(y<key[x]&&!right[x])) return 0;
	if(y==key[x])
	{
		int ans=key[x];
		if(!left[x]||!right[x]) x=left[x]+right[x];
		else
		{
			int t=Select(left[x],size[left[x]]);
			key[x]=Delete(left[x],t);
		} 
		return ans;
	}
	if(y>key[x]) return Delete(left[x],y);
	else return Delete(right[x],y);
}
void Add(int &x,int y)
{
	if(!x) return;
	Add(left[x],y);
	key[x]+=y;
	Add(right[x],y);
}
void Search(int &x)
{
	if(!x) return;
	Search(left[x]);Search(right[x]);
	if(key[x]<minn) ans++,Delete(root,key[x]);
}
int main()
{
	freopen("cashier.in","r",stdin);
	freopen("cashier.out","w",stdout);
	scanf("%d%d",&n,&minn);
	for(int i=1;i<=n;i++)
	{
		scanf("%s%d",s,&k);
		if(s[0]=='I') {if(k>=minn) Insert(root,k);}
		else if(s[0]=='A') Add(root,k),Search(root);
		else if(s[0]=='S') Add(root,-k),Search(root);
		else if(k>size[root]) printf("-1\n");
		else printf("%d\n",Select(root,k));
	}
	printf("%d\n",ans);
}

6 【bzoj 2761】[JLOI2011]不重复数字

给出N个数，要求把其中重复的去掉，只保留第一次出现的数。

太水了吧
set和map真好写，就是慢了点
其实SBT和它们的时间几乎没有差别。。。
才开始PE好几回，因为每行最后每空格。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);tot=0;root=0;
		for(int i=1,x;i<=n;i++)
		{
			scanf("%d",&x);
			if(!Find(root,x))
			{
				Insert(root,x);
				if(i>1) printf(" ");
				printf("%d",x);
			}
		}
		printf("\n");
	}
}

7 【bzoj 3173】[Tjoi2013]最长上升子序列

给定一个序列，初始为空。现在我们将1到N的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？

用平衡树先把序列求出来，然后用nlogn的算法求LIS(因为n2n^2过不了)
LIS：
法1：详解+演示
法2：原本的LIS是f[j]=f[i]+i (i<j&&h[i]<h[j])
用树状数组在logn时间内求出高度<h[j]的最大f值

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
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=100001;
int n,tot,root,len;
int f[N],a[N],ans[N],key[N],left[N],right[N],size[N];
void Left_Rotate(int &x)
{
	int y=right[x];
	right[x]=left[y];
	left[y]=x;
	size[y]=size[x];
	size[x]=size[left[x]]+size[right[x]]+1;
	x=y;
}
void Right_Rotate(int &x)
{
	int y=left[x];
	left[x]=right[y];
	right[y]=x;
	size[y]=size[x];
	size[x]=size[left[x]]+size[right[x]]+1;
	x=y;
}
void Maintain(int &x,bool flag)
{
	if(!flag)
	{
		if(size[left[left[x]]]>size[right[x]])
		  Right_Rotate(x);
		else if(size[right[left[x]]]>size[right[x]])
		  Left_Rotate(left[x]),Right_Rotate(x);
		else return;
	}
	else
	{
		if(size[right[right[x]]]>size[left[x]])
		  Left_Rotate(x);
		else if(size[left[right[x]]]>size[left[x]])
		  Right_Rotate(right[x]),Left_Rotate(x);
		else return;
	}
	Maintain(left[x],0);
	Maintain(right[x],1);
	Maintain(x,1);
	Maintain(x,0);
}
void Insert(int &x,int y)
{
	if(!x)
	{
		x=++tot;
		size[x]=1;
		return;
	}
	size[x]++;
	if(y<=size[left[x]]) Insert(left[x],y);
	else Insert(right[x],y-size[left[x]]-1);
	Maintain(x,y>key[x]); 
}
void Inorder(int x)
{
	if(x)
	{
		Inorder(left[x]);
		a[++tot]=x;
		Inorder(right[x]);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1,j;i<=n;i++)
	  scanf("%d",&j),Insert(root,j);
	tot=0;Inorder(root);
	
	memset(f,127,sizeof(f));
	f[0]=-0x7fffffff;
	for(int i=1;i<=n;i++)
	{
		int t=upper_bound(f,f+len+1,a[i])-f;
		if(f[t-1]<=a[i])
		{
			if(a[i]<f[t]) f[t]=a[i];
			ans[a[i]]=t;
			if(t>len) len=t;
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(ans[i-1]>ans[i]) ans[i]=ans[i-1];
		printf("%d\n",ans[i]);
	}
}

法2例题：【COGS 2049】疯狂动物城

1.物理学要求：为了稳定和美观，半径大的蛋糕必须在放在半径小的蛋糕下面。
2.Mr.Big的钦定要求：编号小的蛋糕必须放在编号大的蛋糕下面。
你需要帮他制定一个使多层蛋糕总体积最大的方案。
注意：两个半径相同的蛋糕不能放在一起

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
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=100001;
const double pi=3.14159265358979323846;
int n,pos[N];
double ans,f,v[N],mx[N];
pair<int,int> a[N];
inline void Change(int x,double y)
{
	for(;x<=n;x+=x&(-x)) mx[x]=max(mx[x],y);
}
inline double Quary(int x)
{
	double maxx=0;
	for(;x;x-=x&(-x)) maxx=max(maxx,mx[x]);
	return maxx;
}
int main()
{
	freopen("zootopia.in","r",stdin);
	freopen("zootopia.out","w",stdout);
	scanf("%d",&n);
	for(int i=n,x,y;i;i--)
	{
		scanf("%d%d",&x,&y);
		a[i]=make_pair(x,i);
		v[i]=pi*x*x*y;
	} 
	sort(a+1,a+n+1);
	pos[a[1].second]=1;
	for(int i=2;i<=n;i++)
	  pos[a[i].second]=pos[a[i-1].second]+(a[i].first!=a[i-1].first);
	for(int i=1;i<=n;i++)
	{
		f=Quary(pos[i]-1)+v[i];
		Change(pos[i],f);
		ans=max(ans,f);
	}
	printf("%.2lf\n",ans);
}
SBT