线段树

OI&ACM, 数据结构
  1. 1 【bzoj 3212】Pku3468 A Simple Problem with Integers
  2. 2 【bzoj 3211】花神游历各国
  3. 3 【bzoj 1593】[Usaco2008 Feb] Hotel 旅馆
  4. 4 【bzoj 3226】[Sdoi2008]校门外的区间
  5. 5 【bzoj 2957】楼房重建

1 【bzoj 3212】Pku3468 A Simple Problem with Integers

线段树裸题、lazy标记 

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
#include<iostream>
#include<cstdio>
using namespace std;
int n,Q,x,y,z,tot=1,a[100001];
char c;
struct node{
	int l,r,ls,rs;
	long long sum,mark;
}t[400001];
void go_down(int root)
{
	if(!t[root].mark) return;
	long long M=t[root].mark;int L=t[root].ls,R=t[root].rs;
	t[L].mark+=M;t[L].sum+=(t[L].r-t[L].l+1)*M;
	t[R].mark+=M;t[R].sum+=(t[R].r-t[R].l+1)*M;
	t[root].mark=0;
}
void Build(int root,int L,int R)
{
	t[root].l=L;t[root].r=R;
	if(L==R) 
	{
		t[root].sum=a[L];return;
	}
	int mid=(L+R)/2;
	t[root].ls=++tot;Build(t[root].ls,L,mid);
	t[root].rs=++tot;Build(t[root].rs,mid+1,R);
	t[root].sum=t[t[root].ls].sum+t[t[root].rs].sum;
}
void Add(int root,int L,int R,int x)
{
	if(L<=t[root].l&&t[root].r<=R)
	{
		t[root].mark+=x;t[root].sum+=x*(t[root].r-t[root].l+1);
		return;
	}
	int mid=(t[root].l+t[root].r)/2;
	go_down(root);
	if(L<=mid) Add(t[root].ls,L,R,x);
	if(R>mid)  Add(t[root].rs,L,R,x);
	t[root].sum=t[t[root].ls].sum+t[t[root].rs].sum;
} 
long long Quary(int root,int L,int R)
{
	if(L<=t[root].l&&t[root].r<=R) 
	  return t[root].sum;
	int mid=(t[root].l+t[root].r)/2;long long ans=0;
	go_down(root);
	if(L<=mid) ans+=Quary(t[root].ls,L,R);
	if(R>mid)  ans+=Quary(t[root].rs,L,R);
	return ans;
}
int main()
{
	scanf("%d%d",&n,&Q);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	Build(1,1,n);
	while(Q--)
	{
		cin>>c;
		if(c=='C')
		{
			scanf("%d%d%d",&x,&y,&z);
			Add(1,x,y,z);
		}
		else
		{
			scanf("%d%d",&x,&y);
			printf("%lld\n",Quary(1,x,y));
		}
	}
}

2 【bzoj 3211】花神游历各国

线段树求sqrt

不能用lazy了
考虑最多一个点根号五次就是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<cstdio>
#include<cmath>
using namespace std;
int n,m,pre[100001],a[100001],tot=1,x,l,r;
struct node{
	int l,r,ls,rs;
	long long num;
}t[300001];
void Build(int root,int L,int R)
{
	t[root].l=L;t[root].r=R;
	if(L==R)
	{
		t[root].num=a[L];return;
	}
	int mid=(L+R)>>1;
	t[root].ls=++tot; Build(t[root].ls,L,mid);
	t[root].rs=++tot; Build(t[root].rs,mid+1,R);
	t[root].num=t[t[root].ls].num+t[t[root].rs].num;
}
void change(int root,int x)
{
	if(t[root].l==t[root].r)
	{
		t[root].num=a[x];return;
	}
	int mid=(t[root].l+t[root].r)>>1;
	if(x<=mid) change(t[root].ls,x);
	else change(t[root].rs,x);
	t[root].num=t[t[root].ls].num+t[t[root].rs].num;
}
long long Quary(int root,int L,int R)
{
	if(L<=t[root].l&&t[root].r<=R) return t[root].num;
	int mid=(t[root].l+t[root].r)>>1;long long ans=0;
	if(L<=mid) ans+=Quary(t[root].ls,L,R);
	if(mid<R)  ans+=Quary(t[root].rs,L,R);
	return ans;
}
int father(int x)
{
	if(pre[x]==x) return x;
	else return pre[x]=father(pre[x]);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]<=1) pre[i]=pre[i-1];
		else pre[i]=i;
	}
	Build(1,1,n);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&l,&r);
		if(x==1)  printf("%lld\n",Quary(1,l,r));
		else
		{
			while(r>=l)
			{
				a[r]=sqrt(a[r]);
				change(1,r);
				if(a[r]<=1) pre[r]=father(r-1);
				r=pre[r-1];
			}
		}
	}
}

3 【bzoj 1593】[Usaco2008 Feb] Hotel 旅馆

