前言

萌新的数据结构板子，可能有些地方很抽象，反正是自己用。

st表

写个线段树不好？不好，容易被卡常。

O(1)O(1) 查询

O(nlog⁡n)O(n \log n) 预处理以及空间消耗

遇到卡空间的题，可以把查询一次改成查询多个区间多次，常数还是很优秀，但是实际写起来有没有树状数组优是个问题？我在老脆克斯里面有道题用了这个方法。

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
#include<bits/stdc++.h>

#define endl '\n'

using namespace std;

const int maxn=2e6+5;

int n,m,a[maxn];

namespace stb{
	
	int st[21][maxn];
	int l2[maxn];
	
	void pre()
	{
		for(int i=2;i<=n;i++) l2[i]=l2[i>>1]+1;
		for(int i=1;i<=n;i++) st[0][i]=a[i];
		for(int i=1;i<=l2[n];i++)
		{
			for(int j=1;j<=n;j++)
			{
				st[i][j]=max(st[i-1][j],st[i-1][j+(1<<(i-1))]);
			}
		}
		return ;
	}
	
	int getmax(int l,int r)
	{
		int tmp=l2[r-l+1];
		return max(st[tmp][l],st[tmp][r-(1<<tmp)+1]);
	}
};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); 
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	stb::pre();
	for(int i=1;i<=m;i++)
	{
		int t1,t2;
		cin>>t1>>t2;
		cout<<stb::getmax(t1,t2)<<endl; 
	}
	return 0;
}

线段树

洛谷P3373 模板 线段树II

如题，已知一个数列，你需要进行下面三种操作：

  • 将某区间每一个数乘上 xx

  • 将某区间每一个数加上 xx

  • 求出某区间每一个数的和

操作 11： 格式：1 x y k 含义：将区间 [x,y][x,y] 内每个数乘上 kk

操作 22： 格式：2 x y k 含义：将区间 [x,y][x,y] 内每个数加上 kk

操作 33： 格式：3 x y 含义：输出区间 [x,y][x,y] 内每个数的和对 pp 取模所得的值

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
#include<bits/stdc++.h>

#define endl '\n'

using namespace std;

const int maxn=100100;
const int modp=571373;

int n,m;
int a[maxn];

namespace sgt{
	
	struct segment_tree{
		int l,r,multag,addtag;
		int sum;
	}t[maxn<<2];
	
	#define lson i<<1,l,mid
	#define rson i<<1|1,mid+1,r
	#define ls (i<<1)
	#define rs (i<<1|1)
	
	void pushup(int i)
	{
		t[i].sum=(t[ls].sum+t[rs].sum)%modp;
	}
	
	void pushdown(int i)
	{
		t[ls].addtag=(1ll*t[ls].addtag*t[i].multag+t[i].addtag)%modp;
		t[rs].addtag=(1ll*t[rs].addtag*t[i].multag+t[i].addtag)%modp;
		t[ls].multag=(1ll*t[i].multag*t[ls].multag)%modp;
		t[rs].multag=(1ll*t[i].multag*t[rs].multag)%modp;
		t[ls].sum=(1ll*t[ls].sum*t[i].multag%modp+1ll*t[i].addtag*(t[ls].r-t[ls].l+1))%modp;
		t[rs].sum=(1ll*t[rs].sum*t[i].multag%modp+1ll*t[i].addtag*(t[rs].r-t[rs].l+1))%modp;
		t[i].addtag=0; t[i].multag=1;
	}
	
	void build_tree(int i,int l,int r)
	{
		t[i].l=l; t[i].r=r;
		t[i].multag=1;
		if(l==r)
		{
			t[i].sum=a[l];
			t[i].multag=1;
			return ;
		}
		int mid=(l+r)>>1;
		build_tree(lson);
		build_tree(rson);
		pushup(i);
	}
	
	void change_mul_tree(int i,int l,int r,int x,int y,int k)
	{
		if(l!=r) pushdown(i);
		if(l>=x&&r<=y)
		{
			t[i].sum=(1ll*t[i].sum*k)%modp;
			t[i].multag=k%modp;
			return ;
		}
		pushdown(i);
		int mid=(l+r)>>1;
		if(x<=mid) change_mul_tree(lson,x,y,k);
		if(y>mid) change_mul_tree(rson,x,y,k);
		pushup(i);
	}
	
