知识汇总-数据结构进阶

并查集,树状数组,线段树,字符串(ac自动机,后缀数组)
待更新:分块,点分治,cdq,可持久化trie,可持久化线段树

并查集

1
2
3
4
5
6
int find(int n){
return n==f[n]? n: f[n] = find(f[n]);
}
void merge(int x,int y){
f[find(x)] = find(y);
}

并查集

  • 带权并查集一般维护x到f[x]之间的关系

带权并查集

奇偶游戏-带权并查集

食物链-扩展域并查集and种类并查集

树状数组

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
//一维
void add(int x, ll y){
for(;x<=n;x += x&-x) c[x] += y;
}
ll query(int x){
ll ans = 0;
for(;x;x -= x&-x) ans += c[x];
return ans;
}

//二维
int lowbit(int x){return x & -x;}
void update(int n,int m,int t){
for(int i=n;i<=s;i+=lowbit(i))
for(int j=m;j<=s;j+=lowbit(j))
tree[i][j]+=t;
}
int sum(int n,int m){
int cnt=0;
for(int i=n;i>0;i-=lowbit(i))
for(int j=m;j>0;j-=lowbit(j))
cnt+=tree[i][j];
return cnt;
}

//逆序数
int main(){
while(~scanf("%d",&n)&&n){
INIT(c,0);
rep(i,1,n) {
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+1,b+1+n);
m=unique(b+1,b+1+n)-b-1;
ll ans=0;
repd(i,n,1){
int t=lower_bound(b+1,b+1+m,a[i])-b;
ans+=query(t-1);
add(t,1);
}
printf("%lld\n",ans);
}
return 0;
}

//二维偏序,维护左下角最值
sort(p+1,p+q+1,cmp); //按其中一维排序
for(int i=1,now;i<=q;i++) {
now=query(p[i].y)+p[i].val;
ans=max(ans,now);
add(p[i].y,now);
}

区间修改单点查询

区间修改区间查询

区间最值

线段树

懒是第一生产力

区间最大子段和

区间最大公约数

字符串

AC自动机

模板三巨头

后缀数组

后缀数组及其应用

Donate comment here