【全程NOIP计划】初级数据结构2

树状数组

可以用于维护前缀信息（可合并）

优点：代码段，速度快

比如：

给定一个长n的数组，支持操作：

1.将第ii个数aia_i加vv

2.询问区间[l,r][l,r]中的数的和

lowbit(i)lowbit(i)：只保留ii的二进制表示中最低位的1

树状数组中，节点ii表示的区间为[i−lowbit(i)+1,i][i-lowbit(i)+1,i]

前缀查询

查询区间[1,i][1,i]的和的时候，由ii可以直接得到[i−lowbit(i)+1,i][i-lowbit(i)+1,i]的和，接下来查询[1,i−lowbit(i)][1,i-lowbit(i)]的区间和，重复上面的步骤就可以了

单点修改

修改ii的时候，寻找包含i的所有区间：

第一个包含ii且lowbitlowbit比ii大的节点是i+lowbit(i)i+lowbit(i)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int y)
{
    for( ;x<=n;x+=lowbit(x)) c[x]+=y;
}
int ask(int x)
{
    int res=0;
    for( ;x;x-=lowbit(x))
        res+=c[x];
    return res;
}
差分

实际上就是用树状数组维护一下差分序列的前缀和就行

区间修改

将区间[l,r][l,r]内的数全加v，或者查询[l,r][l,r]内数的和

考虑用差分数组来表示[1,R][1,R]的前缀和
∑k=1Rak=∑k=1R∑i=1kdi=∑i=1R∑k=iRdi=∑i=1R(R−i+1)di=(R+1)∑i=1Rdi−∑i=1Ridi \sum_{k=1}^Ra_k=\sum_{k=1}^R \sum_{i=1}^kd_i \\ =\sum_{i=1}^R \sum_{k=i}^Rd_i \\ =\sum_{i=1}^R(R-i+1)d_i=(R+1)\sum_{i=1}^Rd_i-\sum_{i=1}^Rid_i

逆序对

题目

给定序列，求有多少对逆序对

思路

对于每个i，它的前面有多少个数比它大

先离散化，对值域建树状数组

然后从左往右扫描一次，在每个位置需要查询权值的前缀和，然后把这个数加入树状数组

时间复杂度O(nlogn)O(nlogn)

二维树状数组

给定n*m的矩阵ai,ja_{i,j},有qq次操作，每次操作修改某个元素或者查询某个子矩阵的和

记录bi,jb_{i,j}表示从(i−lowbit(i)+1,j−lowbit(j)+1)(i-lowbit(i)+1,j-lowbit(j)+1)到(i,j)(i,j)的子矩阵的和

查询和修改的时候，先枚举第一维，再枚举第二维

时间复杂度O(Qlogn logm)O(Qlogn \space logm)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void update(int x,int y,int z)
{
    for(int i=x;i<=n;i+=lowbit(i))
    {
        for(int j=y;j<=m;j+=lowbit(j))
            b[i][j]+=z;
    }
}
int query(int x,int y)
{
    int res=0;
    for(int i=x;i>0;i-=lowbit(i))
    {
        for(int j=y;j>0;j-=lowbit(j))
            res+=b[i][j];
    }
    return res;
}

线段树

可以用于维护区间信息

比如：

维护长为n的序列：

包括单点修改，区间查询等操作

线段树的形式是一颗二叉树，每个节点维护一段区间的信息

根节点为[1,n][1,n]

对于节点[L,R][L,R]，设中点mid=⌊L+R2⌋mid=\lfloor \dfrac {L+R} 2 \rfloor,把该节点从mid处分开，左边的子节点为[L,mid][L,mid]，右边的子节点为[mid+1,R][mid+1,R]

树高O(logn)O(log n)，总结点数2n-1

对于节点x。左儿子为2x,右儿子则为2x-1

建树

根节点为[1,n][1,n]，考虑根节点为[L,R][L,R]的时候：

设mid=(l+r)/2，对于区间[L,mid],[mid+1,R][L,mid],[mid+1,R]递归建树