	void change_add_tree(int i,int l,int r,int x,int y,int k)
	{
		if(l!=r) pushdown(i);
		if(l>=x&&r<=y)
		{
			t[i].sum=(1ll*t[i].sum+1ll*k*(r-l+1))%modp;
			t[i].addtag=k%modp;
			return ;
		}
		pushdown(i);
		int mid=(l+r)>>1;
		if(x<=mid) change_add_tree(lson,x,y,k);
		if(y>mid) change_add_tree(rson,x,y,k);
		pushup(i);		
	}
	
	int query_tree(int i,int l,int r,int x,int y)
	{
		int ans=0;
		if(l>=x&&r<=y)
		{
			return t[i].sum;
		}
		pushdown(i);
		int mid=(l+r)>>1;
		if(x<=mid) ans=(ans+query_tree(lson,x,y))%modp;
		if(y>mid) ans=(ans+query_tree(rson,x,y))%modp;
		return ans;
	}
	
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tmp;
	cin>>n>>m>>tmp;
	for(int i=1;i<=n;i++) cin>>a[i];
	sgt::build_tree(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int opt,t1,t2,t3;
		cin>>opt;
		if(opt==1)
		{
			cin>>t1>>t2>>t3;
			sgt::change_mul_tree(1,1,n,t1,t2,t3);	
		}
		if(opt==2)
		{
			cin>>t1>>t2>>t3;
			sgt::change_add_tree(1,1,n,t1,t2,t3);
		}
		if(opt==3)
		{
			cin>>t1>>t2;
			cout<<sgt::query_tree(1,1,n,t1,t2)<<endl;
		}
	}
	return 0;
}

平衡树(FHQ)

  1. 插入 xx 数
  2. 删除 xx 数(若有多个相同的数，因只删除一个)
  3. 查询 xx 数的排名(排名定义为比当前数小的数的个数 +1+1 )
  4. 查询排名为 xx 的数
  5. 求 xx 的前驱(前驱定义为小于 xx，且最大的数)
  6. 求 xx 的后继(后继定义为大于 xx，且最小的数)
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
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<ctime>
#include<cstdlib>

#define ls(i) c[(i)][0]
#define rs(i) c[(i)][1]

using namespace std;

const int maxn=2000100;

int c[maxn][2];
int a[maxn],rnd[maxn];
int rt,x,y,z;
int sz[maxn];
int val[maxn];
int tot,totans;
int n,m;

struct fhq{

	inline void pushup(int i)
	{
		sz[i]=sz[ls(i)]+sz[rs(i)]+1;
	}

	inline int new_node(int a)
	{
		val[++tot]=a;
		sz[tot]=1;
		rnd[tot]=rand();
		return tot;
	}

	void split(int t,int target,int &x,int &y)
	{
		if(!t) return void(x=y=0);
		if(val[t]>target)
		{
			y=t;
			split(ls(t),target,x,ls(t));
		}
		else
		{
			x=t;
			split(rs(t),target,rs(t),y);
		}
		pushup(t);
	}

	int merge(int x,int y)
	{
		if(!x||!y) return x^y;
		if(rnd[x]<rnd[y]) 
		{
			ls(y)=merge(x,ls(y));
			pushup(y);
			return y;
		}
		else
		{
			rs(x)=merge(rs(x),y);
			pushup(x);
			return x;
		}
	}

	inline int ins_tree(int target)
	{
		split(rt,target,x,y);
		rt=merge(x,new_node(target));
		rt=merge(rt,y);
		return rt;
	}

	inline void del_tree(int target)
	{
		int a,b;
		split(rt,target,x,z);
		split(x,target-1,x,y);
		y=merge(ls(y),rs(y));
		rt=merge(merge(x,y),z);
	}

	inline int kth(int t,int k)
	{
		int p=t;
		while(1)
		{
			if(k==0) return val[p];
			if(k==sz[ls(p)]+1) return val[p];
			if(sz[ls(p)]+1<k) k-=sz[ls(p)]+1,p=rs(p);
			else p=ls(p);
		}
	}

	inline int rk(int target)
	{
		split(rt,target-1,x,y);
		int ans=sz[x]+1;
		merge(x,y);
		return ans;
	}

	inline int pre(int target)
	{
		split(rt,target-1,x,y);
		int ans=kth(x,sz[x]);
		merge(x,y);
		return ans;
	}

	inline int nxt(int target)
	{
		split(rt,target,x,y);
		int ans=kth(y,1);
		merge(x,y);
		return ans;
	}

}fhq;

