基础操作

线段树是一种基于分治思想的二叉树结构，用于在区间上进行统计。每个节点代表一个区间，对于每个内部节点[l,r]（编号p），左子节点代表区间[l,mid]（编号2p），右子节点代表区间[mid+1,r]（编号2p+1）.可以用结构体数组保存一棵线段树，数组大小开到N*4
在这里插入图片描述

P2068 统计和

定义线段树

1
2
3
4
5
struct segment_tree
{
	int l,r;
	long long sum;
}tree[100010*4];

建树

1
2
3
4
5
6
7
8
9
void build(int p,int l,int r)
{
	tree[p].l=l,tree[p].r=r,tree[p].sum=0;
	if(l==r) return;//到达根节点 
	int mid=(l+r)/2;
	build(p*2,l,mid);//左子树 
	build(p*2+1,mid+1,r);//右子树 
}

单点修改

1
2
3
4
5
6
7
8
9
10
11
12
13
void change(int p,int x,int v)
{
	if(tree[p].l==tree[p].r)//到达对应单点（左右端点值都为x） 
	{
		tree[p].sum+=v;//修改 
		return;
	}
	int mid=(tree[p].l+tree[p].r)/2;
	if(x<=mid) change(p*2,x,v);//单点在左子树 
	else change(p*2+1,x,v);//单点在右子树 
	tree[p].sum=(tree[p*2].sum+tree[p*2+1].sum);//合并 
}

区间查询

假设当前询问的区间为[l,r]
递归到一个区间[tl,tr]时,有四种情况：

  1. $l<=tl<=tr<=r$,该区间被完全覆盖在询问区间内，直接返回[tr,tl]上的和；
  2. $tl<=l<=tr<=r$,当前区间的右边一部分在询问区间内，判断l与mid=(tr+tl)/2的大小关系，若l>mid，只需递归右子树，否则需要递归左右子树（右子树会在递归后直接返回）
  3. $l<=tl<=r<=tr$,参考上一条
  4. $tr<=l<=r<=tr$，递归左右子树
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    long long ask(int p,int l,int r)
    {
        if(l<=tree[p].l&&r>=tree[p].r) 
    		return tree[p].sum;//如果整个区间被覆盖，就返回维护的值
        int mid=(tree[p].l+tree[p].r)>>1;
        long long ans=0;
        if(l<=mid) ans+=ask(p*2,l,r);
        if(r>mid) ans+=ask(p*2+1,l,r);//累加答案，返回左右儿子的和
        return ans;
    }

完整代码

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

struct segment_tree
{
	int l,r;
	long long sum;
}tree[100010*4];

void build(int p,int l,int r)
{
	tree[p].l=l,tree[p].r=r,tree[p].sum=0;
	//cout<<"p:"<<p<<" l:"<<l<<" r:"<<r<<endl;
	if(l==r) return;//到达根节点 
	int mid=(l+r)/2;
	build(p*2,l,mid);//左子树 
	build(p*2+1,mid+1,r);//右子树 
}

void change(int p,int x,int v)
{
	if(tree[p].l==tree[p].r)//到达对应单点（左右端点值都为x） 
	{
		tree[p].sum+=v;//修改 
		return;
	}
	int mid=(tree[p].l+tree[p].r)/2;
	if(x<=mid) change(p*2,x,v);//单点在左子树 
	else change(p*2+1,x,v);//单点在右子树 
	tree[p].sum=(tree[p*2].sum+tree[p*2+1].sum);//合并 
}

long long ask(int p,int l,int r)
{
    if(l<=tree[p].l&&r>=tree[p].r) 
		return tree[p].sum;//如果整个区间被覆盖，就返回维护的值
    int mid=(tree[p].l+tree[p].r)>>1;
    long long ans=0;
    if(l<=mid) ans+=ask(p*2,l,r);
    if(r>mid) ans+=ask(p*2+1,l,r);//累加答案，返回左右儿子的和
    return ans;
}
int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		char c; int x,y;
		cin>>c>>x>>y;
		if (c=='x') change(1,x,y);//单点修改 
		if (c=='y') printf("%lld\n",ask(1,x,y));//区间查询 
	}
	return 0;
}

P1198 [JSOI2008] 最大数

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

const int N=200010;
int m,mod,now=0;
long long temp;
int t[N*4];