合并两个区间的信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int a[N], mx[N << 2];
void update(int x, int L, int R) {
    if(L != R) {
        mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
    }
}
void build(int x, int L, int R) {
    if(L == R) {
        mx[x] = a[L];
        return;
    }
    int mid = (L + R) >> 1;
    build(x << 1, L, mid);
    build(x << 1 | 1, mid + 1, R);
    update(x, L, R);
}
单点修改/查询

单点查询：从上向下找到对应的叶子节点

单点修改：先修改叶子节点，然后从下往上向上更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int query(int x, int L, int R, int p) {
    if(L == R) return mx[x];
    int mid = (L + R) >> 1;
    if(p <= mid) return query(x << 1, L, mid, p);
    else return query(x << 1 | 1, mid + 1, R, p);
}
int modify(int x, int L, int R) {
    if(L == R) {
        mx[x] = v;
        return;
    }
    int mid = (L + R) >> 1;
    if(p <= mid) modify(x << 1, L, mid, p, v);
    else modify(x << 1 | 1, mid + 1, R, p, v);
    update(x, L, R);
}
区间查询

查询区间[l,r][l,r]的时候，可以最多拆成2log n2log \space n个不相交区间，合并这些区间可以得到答案

从线段树从上往下找答案

区间修改

对区间[l,r][l,r]加vv，同样可以拆成最多2log n2log\space n个区间，并修改这些区间

在一个节点做区间修改的时候，不立刻修改它的子节点

记录懒标记：每个节点x记录还没有加到子树中的值的总和

查询经过某节点的时候，将懒标记下放给它的两个儿子

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
int mx[N << 2], sum[N << 2], tag[N << 2];
void update(int x) {
    mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
}
void pushdown(int x, int L, int R) {
    if(tag[x] == 0) return;
    sum[x] += tag[x] * (R - L + 1);
    mx[x] += tag[x];
    if(L != R) {
        tag[x << 1] += tag[x];
        tag[x << 1 | 1] += tag[x];
    }
    tag[x] = 0;
}
// a[l...r] += v
void modify(int x, int L, int R, int l, int r, int v) {
    pushdown(x, L, R);
    if(L == l && R == r) {
        tag[x] += v;
        pushdown(x, L, R);
        return;
    }
    int mid = (L + R) >> 1;
    if(r <= mid) modify(x << 1, L, mid, l, r, v);
    else if(l > mid) modify(x << 1 | 1, mid+1, R, l, r, v);
    else{
        modify(x << 1, L, mid, l, mid, v);
        modify(x << 1 | 1, mid+1, R, mid+1, r, v);
    }
    update(x);
}
标记永久化
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
// -------------- 标记永久化 ---
void modify(int x, int L, int R, int l, int r, int v) {
    if(L == l && R == r) {
        tag[x] += v;
        sum[x] += tag[x] * (R - L + 1);
        mx[x] += tag[x];
        return;
    }
    int mid = (L + R) >> 1;
    if(r <= mid) modify(x << 1, L, mid, l, r, v);
    else if(l > mid) modify(x << 1 | 1, mid+1, R, l, r, v);
    else{
        modify(x << 1, L, mid, l, mid, v);
        modify(x << 1 | 1, mid+1, R, mid+1, r, v);
    }
    update(x, L, R);
}
int query(int x, int L, int R, int l, int r, int cur) {
    if(l == L && r == R)
        // return mx[x] + cur;
        return sum[x] + cur * (r - l + 1);
    cur += tag[x];
    int mid = (L + R) >> 1;
    if(r <= mid) return query(x << 1, L, mid, l, r, cur);
    else if(l > mid) return query(x << 1 | 1, mid + 1, R, l, r, cur);
    else{
        int u = query(x << 1, L, mid, l, mid, cur);
        int v = query(x << 1 | 1, mid + 1, R, mid + 1, r, cur);
        // return max(u, v);
        return u + v;
    }
}

P2023 维护序列

思路