线段树记录每一段的最大连续数
为了上传下传还要记录从左边和右边数的最大连续数 

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
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,k,x,y,tot=1;
struct node{
	int l,r,ls,rs,llen,rlen,maxlen,mark;
}t[100001];
void push_up(int root)
{
	int L=t[root].ls,R=t[root].rs;
	int maxx=max(t[L].maxlen,t[R].maxlen);
	t[root].maxlen=max(maxx,t[L].rlen+t[R].llen);
	if(t[L].llen==t[L].r-t[L].l+1) t[root].llen=t[L].llen+t[R].llen;
	  else t[root].llen=t[L].llen;
	if(t[R].rlen==t[R].r-t[R].l+1) t[root].rlen=t[L].rlen+t[R].rlen;
	  else t[root].rlen=t[R].rlen;
}
void push_down(int root)
{
	if(t[root].mark==-1) return;
	int L=t[root].ls,R=t[root].rs;
	t[L].llen=t[L].rlen=t[L].maxlen=(t[L].r-t[L].l+1)*t[root].mark;
	t[R].llen=t[R].rlen=t[R].maxlen=(t[R].r-t[R].l+1)*t[root].mark;
	t[L].mark=t[R].mark=t[root].mark;
	t[root].mark=-1;
}
void Build(int root,int L,int R)
{
	t[root].l=L;t[root].r=R;t[root].mark=-1;
	t[root].llen=t[root].rlen=t[root].maxlen=R-L+1;
	if(L==R) return;
	int mid=(L+R)>>1;
	t[root].ls=++tot;Build(t[root].ls,L,mid);
	t[root].rs=++tot;Build(t[root].rs,mid+1,R);
	push_up(root);
}
int find(int root,int len)
{
	push_down(root);
	if(t[root].l==t[root].r) return t[root].l;
	int L=t[root].ls,R=t[root].rs;
	if(t[L].maxlen>=len) return find(L,len);
	if(t[L].rlen+t[R].llen>=len) return t[L].r-t[L].rlen+1;
	return find(R,len);
}
void change(int root,int L,int R,int x)
{
	push_down(root);
	if(L<=t[root].l&&t[root].r<=R)
	{
		t[root].llen=t[root].rlen=t[root].maxlen=(t[root].r-t[root].l+1)*x;
		t[root].mark=x;return;
	}
	int mid=(t[root].l+t[root].r)>>1;
	if(L<=mid) change(t[root].ls,L,R,x);
	if(R>mid)  change(t[root].rs,L,R,x);
	push_up(root);
}
int main()
{
	scanf("%d%d",&n,&m);
	Build(1,1,n);
	while(m--)
	{
		scanf("%d",&k);
		if(k==1)
		{
			scanf("%d",&x);
			if(x>t[1].maxlen) printf("0\n");
			else
			{
				y=find(1,x);
				printf("%d\n",y);
				change(1,y,y+x-1,0);
			}
		}
		else
		{
			scanf("%d%d",&x,&y);
			change(1,x,x+y-1,1);
		}
	}
}

4 【bzoj 3226】[Sdoi2008]校门外的区间

5种运算如下：
U T : S∪T
I T : S∩T
D T : S－T
C T ：T－S
S T ：S⊕T

U 区间涂1
I 两侧区间涂0
D 区间涂0
C 两侧涂0,中间取反
S 区间取反