void insert(int p,int l,int r,int x)
{
	if(l==r)
	{
		t[p]=x;
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=now) insert(p*2,l,mid,x);
	if(mid<now) insert(p*2+1,mid+1,r,x);
	t[p]=max(t[p*2],t[p*2+1])%mod;
}

int ask(int p,int l,int r,int ll,int rr)
{
	if(ll<=l&&rr>=r)
		return t[p];
	int mid=(l+r)/2;
	int maxn=-0x3ffffff;
	if(mid>=ll) maxn=max(maxn,ask(p*2,l,mid,ll,rr));
	if(mid<rr) maxn=max(maxn,ask(p*2+1,mid+1,r,ll,rr));
	return maxn;
}

int main()
{
	cin>>m>>mod;
	for(int i=0;i<m;i++)
	{
		char op;
		cin>>op;
		if(op=='A')
		{
			++now;
			int x;
			scanf("%d",&x);
			int a=(x+temp)%mod;
			insert(1,1,m,a);
		}
		if(op=='Q')
		{
			int len;
			scanf("%d",&len);
			if(len==0) temp=0;
			else temp=ask(1,1,m,now-len+1,now)%mod;
			cout<<temp<<'\n';
		}
		//cout<<"now:"<<now<<" temp:"<<temp<<endl;
		//cout<<"t[1].val:"<<t[1]<<"t[2].val:"<<t[2]<<"t[3].val:"<<t[3]<<endl;
	}
    return 0;
}


P1471 方差

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
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
double a[N];
struct Node
{
	int l,r;
	double sum,total,add;
}tr[N*4];

void pushdown(int u)
{
	tr[u<<1].total+=2*tr[u<<1].sum*tr[u].add+(tr[u<<1].r-tr[u<<1].l+1)*tr[u].add*tr[u].add;
	tr[u<<1].sum+=(tr[u<<1].r-tr[u<<1].l+1)*tr[u].add;
	tr[u<<1].add+=tr[u].add;
	tr[u<<1|1].total+=2*tr[u<<1|1].sum*tr[u].add+(tr[u<<1|1].r-tr[u<<1|1].l+1)*tr[u].add*tr[u].add;
	tr[u<<1|1].sum+=(tr[u<<1|1].r-tr[u<<1|1].l+1)*tr[u].add;
	tr[u<<1|1].add+=tr[u].add;
	tr[u].add=0;
}

void build(int u,int l,int r)
{
	if(l==r)
	{
		tr[u]={l,r,a[l],a[l]*a[l],0};
		return;
	}
	else
	{
		tr[u].l=l,tr[u].r=r;
		int mid=l+r>>1; 
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
		tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
		tr[u].total=tr[u<<1].total+tr[u<<1|1].total;
	}
}

void modify(int u,int l,int r,double v)
{
	if(l<=tr[u].l&&tr[u].r<=r)
	{
		tr[u].total+=2*tr[u].sum*v+(tr[u].r-tr[u].l+1)*v*v;
		tr[u].sum+=(tr[u].r-tr[u].l+1)*v;
		tr[u].add+=v;
	}
	else
	{
		pushdown(u);
		int mid=tr[u].l+tr[u].r>>1;
		if(l<=mid) modify(u<<1,l,r,v); 
		if(r>mid) modify(u<<1|1,l,r,v);
		tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
		tr[u].total=tr[u<<1].total+tr[u<<1|1].total;
	}
}

Node query(int u,int l,int r)
{
	if(l<=tr[u].l&&tr[u].r<=r) return tr[u];
	pushdown(u);
	int mid=tr[u].l+tr[u].r>>1;
	Node res,tmp;
	res.sum=0,res.total=0;
	if(l<=mid) tmp=query(u<<1,l,r),res.total+=tmp.total,res.sum+=tmp.sum;
	if(r>mid) tmp=query(u<<1|1,l,r),res.total+=tmp.total,res.sum+=tmp.sum;
	return res;
}


int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%lf",&a[i]);
	memset(tr,0,sizeof(tr));
	build(1,1,n);
	while(m--)
	{
		int op;
		scanf("%d",&op);
		if(op==1)
		{
			int l,r;
			double v;
			scanf("%d%d%lf",&l,&r,&v);
			modify(1,l,r,v);
		}
		else
		{
			int l,r;
			scanf("%d%d",&l,&r);
			Node t1=query(1,l,r);
			double ave=t1.sum*1.0/(r-l+1);
			double s=t1.total*1.0/(r-l+1)-ave*ave;
			//printf("t.total:%.ld t.sum:%ld ave:%.4lf s:%.4lf\n",t2,t1,ave,s);
			if(op==2) printf("%.4lf\n",ave);
			else printf("%.4lf\n",s);	
		}
	}
    return 0;
}