int main()
{
	srand(time(NULL));
	ios::sync_with_stdio(false);
	register int i,j;
	int t1,opt;
	cin>>n>>m;
	int lasans=0;
	for(i=1;i<=n;i++) cin>>t1,fhq.ins_tree(t1);
	for(i=1;i<=m;i++)
	{
		cin>>opt>>t1;
		t1^=lasans;
		if(opt==1)
		{
			fhq.ins_tree(t1);
		}
		if(opt==2)
		{
			fhq.del_tree(t1);
		}
		if(opt==3)
		{
			lasans=fhq.rk(t1);
			totans^=lasans;		
		}
		if(opt==4)
		{
			lasans=fhq.kth(rt,t1);
			totans^=lasans;
		}
		if(opt==5)
		{
			lasans=fhq.pre(t1);
			totans^=lasans;
		}
		if(opt==6)
		{
			lasans=fhq.nxt(t1);
			totans^=lasans;
		}
	}
	cout<<totans<<endl;
	return 0;
}

平衡树 Splay

旋转区间

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
#include<iostream>
using namespace std;
#define MAXN 1000007
#define INF 100000089
struct Splay_tree{
	int f,sub_size,cnt,value,tag;
	int son[2];
}s[MAXN];
int original[MAXN],root,wz;
inline bool which(int x){
	return x==s[s[x].f].son[1];
}
inline void update(int x){
	if(x){
	s[x].sub_size=s[x].cnt;
	if(s[x].son[0])s[x].sub_size+=s[s[x].son[0]].sub_size;
    if(s[x].son[1])s[x].sub_size+=s[s[x].son[1]].sub_size;
	}
}
inline void pushdown(int x){
    if(x&&s[x].tag){
    	s[s[x].son[1]].tag^=1;
    	s[s[x].son[0]].tag^=1;
    	swap(s[x].son[1],s[x].son[0]);
    	s[x].tag=0;
    }	
}
inline void rotate(int x){
	int fnow=s[x].f,ffnow=s[fnow].f;
	pushdown(x),pushdown(fnow);
	bool w=which(x);
	s[fnow].son[w]=s[x].son[w^1];
	s[s[fnow].son[w]].f=fnow;
	s[fnow].f=x;
	s[x].f=ffnow;
	s[x].son[w^1]=fnow;
	if(ffnow){
		s[ffnow].son[s[ffnow].son[1]==fnow]=x;
	}
	update(fnow);
}
inline void splay(int x,int goal){
	for(int qwq;(qwq=s[x].f)!=goal;rotate(x)){
		if(s[qwq].f!=goal){//这个地方特别重要，原因是需要判断的是当前的父亲有没有到目标节点，而如果把“qwq”改成“x”……就会炸 
			rotate(which(x)==which(qwq)?qwq:x);
		}
	}
	if(goal==0){
		root=x;
	}
}

int build_tree(int l, int r, int fa) {
        if(l > r) { return 0; }
        int mid = (l + r) >> 1;
        int now = ++ wz;
        s[now].f=fa;
	    s[now].son[0]=s[now].son[1]=0;
		s[now].cnt++;
    	s[now].value=original[mid];
		s[now].sub_size++;
        s[now].son[0] = build_tree(l, mid - 1, now);
        s[now].son[1] = build_tree(mid + 1, r, now);
        update(now);
        return now;
}
inline int find(int x){
	int now=root;
	while(1)
	{
	    pushdown(now);
		if(x<=s[s[now].son[0]].sub_size){
			now=s[now].son[0];
		}	
		else  {
		x-=s[s[now].son[0] ].sub_size + 1;
	    if(!x)return now;
	    now=s[now].son[1];
		}
	}
}
inline void reverse(int x,int y){
	int l=x-1,r=y+1;
	l=find(l),r=find(r);
	splay(l,0);
	splay(r,l);
	int pos=s[root].son[1];
	pos=s[pos].son[0];
	s[pos].tag^=1;
}
inline void dfs(int now){
	pushdown(now);
	if(s[now].son[0])dfs(s[now].son[0]);
	if(s[now].value!=-INF&&s[now].value!=INF){
		cout<<s[now].value<<" ";
	}
	if(s[now].son[1])dfs(s[now].son[1]);
}
int main(){
	int n,m,x,y;
	cin>>n>>m;
	original[1]=-INF,original[n+2]=INF;
	for(int i=1;i<=n;i++){
		original[i+1]=i;
	}
	root=build_tree(1,n+2,0);//有一个良好的定义变量习惯很重要……重复定义同一个变量（比如全局的和局部的同名）那么就会发生覆盖。 
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		reverse(x+1,y+1);
	}
	dfs(root);
}