实际上就是多一个乘法标记，跟线段树2差不多，就一板子

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int maxn=100010;
int p;
int a[maxn+5];
struct tree{
	int l,r;
	long long dat,lazy,mul;
}t[maxn*4+5];
void pushup(int k)
{
	t[k].dat=(t[k<<1].dat+t[k<<1|1].dat)%p;
}
void build(int k,int l,int r)
{
	t[k].lazy=0,t[k].mul=1;
	t[k].l=l,t[k].r=r;
	if(l==r)
	{
		t[k].dat=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	pushup(k);
}
void pushdown(int k)
{
		t[k<<1].dat=(t[k<<1].dat*t[k].mul+t[k].lazy*(t[k<<1].r-t[k<<1].l+1))%p;
		t[k<<1|1].dat=(t[k<<1|1].dat*t[k].mul+t[k].lazy*(t[k<<1|1].r-t[k<<1|1].l+1))%p;
		t[k<<1].mul=(t[k<<1].mul*t[k].mul)%p;
		t[k<<1|1].mul=(t[k<<1|1].mul*t[k].mul)%p;
		t[k<<1].lazy=(t[k<<1].lazy*t[k].mul+t[k].lazy)%p;
		t[k<<1|1].lazy=(t[k<<1|1].lazy*t[k].mul+t[k].lazy)%p;
		t[k].mul=1;
		t[k].lazy=0;
}
void updata(int k,int l,int r,int v)
{
	if(l<=t[k].l&&r>=t[k].r)
	{
		t[k].dat=(t[k].dat+(long long)v*(t[k].r-t[k].l+1))%p;
		t[k].lazy=(t[k].lazy+v)%p;
		return ;
	}
	pushdown(k);
	int mid=(t[k].l+t[k].r)>>1;
	if(l<=mid)
	updata(k<<1,l,r,v);
	if(r>mid)
	updata(k<<1|1,l,r,v);
	pushup(k);
}
void updata2(int k,int l,int r,int v)
{
	if(l<=t[k].l&&r>=t[k].r)
	{
		t[k].dat=(t[k].dat*v)%p;
		t[k].lazy=(t[k].lazy*v)%p;
		t[k].mul=(t[k].mul*v)%p;
		return ;
	}
	pushdown(k);
	int mid=(t[k].l+t[k].r)>>1;
	if(l<=mid)
	updata2(k<<1,l,r,v);
	if(r>mid)
	updata2(k<<1|1,l,r,v);
	pushup(k);
}
long long query(int k,int l,int r)
{
	if(l<=t[k].l&&r>=t[k].r)
	return t[k].dat;
	pushdown(k);
	int mid=(t[k].l+t[k].r)>>1;
	long long ans=0%p;
	if(l<=mid)
	ans+=query(k<<1,l,r)%p;
	if(r>mid)
	ans+=query(k<<1|1,l,r)%p;
	return ans%p;
}
int main()
{
	std::ios::sync_with_stdio(false);
	int n,m;
	cin>>n>>p;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	cin>>m;
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int o;
		cin>>o;
		if(o==1)
		{
			int x,y,k;
			cin>>x>>y>>k;
			updata2(1,x,y,k);
			continue;
		}
		if(o==2)
		{
			int x,y,k;
			cin>>x>>y>>k;
			updata(1,x,y,k);
			continue;
		}
		if(o==3)
		{
			int x,y;
			cin>>x>>y;
			cout<<query(1,x,y)<<'\n';
		}
	}
	return 0;
}

P4513 小白逛公园

思路

在每个节点处维护：

区间最大字段和，区间最大前缀和和区间最大后缀和