延迟操作

P3372 【模板】线段树 1
延迟标记
之前遇到区间修改时可能会遍历区间内的所有数，效率极其低下，有了线段树这种每个结点代表一个区间的数据结构，我们可以在结构体里新增一个变量add，用于储存对区间的增值操作，在未访问到这个区间时，我们可以不用管（这样就省掉了很多无用功233），如果访问到这个区间，就把这个区间对应的sum值加上（add*区间内点数），将add下放到左右两个子树，再将当前节点的add归零。
延迟标记的含义为“该节点曾经被修改，但其子节点尚未被更新”，其本身信息已被修改完毕。

1
2
3
4
5
6
7
8
9
10
11
void spread(int p)
{
	if(tree[p].add!=0)
	{
		tree[p*2].sum+=(tree[p*2].r-tree[p*2].l+1)*tree[p].add;=
		tree[p*2+1].sum+=(tree[p*2+1].r-tree[p*2+1].l+1)*tree[p].add;=
		tree[p*2].add+=tree[p].add;
		tree[p*2+1].add+=tree[p].add;
		tree[p].add=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
#include<bits/stdc++.h>
using namespace std;

int n,m,a[100010];

struct segment_tree
{
	int l,r;
	long long sum,add;
}tree[100010*4];

void build(int p,int l,int r)
{
	tree[p].l=l,tree[p].r=r;
	if(l==r)
	{
		tree[p].sum=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}

void spread(int p)
{
	if(tree[p].add!=0)
	{
		tree[p*2].sum+=(tree[p*2].r-tree[p*2].l+1)*tree[p].add;=
		tree[p*2+1].sum+=(tree[p*2+1].r-tree[p*2+1].l+1)*tree[p].add;=
		tree[p*2].add+=tree[p].add;
		tree[p*2+1].add+=tree[p].add;
		tree[p].add=0;
	}
}

void change(int p,int l,int r,int x)
{
	if(l<=tree[p].l&&r>=tree[p].r)
	{
		tree[p].sum+=(long long)x*(tree[p].r-tree[p].l+1);
		tree[p].add+=x;
		return;
	}
	spread(p);//延迟标记
	int mid=(tree[p].l+tree[p].r)/2;
	if(l<=mid) change(p*2,l,r,x);
	if(r>mid) change(p*2+1,l,r,x);
	tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}

long long ask(int p,int l,int r)
{
    if(l<=tree[p].l && r>=tree[p].r) 
		return tree[p].sum;//如果被覆盖，就返回维护的值
    spread(p);//下传延迟标记，并查询左右儿子
    int mid=(tree[p].l+tree[p].r)>>1;
    long long ans=0;
    if(l<=mid) ans+=ask(p*2,l,r);
    if(r>mid) ans+=ask(p*2+1,l,r);//累加答案，返回左右儿子的和
    return ans;
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	build(1,1,n);
	while(m--)
	{
		int op,l,r;
		scanf("%d%d%d",&op,&l,&r);
		if(op==1)
		{
			int x;
			scanf("%d",&x);
			change(1,l,r,x);
		}
		else if(op==2)
			printf("%lld\n",ask(1,l,r));
	}
	return 0;
}

P2574 XOR的艺术

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<bits/stdc++.h>
using namespace std;
const int N=200020;
int a[N];

struct segment_tree
{
	int l,r,num,mark;
}t[N*4];

void build(int p,int l,int r)
{
	t[p].l=l,t[p].r=r;
	if(l==r)
	{
		t[p].num=a[l];
		//cout<<"p:"<<p<<' '<<a[l]<<endl;
		return;
	}
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	t[p].num=t[p*2].num+t[p*2+1].num;
}

void spread(int p)
{
	if(t[p].mark)
	{
		t[p*2].num=(t[p*2].r-t[p*2].l+1)-t[p*2].num;
		t[p*2+1].num=(t[p*2+1].r-t[p*2+1].l+1)-t[p*2+1].num;
		t[p*2].mark^=1;
		t[p*2+1].mark^=1;
		t[p].mark=0;
	}
}

void change(int p,int l,int r)
{
	if(l<=t[p].l&&t[p].r<=r)
	{
		t[p].num=(t[p].r-t[p].l+1)-t[p].num;
		t[p].mark^=1;
		return;
	}
	int mid=(t[p].l+t[p].r)>>1;
	spread(p);
	if(l<=mid) change(p*2,l,r);
	if(mid<r) change(p*2+1,l,r);
	t[p].num=t[p*2].num+t[p*2+1].num;
}

int ask(int p,int l,int r)
{
	if(t[p].l>=l&&t[p].r<=r) 
		return t[p].num;//如果完全包含，返回区间
	int mid=(t[p].l+t[p].r)/2;
	int ans=0;
	spread(p);//下传标记
	if(l<=mid) ans+=ask(p*2,l,r);//继续向下
	if(r>mid) ans+=ask(p*2+1,l,r);
	return ans;
}

int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%1d",&a[i]);
	build(1,1,n);
	while(m--)
	{
		int op,l,r;
		scanf("%d%d%d",&op,&l,&r);
		if(op==1) cout<<ask(1,l,r)<<endl;
		if(op==0) change(1,l,r);
	}
    return 0;
}

P1438 无聊的数列

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int n,m,a[N];

struct Node
{
	int l,r;
	LL sum,add;
}tr[N*4];

void build(int u,int l,int r)
{
	tr[u]={l,r,0,0};
	if(l==r) return;
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
}
void pushdown(int u)
{
	tr[u<<1].sum+=(tr[u<<1].r-tr[u<<1].l+1)*tr[u].add;
	tr[u<<1|1].sum+=(tr[u<<1|1].r-tr[u<<1|1].l+1)*tr[u].add;
	tr[u<<1].add+=tr[u].add;
	tr[u<<1|1].add+=tr[u].add;
	tr[u].add=0;
}

void modify(int u,int l,int r,int v)
{
	if(tr[u].l>=l&&tr[u].r<=r)
	{
		tr[u].sum+=(tr[u].r-tr[u].l+1)*v;
        tr[u].add+=v;
	}
	else
	{
		pushdown(u);
		int mid=(tr[u].l+tr[u].r)>>1;
		if(l<=mid) modify(u<<1,l,r,v);
		if(r>mid) modify(u<<1|1,l,r,v);
		tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
	}
}


LL query(int u,int l,int r)
{
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
	else
	{	
		pushdown(u);
		int mid=(tr[u].l+tr[u].r)>>1;
		LL sum=0;
		if(l<=mid) sum+=query(u<<1,l,r);
		if(r>mid) sum+=query(u<<1|1,l,r);
		return sum;
	}
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	build(1,1,n);
	while(m--)
	{
		int op;
		scanf("%d",&op);
		if(op==1)
		{
			int l,r,k,d;
			scanf("%d%d%d%d",&l,&r,&k,&d);
			modify(1,l,l,k);
			if(l<r) modify(1,l+1,r,d);
			if(r<n) modify(1,r+1,r+1,-k-d*(r-l));
		}
		if(op==2)
		{
			int x;
			scanf("%d",&x);
			printf("%lld\n",a[x]+query(1,1,x));
		}
	}
    return 0;
}

真的容易在各种奇奇怪怪的地方打错啊，(✖人✖)。
如果有更多种操作（乘上一个值等）可以在结构体再开别的变量，保存标记信息，但需要各个标记下放的顺序。这模板2要了我老命，爬

P3373 【模板】线段树 2

区间乘法：将整个区间上的数乘上一个数时同时要把它储存的add和mu都乘上该数。每次延迟标记下放遵循“先乘后加”：先把区间上的数乘上储存的mu再作区间加法。

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
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int n,m,a[1000005],mod;

struct segment_tree
{
	ll sum,l,r,mu,add;
}t[1000005];

ll read()
{
	ll x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
void build(ll p,ll l,ll r)
{
	t[p].l=l,t[p].r=r,t[p].mu=1;//乘法运算的幺元是1 
	if(l==r)
	{
		t[p].sum=a[l]%mod;
		return;
	}
	ll mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
}

void spread(ll p)//重点关注 ！！！ 
{ 
	t[p*2].sum=(t[p*2].sum*t[p].mu+(t[p*2].r-t[p*2].l+1)*t[p].add%mod)%mod;
	t[p*2+1].sum=(t[p*2+1].sum*t[p].mu+(t[p*2+1].r-t[p*2+1].l+1)*t[p].add%mod)%mod;
	t[p*2].mu=(t[p*2].mu*t[p].mu)%mod;
	t[p*2+1].mu=(t[p*2+1].mu*t[p].mu)%mod;
	t[p*2].add=(t[p*2].add*t[p].mu+t[p].add)%mod;
	t[p*2+1].add=(t[p*2+1].add*t[p].mu+t[p].add)%mod;
	t[p].add=0;
	t[p].mu=1;
}

void pluss(ll p,ll l,ll r,ll x)
{
	if(l<=t[p].l&&t[p].r<=r)
	{
		t[p].sum=(t[p].sum+(t[p].r-t[p].l+1)*x%mod)%mod;
		t[p].add+=x;
		return;
	}
	spread(p);
	ll mid=(t[p].l+t[p].r)>>1;
	if(l<=mid) pluss(p*2,l,r,x);//一直都是（l,r)，算出mid仅用于比较 
	if(mid<r) pluss(p*2+1,l,r,x);
	t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
}

void mu(ll p,ll l,ll r,ll x)
{
	if(l<=t[p].l&&t[p].r<=r)
	{
		t[p].add=(t[p].add*x)%mod;
		t[p].mu=(t[p].mu*x)%mod;
		t[p].sum=(t[p].sum*x)%mod;
		return;
	}
	spread(p);
	ll mid=(t[p].l+t[p].r)>>1;
	if(l<=mid) mu(p*2,l,r,x);
	if(mid<r) mu(p*2+1,l,r,x);
	t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod;
}

ll ask(ll p,ll l,ll r)
{
	if(l<=t[p].l&&t[p].r<=r)
		return t[p].sum;
	spread(p);//每次询问到这里也要下放标记 
	ll mid=(t[p].l+t[p].r)>>1;
	ll val=0;
	if(l<=mid) val=(val+ask(p*2,l,r))%mod;
	if(mid<r )val=(val+ask(p*2+1,l,r))%mod;
	return val;
}
int main()
{
	cin>>n>>m>>mod;
	for(int i=1;i<=n;i++)
		a[i]=read();
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int op=read();
		if(op==1)
		{
			ll cn=read(),cm=read(),cw=read();
			mu(1,cn,cm,cw);
		}else if(op==2)
		{
			ll cn=read(),cm=read(),cw=read();
			pluss(1,cn,cm,cw);
		}
		else 
		{
			ll cn=read(),cm=read();
			cout<<ask(1,cn,cm)<<endl;
		}
    }
}

扫描线

247. 亚特兰蒂斯

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

const int N=1e5+10;
int n;
struct segment
{
	double x,y1,y2;
	int k;
	bool operator< (const segment &t)const
	{
		return x<t.x;
	}
}seg[N*2];//储存竖线 
struct Node
{
	int l,r;
	int cnt;
	double len;
}tr[N*8];//在纵坐标上建线段树 

vector<double>line;

int find(double x)
{
	return lower_bound(line.begin(),line.end(),x)-line.begin();
}

void pushup(int u)
{
	if(tr[u].cnt) tr[u].len=line[tr[u].r+1]-line[tr[u].l];
	else if(tr[u].l!=tr[u].r)
		tr[u].len=tr[u<<1].len+tr[u<<1|1].len;
	else tr[u].len=0;
}
void build(int u,int l,int r)
{
	tr[u]={l,r,0,0};
	if(l!=r)
	{
		int mid=l+r>>1;
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
	}
	
}

void modify(int u,int l,int r,int k)
{
	if(l<=tr[u].l&&tr[u].r<=r)
		tr[u].cnt+=k;
	else
	{
		int mid=(tr[u].l+tr[u].r)>>1;
		if(l<=mid) modify(u<<1,l,r,k);
		if(mid<r) modify(u<<1|1,l,r,k);
	}
	pushup(u);
}

int main()
{
	int T=1;
	while(scanf("%d",&n),n)
	{
		line.clear();
		int cnt=0;
		for(int i=0;i<n;i++)
		{
			double x1,x2,y1,y2;
			scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
			seg[cnt++]={x1,y1,y2,1};//k==1表示矩形左边 
			seg[cnt++]={x2,y1,y2,-1};//k==2表示矩形右边 
			line.push_back(y1);
			line.push_back(y2);
		}
		sort(line.begin(),line.end());
        line.erase(unique(line.begin(),line.end()),line.end());
		build(1,0,line.size()-2);
		sort(seg,seg+2*n);
		double ans=0;
		for(int i=0;i<2*n;i++)
		{
			if(i>0) ans+=tr[1].len*(seg[i].x-seg[i-1].x);
			modify(1,find(seg[i].y1),find(seg[i].y2)-1,seg[i].k); 
		}
		printf("Test case #%d\n",T++);
        printf("Total explored area: %.2lf\n\n",ans);
	}
    return 0;
}


主席树

P3834 【模板】可持久化线段树 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
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int a[N],b[N],n,m,tot,total,root[N];
struct Node
{
    int l,r;
    int cnt;
}tr[N*4+N*20];

int build(int l,int r)
{
    int p=++tot;
    if(l==r) return p;
    int mid=(l+r)>>1;
    tr[p].l=build(l,mid),tr[p].r=build(mid+1,r);
    return p;
}

int insert(int p,int l,int r,int x)
{
    int q=++tot;//点分裂
    tr[q]=tr[p];
    if(l==r)
    {
        tr[q].cnt++;
        return q;
    }
    int mid=(l+r)>>1;
    if(x<=mid) tr[q].l=insert(tr[p].l,l,mid,x);
    else tr[q].r=insert(tr[p].r,mid+1,r,x);
    tr[q].cnt=tr[tr[q].l].cnt+tr[tr[q].r].cnt;
    return q;
}

int query(int p,int q,int l,int r,int k)
{
    if(l==r) return l;
    int dif=tr[tr[q].l].cnt-tr[tr[p].l].cnt;
    int mid=(l+r)>>1;
    if(k<=dif) return query(tr[p].l,tr[q].l,l,mid,k);
    else return query(tr[p].r,tr[q].r,mid+1,r,k-dif);
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),b[i]=a[i];
    sort(a+1,a+n+1);
    total=unique(a+1,a+n+1)-a-1;
    root[0]=build(1,total);
    for(int i=1;i<=n;i++)
        b[i]=lower_bound(a+1,a+total+1,b[i])-a;
    for(int i=1;i<=n;i++)
        root[i]=insert(root[i-1],1,total,b[i]);
    while(m--)
    {
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",a[query(root[l-1],root[r],1,total,k)]);
    }
    return 0;
}

P1972 [SDOI2009] HH的项链
每次都是先把$last[a[i]]$的位置先改了（之前没有的话就直接继承上一个节点的了），形成树t，再在t的基础上继续修改。查询的时候我们用右端点控制树的版本，而用左端点控制范围。

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

const int N=1e6+10;
int n,a[N],root[N],last[N],ans[N],tot,m;
inline int read()
{
	int 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;
}
struct Node
{
    int l,r;
    int cnt;
}tr[N*40];


int build(int l,int r)
{
    int p=++tot;
    if(l==r) return p;
    int mid=(l+r)>>1;
    tr[p].l=build(l,mid),tr[p].r=build(mid+1,r);
    return p;
}

int insert(int p,int idx,int l,int r,int x)
{
    int q=++tot;//点分裂
    tr[q]=tr[p],tr[q].cnt+=x;
	if(l<r)
	{
		int mid=(l+r)>>1;
	    if(idx<=mid) tr[q].l=insert(tr[p].l,idx,l,mid,x);
	    else tr[q].r=insert(tr[p].r,idx,mid+1,r,x);
	}
	return q;
}

int query(int idx,int q,int l,int r)
{
	if(l==r) return tr[q].cnt;
	int mid=l+r>>1;
	if(idx<=mid) return query(idx,tr[q].l,l,mid)+tr[tr[q].r].cnt;
	else return query(idx,tr[q].r,mid+1,r);
}

int main()
{
	cin>>n;
	root[0]=build(1,n);
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		if(!last[a[i]])//该数据第一次出现 
			root[i]=insert(root[i-1],i,1,n,1);
		else
		{
			int t=insert(root[i-1],last[a[i]],1,n,-1);
			root[i]=insert(t,i,1,n,1);
		}
		last[a[i]]=i;
	}
    cin>>m;
    for(int i=1;i<=m;i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",query(l,root[r],1,n));
	}
    return 0;
}