开两倍，为了存()和[]
不小心RE了四回，因为忘了数字不只是一位（呜呜 不要打我）
我写了动态开点

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
#include<cstdio>
using namespace std;
char s[20];
int n,tot=1,x,y;
struct node{
	int l,r,ls,rs,mark;
}t[300000];
void push_down(int root)
{
	int L=t[root].ls,R=t[root].rs;
	t[L].mark=t[R].mark=t[root].mark;
}
void change(int root,int L,int R,int x)
{
	if(L>R) return;
	if(L<=t[root].l&&t[root].r<=R)
	{
		t[root].mark=x;return;
	}
	int mid=(t[root].l+t[root].r)>>1;
	if(!t[root].ls) t[root].ls=++tot,t[tot].l=t[root].l,t[tot].r=mid;
	if(!t[root].rs) t[root].rs=++tot,t[tot].l=mid+1,t[tot].r=t[root].r;
	if(t[root].mark!=-1) push_down(root);
	if(L<=mid) change(t[root].ls,L,R,x);
	if(R>mid)  change(t[root].rs,L,R,x);
	if(t[t[root].ls].mark==t[t[root].rs].mark) t[root].mark=t[t[root].ls].mark;
	else t[root].mark=-1;
}
void fan(int root,int L,int R)
{
	if(L>R) return;
	if(L<=t[root].l&&t[root].r<=R&&t[root].mark!=-1)
	{
		t[root].mark=1-t[root].mark;return;
	}
	int mid=(t[root].l+t[root].r)>>1;
	if(!t[root].ls) t[root].ls=++tot,t[tot].l=t[root].l,t[tot].r=mid;
	if(!t[root].rs) t[root].rs=++tot,t[tot].l=mid+1,t[tot].r=t[root].r;
	if(t[root].mark!=-1) push_down(root);
	if(L<=mid) fan(t[root].ls,L,R);
	if(R>mid)  fan(t[root].rs,L,R);
	if(t[t[root].ls].mark==t[t[root].rs].mark) t[root].mark=t[t[root].ls].mark;
	else t[root].mark=-1;
}
bool search(int root,int x)
{
	if(t[root].l<=x&&x<=t[root].r&&t[root].mark!=-1)  return t[root].mark;
	int mid=(t[root].l+t[root].r)>>1;
	if(!t[root].ls) t[root].ls=++tot,t[tot].l=t[root].l,t[tot].r=mid;
	if(!t[root].rs) t[root].rs=++tot,t[tot].l=mid+1,t[tot].r=t[root].r;
	if(t[root].mark!=-1) push_down(root);
	if(x<=mid) search(t[root].ls,x);else search(t[root].rs,x);
}
int main()
{
	t[1].l=1;t[1].r=131072;
 	while(scanf("%s%s",s,s+2)==2)
	{
		if(s[0]<'A'||s[0]>'Z') continue;
		int i=3;x=y=0;
		while(s[i]>='0'&&s[i]<='9') x=x*10+s[i++]-'0';
		i++;
		while(s[i]>='0'&&s[i]<='9') y=y*10+s[i++]-'0';
		if(s[2]=='[') x=x*2+1;else x=x*2+2;
		if(s[i]==']') y=y*2+1;else y=y*2;
		if(y>n) n=y;
		if(s[0]=='U') change(1,x,y,1);
		else if(s[0]=='I') change(1,1,x-1,0),change(1,y+1,n,0);
		else if(s[0]=='D') change(1,x,y,0);
		else if(s[0]=='C') change(1,1,x-1,0),change(1,y+1,n,0),fan(1,x,y);
		else fan(1,x,y);
	}
	int L=0,R=0,yes=0;
	for(int i=1;i<=n;i++)
	{
		if(search(1,i))
		{
			if(!L) L=i;else R=i;
		}
		else
		{
			if(!L) continue;
			if(!R) R=L;
			if(L%2) printf("[");else printf("(");
			printf("%d,%d",(L-1)/2,R/2);
			if(R%2) printf("] ");else printf(") ");
			L=R=0;yes=1;
		}
	}
	if(L)
	{
		if(!R) R=L;
	    if(L%2) printf("[");else printf("(");
	    printf("%d,%d",(L-1)/2,R/2);
	    if(R%2) printf("]");else printf(")");
	    L=R=0;yes=1;
	}
	if(!yes) printf("empty set");
}

5 【bzoj 2957】楼房重建

求抬头望去能看到的楼房数

保存一下这个区间的最大斜率和在不考虑其他区间的情况下能看到的楼房数。
然后我们考虑合并：
1. 最大值直接合并就好了。
2. 对于左子树的楼房数,合并之后是没有影响的，直接加上就好。
3. 对于右子树。我们考虑一下右子树的左子树的最大值(a)和左子树的最大值(b)
- 如果a<=b,显然左子树会把它全挡住。答案只可能出现在右子树的右子树然后我们递归一下右子树的右子树即可。
- 如果a>b,显然我们需要重新计算一下右子树的左子树的楼房数,而右子树的右子树是不会被影响的，所以我们先去掉以前的右子树的左子树的值，再递归右子树的左子树.重新计算一遍加上即可。

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<iostream>
#include<cstdio>
using namespace std;
int n,m,x,y,pre,ans,tot=1;
struct node{
	int l,r,ls,rs,ans;double maxx;
}t[200001];
void Build(int root,int L,int R)
{
	t[root].l=L;t[root].r=R;
	if(L==R) return;
	int mid=(L+R)>>1;
	t[root].ls=++tot;Build(t[root].ls,L,mid);
	t[root].rs=++tot;Build(t[root].rs,mid+1,R);
}
int search(int root,double d)
{
	if(t[root].l==t[root].r) return t[root].maxx>d;
	if(t[t[root].ls].maxx<=d) return search(t[root].rs,d);
	return t[root].ans-t[t[root].ls].ans+search(t[root].ls,d);
}
void Change(int root,int num,double d)
{
	if(t[root].l==t[root].r)
	{
		t[root].ans=1;t[root].maxx=d;return;
	}
	int mid=(t[root].l+t[root].r)>>1;
	if(num<=mid) Change(t[root].ls,num,d); else Change(t[root].rs,num,d);
	t[root].maxx=max(t[t[root].ls].maxx,t[t[root].rs].maxx);
	t[root].ans=t[t[root].ls].ans+search(t[root].rs,t[t[root].ls].maxx);
}
int main()
{
	scanf("%d%d",&n,&m);
	Build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		Change(1,x,1.0*y/x);
		printf("%d\n",t[1].ans);
	}
}
线段树