合并的时候分类讨论就好了

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 <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int maxn=500005;
int n,m;
int a[maxn];
struct tree{
	int l,r;
	int sum,lmax,rmax,maxx;
}t[maxn*4];
void pushup(int k)
{
	t[k].sum=t[k<<1].sum+t[k<<1|1].sum;
	t[k].lmax=max(t[k<<1].sum+t[k<<1|1].lmax,t[k<<1].lmax);
	t[k].rmax=max(t[k<<1|1].sum+t[k<<1].rmax,t[k<<1|1].rmax);
	t[k].maxx=max(max(t[k<<1].maxx,t[k<<1|1].maxx),t[k<<1].rmax+t[k<<1|1].lmax);
}
void build(int k,int l,int r)
{
	t[k].l=l,t[k].r=r;
	if(l==r)
	{
		t[k].sum=t[k].lmax=t[k].rmax=t[k].maxx=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	pushup(k);
}
void update(int k,int p,int v)
{
	if(t[k].l==t[k].r)
	{
		t[k].sum=t[k].lmax=t[k].rmax=t[k].maxx=v;
		return ;
	}
	int mid=(t[k].l+t[k].r)>>1;
	if(mid>=p)
	update(k<<1,p,v);
	else
	update(k<<1|1,p,v);
	pushup(k);
}
tree query(int k,int l,int r)
{
	if(l<=t[k].l&&t[k].r<=r)
	return t[k];
	int mid=(t[k].l+t[k].r)>>1;
	if(r<=mid)
	return query(k<<1,l,r);
	else if(l>mid)
	return query(k<<1|1,l,r);
	else
	{
		tree x=query(k<<1,l,r);
		tree y=query(k<<1|1,l,r);
		tree merge;
		merge.sum=x.sum+y.sum;
		merge.lmax=max(x.sum+y.lmax,x.lmax);
		merge.rmax=max(y.sum+x.rmax,y.rmax);
		merge.maxx=max(max(x.maxx,y.maxx),x.rmax+y.lmax);
		return merge;
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int a,b;
			cin>>a>>b;
			if(a>b) swap(a,b);
			tree ans=query(1,a,b);
			cout<<ans.maxx<<'\n';
		}
		else
		{
			int p,s;
			cin>>p>>s;
			update(1,p,s); 
		}
	}
	return 0;
}

P2894 Hotel

思路

线段树

类似上一道题目

在每个节点处维护：

区间内最长全0的长度，最长全0前缀和最长全0后缀

查询时，在线段树上二分找到最靠前的答案

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int maxn=500005;
int n,m;
struct tree{
	int sum;
	int len;
	int lmax,rmax;
	int lazy;
}t[maxn*4];
void pushup(int k)
{
	if(t[k<<1].sum==t[k<<1].len)
	t[k].lmax=t[k<<1].len+t[k<<1|1].lmax;
	else 
	t[k].lmax=t[k<<1].lmax;
	
	if(t[k<<1|1].sum==t[k<<1|1].len)
	t[k].rmax=t[k<<1|1].len+t[k<<1].rmax; 
	else 
	t[k].rmax=t[k<<1|1].rmax;
	
	t[k].sum=max(max(t[k<<1].sum,t[k<<1|1].sum),t[k<<1].rmax+t[k<<1|1].lmax);
} 
void pushdown(int k)
{
	if(t[k].lazy==0)
	return;
	if(t[k].lazy==1)
	{
	    t[k<<1].lazy=t[k<<1|1].lazy=1;
		t[k<<1].sum=t[k<<1].lmax=t[k<<1].rmax=0;
		t[k<<1|1].sum=t[k<<1|1].lmax=t[k<<1|1].rmax=0;
	}
	if(t[k].lazy==2)
	{
		t[k<<1].lazy=t[k<<1|1].lazy=2;
		t[k<<1].sum=t[k<<1].lmax=t[k<<1].rmax=t[k<<1].len;
		t[k<<1|1].sum=t[k<<1|1].lmax=t[k<<1|1].rmax=t[k<<1|1].len;
	}
	t[k].lazy=0;
}
void build(int k,int l,int r)
{
	t[k].lazy=0;
	t[k].sum=t[k].len=t[k].lmax=t[k].rmax=r-l+1;
	if(l==r)
	return;
	int mid=(l+r)/2;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r); 
}
void update(int k,int l,int r,int tag,int L,int R)
{
	pushdown(k);
	if(L<=l&&r<=R)
	{
    	if(tag==1)t[k].sum=t[k].lmax=t[k].rmax=0;
		else t[k].sum=t[k].lmax=t[k].rmax=t[k].len; 
		t[k].lazy=tag;
		return;
	}
	int mid=(l+r)/2;
	if(L<=mid)
	update(k<<1,l,mid,tag,L,R);
	if(R>mid)
	update(k<<1|1,mid+1,r,tag,L,R);
	pushup(k);
}
int query(int k,int l,int r,int length)
{
	pushdown(k);
	if(l==r)return l;
	int mid=(l+r)/2;
	if(t[k<<1].sum>=length)
	return query(k<<1,l,mid,length);
	if(t[k<<1].rmax+t[k<<1|1].lmax>=length)
	return mid-t[k<<1].rmax+1;
	else 
	return query(k<<1|1,mid+1,r,length);
}
int main()
{
	cin>>n>>m;
	build(1,1,n);
	for(int i=1;i<=m;i++) 
	{
		int op,x,y;
		cin>>op;
		if(op==1)
		{
			cin>>x;
			if(t[1].sum>=x)
			{
				int l=query(1,1,n,x);
				cout<<l<<'\n';
				update(1,1,n,1,l,l+x-1);
			}
			else
			cout<<0<<'\n';
		}
		else
		{
			cin>>x>>y;
			update(1,1,n,2,x,x+y-1);
		}
	}
	return 0;
}

P5490 扫描线

思路

一个扫描线的模板

离散化坐标，并按照x从小到大的顺序扫描

每一步加入或者删除一个矩形（一根线段），线段树维护被覆盖部分

维护被覆盖的面基，节点记录：

实际区间长度，被覆盖部分长度，最小值，最小值部分长度

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
const int maxn=1e6+5;
int n;
long long x1,y1,x2,y2;
long long x[maxn*2];
struct scanline{
	long long l,r,h;
	int mark;
	bool operator < (const scanline &rhs) const
	{
		return h<rhs.h;
	}
}line[maxn*2];
struct tree{
	int l,r;
	int sum;
	long long len;
}t[maxn*4];
void pushup(int k)
{
	if(t[k].sum)
	t[k].len=x[t[k].r+1]-x[t[k].l];
	else
	t[k].len=t[k<<1].len+t[k<<1|1].len;
}
void build(int k,int l,int r)
{
	t[k].l=l,t[k].r=r;
	t[k].len=0;
	t[k].sum=0;
	if(l==r)
	return ;
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
}
void edit_tree(int k,long long l,long long r,int c)
{
	if(x[t[k].r+1]<=l||r<=x[t[k].l])
	return ;
	if(l<=x[t[k].l]&&x[t[k].r+1]<=r)
	{
		t[k].sum+=c;
		pushup(k);
		return ;
	}
	edit_tree(k<<1,l,r,c);
	edit_tree(k<<1|1,l,r,c);
	pushup(k);
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x1>>y1>>x2>>y2;
		x[2*i-1]=x1,x[2*i]=x2;
		line[2*i-1]=(scanline){x1,x2,y1,1};
		line[2*i]=(scanline){x1,x2,y2,-1};
	}
	n<<=1;
	sort(line+1,line+1+n);
	sort(x+1,x+1+n);
	//离散化 
	int tot=unique(x+1,x+1+n)-x-1;
	build(1,1,tot-1);
	long long ans=0;
	for(int i=1;i<n;i++)
	{
		edit_tree(1,line[i].l,line[i].r,line[i].mark);
		
		ans+=t[1].len*(line[i+1].h-line[i].h);
	}
	cout<<ans<<endl;
	return 0;
}

线段树的可持久化

可持久化：支持保存和访问数据结构历史版本

可持久化线段树

在单次修改之后，产生变化的节点只有O(log n)O(log \space n)个

只需要为这些节点开辟新的空间

不能用堆式编号，需要记录子树节点编号，并动态开点，区间操作需要标记永久化，单次操作的时间和空间复杂度为O(log n)O(log \space 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
const int maxn=100005;
struct node{
    int l,r;
    int sum,ls,rs;
}a[20*maxn];
int cnt,root[maxn];//root代表每次操作之后的根节点
void modify(int &x,int L,int R,int p,int v)//把p位置修改成v
{
    if(!x)
        x=++cnt;//如果x还没有开，那就新开一个点
    if(L==R)
    {
        a[x].sum=v;
        return ;
    }
    int mid=(L+R)>>1;
    if(p<=mid)
        modify(a[x].ls,L,mid,p,v);
    else
        modify(a[x].rs,mid+1,R,p,v);
    a[x].sum=a[a[x].ls].sum+a[a[x].rs].sum;//合并信息
}
int query(int x,int L,int R,int l,int r)
{
    if(x==0)
         return 0;
    if(l==L&&r==R)
        return a[x].sum;
    int mid=(L+R)>>1;
    if(r<=mid)
        return query(a[x].ls,L,mid,l,r);
    else if(l>mid)
        return query(a[x].rs,mid+1,R,l,r);
    else
    {
        int u=query(a[x].ls,L,mid,l,mid);
        int v=query(a[x].rs,mid+1,R,mid+1,r);
        return u+v;
    }
}
int main() 
{
    for(int i=1; i<=Q; i++) 
    {
        root[i] = root[i-1];
        modify(root[i], 1, n, p, v);
    }
    return 0;
}
可持久化并查集

用持久化也可以实现可持久化并查集

P3834 可持久化线段树（模板）

思路

考虑区间是[1,n][1,n]的情况：

1.离散化之后建立值域线段树，区间[L,R][L,R]保存落在[L,R][L,R]内的数的个数

2.在线段树上二分找到第k大的值

3.如果左子树的总和≤k\le k，则向左子树走，否则向右子树走

主席树

区间[L,R][L,R]的值域线段树，可以用[1,R],[1,L−1][1,R],[1,L-1]的相减得到

暴力：开n棵线段树，时间复杂度为O(n2)O(n^2)

1.将第i棵线段树在第i-1棵线段树的基础上修改了一个值

2.将线段树可持久化，一共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
53
int query_kth(int x,int L,int R,int k)
{
    if(L==R)
        return L;
    int mid=(L+R)>>1;
    int =a[a[x].ls].sum-a[a[y].ls].sum;
    if(s>=k)
        return query(a[x].ls,L,mid,k);
    else
        return query(a[x].rc,mid+1,R,k-s);
}

//其他的

const int N = 100005;
struct Node{
    int lc, rc, sum;
}a[20 * N];
int cnt, root[N];
// a[p] = v;
void modify(int& x, int L, int R, int p, int v) {
    a[++cnt] = a[x];
    x = cnt;
    if(L == R) {
        a[x].sum = v;
        return;
    }
    int mid = (L + R) >> 1;
    if(p <= mid) modify(a[x].lc, L, mid, p, v);
    else modify(a[x].rc, mid+1, R, p, v);
    a[x].sum = a[a[x].lc].sum + a[a[x].rc].sum;     // a[0].sum = 0;
}
int query(int x, int L, int R, int l, int r) {
    if(x == 0) return 0;
    if(l == L && r == R) return a[x].sum;
    int mid = (L + R) >> 1;
    if(r <= mid) return query(a[x].lc, L, mid, l, r);
    else if(l > mid) return query(a[x].rc, mid + 1, R, l, r);
    else{
        int u = query(a[x].lc, L, mid, l, mid);
        int v = query(a[x].rc, mid + 1, R, mid + 1, r);
        return u + v;
    }
}
int main() {
    for(int i=1; i<=Q; i++) {
        root[i] = root[i-1];
        modify(root[i], 1, n, p, v);
        // root[i] = ++cnt
    }
    // query(root[i], 1, n, l, r);
    return 0;
}

P4216 情报传递

思路

得到一个路径的主席树

综合练习

P4145 花神游历各国

思路

注意到每个数最多开根6次后就会变成1

方法1：

在线段树上暴力开根，把全都是1的区间打上标记

方法2：

树状数组暴力单点修改，在修改的时候跳过所有的1，可以使用并查集来实现

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
const int maxn=100005;
long long n,m;
long long a[maxn],b[maxn];
bool vis[maxn]={false};
long long fa[maxn];
long long get(long long x)
{
	return fa[x]=(x==fa[x]? x:get(fa[x]));
}
void init()
{
	for(int i=1;i<=maxn-5;i++)
	fa[i]=i;
}
inline long long read()
{
	long long x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
long long lowbit(long long x)
{
	return x&(-x);
}
void add(long long x,long long y)
{
	for( ;x<=n;x+=lowbit(x))
	b[x]+=y; 
}
long long ask(long long x)
{
	long long res=0;
	for( ;x;x-=lowbit(x))
	res+=b[x];
	return res;
}
int main()
{
	init();
	n=read();
	for(register long long i=1;i<=n;i++)
	{
		a[i]=read();
		add(i,a[i]);
	}
	fa[n+1]=n+1;
	m=read();
	while(m--)
	{
		int k=read(),l=read(),r=read();
		if(l>r) swap(l,r);
		if(k==0)
		{
			long long t;
			for(int i=l;i<=r;add(i,(t=(int)sqrt(a[i]))-a[i]),a[i]=t,fa[i]=(a[i]<=1)?i+1:i,i=(get(i)==i)?i+1:fa[i]);
		}
		else
		{
			cout<<ask(r)-ask(l-1)<<'\n';
		}
	}
	return 0;
}

P1972 HH的项链

思路

离线询问，从左往右考虑每个下标ii，并处理右端点ii的询问

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int maxn=1000005;
int n,m;
int a[maxn],b[maxn];
int vis[maxn],ans[maxn];
struct qyj{
	int l,r;
	int id;
}q[maxn];
int lowbit(int x)
{
	return x&(-x);
}
void add(int x,int y)
{
	for( ;x<=n;x+=lowbit(x))
	b[x]+=y;
}
int ask(int x)
{
	int res=0;
	for( ;x; x-=lowbit(x))
	res+=b[x];
	return res;
}
bool cmp(qyj x,qyj y)
{
	return x.r<y.r; 
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>q[i].l>>q[i].r;
		q[i].id=i;
	}
	sort(q+1,q+1+m,cmp);
	int pow=1;
	for(int i=1;i<=m;i++)
	{
		for(int j=pow;j<=q[i].r;j++)
		{
			if(vis[a[j]])
			add(vis[a[j]],-1);
			add(j,1);
			vis[a[j]]=j;
		}
		pow=q[i].r+1;
		ans[q[i].id]=ask(q[i].r)-ask(q[i].l-1);
	}
	for(int i=1;i<=m;i++)
	cout<<ans[i]<<'\n';
	return 0;
}

P4587 神秘数

思路

如果没有区间查询：

从小到大考虑每一个数，设当前能表示出[1,x][1,x]的数

如果下一个数ai≥x+2a_i \ge x+2，则答案是x+1x+1

否则，能表示的数的范围则扩充到[1,x+ai][1,x+a_i]

优化扩充的过程：设一个last，表示用≤last\le last的数凑出的范围是[1,x][1,x]

如果下一个数>x+1>x+1,则答案就是x+1x+1

否则，求出所有在[last+1,x][last+1,x]之间的数的和sumsum

则xx增加到x+sumx+sum，lastlast增加到原来的xx

扩充不超过O(log(∑ai))O(log(\sum a_i))步（斐波那契）

然后主席树实现查询

总的时间复杂度为O(mlog n log(∑ai))O(mlog \space n \space log(\sum a_i))

P1712 区间

思路

按照区间长度排序，双指针扫一遍

线段树区间加，维护区间最大值

时间复杂度O(nlogn)O(nlogn)