线段树代码仓库

自用笔记算法

线段树代码仓库

除基本操作(区间单点增减替换 区间单点查询最值或和)
除pdf(个别pdf题目会加进来)

1.查询覆盖后的颜色段数目/海报数目(在query里hash计算)
3.根号修改
2.简单区间合并(lcis 包含某个数字的最大连续区间 连续区间和最大值)

zoj 1610

题目要求

区间替换颜色 查询某种颜色的颜色段数目

参考AC代码

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>
#define maxn 8050
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
int q,last;
int lazy[maxn<<2],num[maxn];
void init(){
	memset(lazy,-1,sizeof(lazy));
	memset(num,0,sizeof(num));
	last=-1;
}
void push_down(int rt){
	if(lazy[rt]!=-1){
		lazy[rt<<1]=lazy[rt];
		lazy[rt<<1|1]=lazy[rt];
		lazy[rt]=-1;
	}
}
void update(int rt,int l,int r,int L,int R,int x){
	if(l>=L && r<=R){
		lazy[rt]=x;
		return;
	}
	push_down(rt);
	int mid=l+r>>1;
	if(mid>=L) update(lson,L,R,x);
	if(mid<R) update(rson,L,R,x);
}
void query(int rt,int l,int r){
	if(l==r){
		if(lazy[rt]!=-1 && lazy[rt]!=last) num[lazy[rt]]++;
		last=lazy[rt]; 
		return;
	}
	push_down(rt);
	int mid=l+r>>1;
	query(lson);
	query(rson);
}
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d",&q)!=EOF){
		init();
		while(q--){
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			if(a<b) update(1,1,8005,a+1,b,c);
		}
		query(1,1,8005);
		for(int i=0;i<8005;i++){
			if(num[i]) printf("%d %d\n",i,num[i]);
		}
		puts("");
	}
	return 0;
}

思路

和下一题贴海报类似
正常用lazy覆盖 最后query里l==r的时候进行计数操作
如果这个位置颜色不为0并且跟上一个颜色段的颜色不一样 说明这是一个新的颜色段
该颜色段数目++ 同时跟新last

poj 2528

题目要求

在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报

参考AC代码

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<algorithm>
#include<vector>
#include<cstring>
#define maxn 10050
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
int t,n,cnt;
int lazy[2*maxn<<2];
int hashh[maxn];
int l[maxn],r[maxn];
vector<int>v;
int getid(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
void push_down(int rt){
	if(lazy[rt]){
		lazy[rt<<1]=lazy[rt];
		lazy[rt<<1|1]=lazy[rt];
		lazy[rt]=0;
	}
}
void change(int rt,int l,int r,int L,int R,int x){
	if(L<=l && r<=R){
		lazy[rt]=x;
		return;
	}
	push_down(rt);
	int mid=(l+r)>>1;
	if(mid>=L) change(lson,L,R,x);
	if(mid<R) change(rson,L,R,x);
}
void query(int rt,int l,int r){
	if(lazy[rt]){
		if(!hashh[lazy[rt]]){
			cnt++;
			hashh[lazy[rt]]=1;
		}
		return;
	}
	if(l==r) return;
	int mid=l+r>>1;
	query(lson);
	query(rson);
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		memset(lazy,0,sizeof(lazy));
		memset(hashh,0,sizeof(hashh));
		cnt=0;
		v.clear();
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d%d",&l[i],&r[i]);
			v.push_back(l[i]);
			v.push_back(r[i]);
		}
		sort(v.begin(),v.end());
		v.erase(unique(v.begin(),v.end()),v.end());
		int len=v.size();
		for(int i=1;i<=n;i++){
			int L=getid(l[i]);
			int R=getid(r[i]);
			change(1,1,len,L,R,i);
		}
		query(1,1,len);
		printf("%d\n",cnt);
	}
	return 0;
}

思路

数据范围很大 加上是区间问题 我们离散化
每种类型的海报我们简单hash一个颜色i
同样在query里l==r的时候进行计数操作
如果这个颜色段没有出现过 cnt++ 同时这个颜色记录为出现过

HDU 4027

题目要求

两种操作 第一种是把l到r区间内的数全部开根号
第二种是求l到r区间和

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define LL long long
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
int n,q;
LL a[maxn];
LL sum[maxn<<2];
void push_up(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int rt,int l,int r){
    if(l==r){
        sum[rt]=a[l];
        return;
    }
    int mid=l+r>>1;
    build(lson);
    build(rson);
    push_up(rt);
}
void update(int rt,int l,int r,int L,int R){
    if(l==r){
        sum[rt]=sqrt(sum[rt]);
        return;
    }
    if(l>=L && r<=R && sum[rt]==r-l+1) return;
    int mid=l+r>>1;
    if(mid>=L) update(lson,L,R);
    if(mid<R) update(rson,L,R);
    push_up(rt);
}
LL query(int rt,int l,int r,int L,int R){
    if(l>=L && r<=R) return sum[rt];
    int mid=l+r>>1;
    if(mid>=R) return query(lson,L,R);
    else if(mid<L) return query(rson,L,R);
    else return query(lson,L,R)+query(rson,L,R);
}
int Case=1;
int main(){
//    freopen("input.txt","r",stdin);
    while(scanf("%d",&n)!=EOF){
        printf("Case #%d:\n",Case++);
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        build(1,1,n);
        scanf("%d",&q);
        while(q--){
            int op,x,y;
            scanf("%d%d%d",&op,&x,&y);
            if(x>y) swap(x,y); 
            if(op==0) update(1,1,n,x,y);
            else if(op==1) printf("%lld\n",query(1,1,n,x,y));
        }
        puts("");
    }
    return 0;
}

思路

由于区间内每个点开根号 无法用lazy延迟 我们只能单点修改
可以注意到一个性质 LL范围的数字最多经过7次开根号后就会变成1 所以我们加一个剪枝：
如果区间的和等于区间长度(等价于区间内的每个数字都是1) 那么这个区间就无需操作了
注意点：
1.开LL
2.必须确保x<y

HDU 3308

转跳链接

HDU 1540

题目要求

三种操作 删除某个位置的数字 恢复上一次删除的数字 查询包含某个数字x的最大连续区间

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 50050
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
int n,m;
struct T{
	int l,r;
	int sum,lsum,rsum;
}tree[maxn<<2];
int s[maxn],top;
void push_up(int rt){  //跟lcis类似 区别在于不需要判断能否连接
	if(tree[rt<<1].lsum==tree[rt<<1].r-tree[rt<<1].l+1) tree[rt].lsum=tree[rt<<1].lsum+tree[rt<<1|1].lsum;
	else tree[rt].lsum=tree[rt<<1].lsum;
	if(tree[rt<<1|1].rsum==tree[rt<<1|1].r-tree[rt<<1|1].l+1) tree[rt].rsum=tree[rt<<1|1].rsum+tree[rt<<1].rsum;
	else tree[rt].rsum=tree[rt<<1|1].rsum;
	tree[rt].sum=max(max(tree[rt<<1].sum,tree[rt<<1|1].sum),tree[rt<<1].rsum+tree[rt<<1|1].lsum);	
}
void build(int rt,int l,int r){   //这样的写法可以避免push up操作
	tree[rt].sum=tree[rt].lsum=tree[rt].rsum=r-l+1;
	tree[rt].l=l,tree[rt].r=r;
	if(l==r) return;
	int mid=l+r>>1;
	build(lson);
	build(rson);
}
void update(int rt,int x,int flag){ //flag为1代表修复 为0代表破坏
	if(tree[rt].l==tree[rt].r){
		if(flag==1) tree[rt].sum=tree[rt].lsum=tree[rt].rsum=1;
		else tree[rt].sum=tree[rt].lsum=tree[rt].rsum=0;
		return;
	}
	int mid=(tree[rt].l+tree[rt].r)>>1;
	if(mid>=x) update(rt<<1,x,flag);
	else update(rt<<1|1,x,flag);
	push_up(rt);
}
int query(int rt,int x){  //加一个剪枝 如果区间为空或者区间已满 直接返回
	if(tree[rt].l==tree[rt].r || tree[rt].sum==0 || tree[rt].sum==tree[rt].r-tree[rt].l+1) return tree[rt].sum;
	int mid=(tree[rt].l+tree[rt].r)>>1;
	if(mid>=x){
		//判断当前这个数是否在左区间的右连续中 其中tree[rt<<1].r-tree[rt<<1].rsum+1代表左子树右边连续区间的左边界值 即连续区间的起点 
		if(x>=tree[rt<<1].r-tree[rt<<1].rsum+1) return tree[rt<<1].rsum+tree[rt<<1|1].lsum;
		else return query(rt<<1,x);
	}
	else{ //同理 判断这个数字是否在右区间的左连续中 tree[rt<<1|1].l+tree[rt<<1|1].lsum-1为右终点
		if(x<=tree[rt<<1|1].l+tree[rt<<1|1].lsum-1) return tree[rt<<1].rsum+tree[rt<<1|1].lsum;
		return query(rt<<1|1,x);
	}
}
char op[10];
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d",&n,&m)!=EOF){
		build(1,1,n);
		top=0;
		while(m--){
			scanf("%s",op);
			if(op[0]=='D'){
				int x;
				scanf("%d",&x);
				s[++top]=x;
				update(1,x,0);
			}
			else if(op[0]=='Q'){
				int x;
				scanf("%d",&x);
				printf("%d\n",query(1,x));
			}
			else{
				int x;
				x=s[top--];
				update(1,x,1);
			}
		}
	}
	return 0;
}

思路

跟lcis类似 再维护l和r
删除和恢复用栈维护
注意push up操作和query里的操作

bzoj 1135

维护连续区间和的最大值
注意写法

参考AC代码

1
2
3
4
5
6
void pushup(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    lmax[rt]=max(lmax[rt<<1],sum[rt<<1]+lmax[rt<<1|1]);
    rmax[rt]=max(rmax[rt<<1|1],sum[rt<<1|1]+rmax[rt<<1]);
    mmax[rt]=max(lmax[rt<<1|1]+rmax[rt<<1],max(mmax[rt<<1],mmax[rt<<1|1]));
}

HDU 4614

题目要求

有n个花瓶 每个花瓶只能放一朵花
给出q次两种类型的操作
1代表在x位置开始放y多花 如果有这个位置有花 后推 直到最后一个 如果有部分花没有放 直接扔掉 如果一朵花都没有放
输出Can not put any one.
2代表把x到y位置的花全部清空 输出一共有多少朵花

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 50050
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r 
using namespace std;
int t,n,q;
int sum[maxn<<2],lazy[maxn<<2];
void push_up(int rt){
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void push_down(int rt,int l,int r){
	if(lazy[rt]!=-1){
		lazy[rt<<1]=lazy[rt];
		lazy[rt<<1|1]=lazy[rt];
		if(lazy[rt]){
			int mid=l+r>>1;
			sum[rt<<1]=mid-l+1;
			sum[rt<<1|1]=r-mid;
		}
		else sum[rt<<1]=sum[rt<<1|1]=0;
		lazy[rt]=-1;
	}
}
void build(int rt,int l,int r){
	sum[rt]=0,lazy[rt]=-1;
	if(l==r) return;
	int mid=l+r>>1;
	build(lson);
	build(rson);
}
void update(int rt,int l,int r,int L,int R,int val){
	if(l>=L && r<=R){
		lazy[rt]=val;
		if(val) sum[rt]=r-l+1;
		else sum[rt]=0;
		return;
	}
	push_down(rt,l,r);
	int mid=l+r>>1;
	if(mid>=L) update(lson,L,R,val);
	if(mid<R) update(rson,L,R,val);
	push_up(rt);
}
int query(int rt,int l,int r,int L,int R){
	if(l>=L && r<=R) return sum[rt];
	push_down(rt,l,r);
	int mid=l+r>>1;
	if(mid>=R) return query(lson,L,R);
	else if(mid<L) return query(rson,L,R);
	else return query(lson,L,R)+query(rson,L,R);
}
int bin(int st,int num){
	int l=st,r=n;
	int ans=-1;
	while(l<=r){
		int mid=l+r>>1;
		int tmp=query(1,1,n,st,mid);
		if(mid-st+1-tmp>=num) ans=mid,r=mid-1;
		else l=mid+1;
	}
	return ans;
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&q);
		build(1,1,n);
		while(q--){
			int op,x,y;
			scanf("%d%d%d",&op,&x,&y);
			if(op==1){
				x++;
				int pos1=bin(x,1);
				if(pos1==-1) puts("Can not put any one.");
				else{
					int tmp=query(1,1,n,pos1,n);
					tmp=n-pos1+1-tmp;
					if(tmp<=y) y=tmp;
					int pos2=bin(x,y);
					printf("%d %d\n",pos1-1,pos2-1);
					update(1,1,n,pos1,pos2,1); 
				}
			}
			else if(op==2){
				x++,y++;
				printf("%d\n",query(1,1,n,x,y));
				update(1,1,n,x,y,0);
			}
		}
		puts("");
	}	
	return 0;
}

思路

线段树+二分查找
sum维护区间的花数量和 lazy表示该区间是否全部有花(lazy=1) 全部没有花(lazy=0)
因为区间是0到n-1 所以++ 输出的时候–
先找到在x位置开始放1朵花的位置 如果找不到这个位置输出Can not put any one.
否则找到的pos1就是起点 然后找出从pos1到n的所有空位置的数量(总位置-query有花的数量) 如果比y小 y=tmp 多余的花需要丢掉
再从pos1位置开始找到放b多花的终止位置 就是答案
注意1操作结束要把pos1到pos2位置全部变成1 2操作全部变成0
二分的具体操作：固定st起点 如果空位置≥num 区间向左移动缩小空位置数量 确保找到的位置最左 否则向右移动

HDU 1225

题目要求

求矩形面积并(至少两次)

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 20050
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
const double eps=1e-9;
int T,n;
int cnt[maxn<<2];
double one[maxn<<2],two[maxn<<2];
struct Seg{
    double l,r,h;
    int val;
    Seg(){}
    Seg(double l,double r,double h,int val):l(l),r(r),h(h),val(val){}
    bool operator < (const Seg& rhs) const{
        return h<rhs.h;
    }
};
vector<Seg>v;
vector<double>mp;
void pushup(int rt,int l,int r){
    if(cnt[rt]>=2) two[rt]=one[rt]=mp[r]-mp[l-1];
    else if(cnt[rt]==1) {
        one[rt]=mp[r]-mp[l-1];
        if(l==r) two[rt]=0;
        else two[rt]=one[rt<<1]+one[rt<<1|1];
    }
    else{
        if(l==r) one[rt]=two[rt]=0;
        else{
            one[rt]=one[rt<<1]+one[rt<<1|1];
            two[rt]=two[rt<<1]+two[rt<<1|1];
        }
    }
}
void update(int rt,int l,int r,int L,int R,int val){
    if(L<=l && r<=R) {
        cnt[rt]+=val;
        pushup(rt,l,r);
        return;
    }
    int mid=(l+r)>>1;
    if(L<=mid) update(lson,L,R,val);
    if(R>mid) update(rson,L,R,val);
    pushup(rt,l,r);
}
int main(){
//    freopen("input.txt","r",stdin);
       scanf("%d",&T);
    while(T--){
        double X1,X2,Y1,Y2;
        scanf("%d",&n);
        mp.clear();
        v.clear();
        for(int i=1;i<=n;i++){
            scanf("%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2);
            v.push_back(Seg(X1,X2,Y1,1));
            v.push_back(Seg(X1,X2,Y2,-1));
            mp.push_back(X1);
            mp.push_back(X2);
        }
        sort(v.begin(),v.end());
        sort(mp.begin(),mp.end());
        mp.resize(unique(mp.begin(),mp.end())-mp.begin());
        mm(cnt,0),mm(one,0),mm(two,0);
        int m=mp.size();
        double ans=0.0;
        for(int i=0;i<=v.size()-2;i++){
            int l=lower_bound(mp.begin(),mp.end(),v[i].l)-mp.begin();
            int r=lower_bound(mp.begin(),mp.end(),v[i].r)-mp.begin();
            l++,r++;
            if(l<r) update(1,1,m,l,r-1,v[i].val);
            ans+=two[1]*(v[i+1].h-v[i].h);
        }
        printf("%.2f\n",ans+eps);
    }
    return 0;
}

HDU 3642

题目要求

求矩形面积并(至少三次)

参考AC代码

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
#include<bits/stdc++.h>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
typedef __int64 lld;
const int maxn = 2222;
int x[maxn],z[maxn],n,cntx,cntz;
int sum[maxn<<2],once[maxn<<2],twice[maxn<<2];
int cover[maxn<<2];
struct seg{
    int l,r,h;
    int flag;
    seg(){};
    seg(int _l,int _r,int _h,int _flag):l(_l),r(_r),h(_h),flag(_flag){}
    bool operator < (const seg &cmp)const {
        if(h==cmp.h) return flag>cmp.flag;
        return h<cmp.h;
    }
}ss[maxn];
struct point {
    int x,y,z;
    void get(){
        scanf("%d%d%d",&x,&y,&z);
    }
};
struct pp{
    point a,b;
}cube[1111];
void pushup(int rt,int l,int r){
    if(cover[rt]==3){
        sum[rt]=x[r+1]-x[l];
        once[rt]=0;
        twice[rt]=0;
        return ;
    }
    if(cover[rt]==2){
        sum[rt]=once[rt<<1]+once[rt<<1|1]+sum[rt<<1]+sum[rt<<1|1]+twice[rt<<1]+twice[rt<<1|1];
        once[rt]=0;
        twice[rt]=x[r+1]-x[l]-sum[rt];
        return ;
    }
    if(cover[rt]==1){
        sum[rt]=twice[rt<<1]+twice[rt<<1|1]+sum[rt<<1]+sum[rt<<1|1];
        twice[rt]=once[rt<<1]+once[rt<<1|1];
        once[rt]=x[r+1]-x[l]-sum[rt]-twice[rt];
        return ;
    }
    if(cover[rt]==0){
        sum[rt]=sum[rt<<1]+sum[rt<<1|1];
        once[rt]=once[rt<<1]+once[rt<<1|1];
        twice[rt]=twice[rt<<1]+twice[rt<<1|1];
        return ;
    }
}
void update(int L,int R,int c,int l,int r,int rt){
    if(L<=l&&r<=R){
        cover[rt]+=c;
        pushup(rt,l,r);
        return ;
    }
    int m=(l+r)>>1;
    if(L<=m) update(L,R,c,lson);
    if(R>m) update(L,R,c,rson);
    pushup(rt,l,r);
}
lld solve(){
    sort(x,x+cntx);
    sort(z,z+cntz);
    cntx=unique(x,x+cntx)-x;
    cntz=unique(z,z+cntz)-z;
    lld ans=0;
    for(int i=0;i<cntz-1;i++){
        int tot=0;
        for(int j=1;j<=n;j++){
            if(cube[j].a.z<=z[i] && cube[j].b.z>z[i])
            {
                int x1=cube[j].a.x,x2=cube[j].b.x;
                int y1=cube[j].a.y,y2=cube[j].b.y;
                ss[tot++]=seg(x1,x2,y1,1);
                ss[tot++]=seg(x1,x2,y2,-1);
            }
        }
        memset(cover,0,sizeof(cover));
        memset(sum,0,sizeof(sum));
        memset(once,0,sizeof(0));
        memset(twice,0,sizeof(twice));
        sort(ss,ss+tot);
        lld area=0;
        int left=lower_bound(x,x+cntx,ss[0].l)-x;
        int right=lower_bound(x,x+cntx,ss[0].r)-x-1;
        update(left,right,ss[0].flag,0,cntx-1,1);
        for(int j=1;j<tot;j++){
            area+=(lld)sum[1]*(ss[j].h-ss[j-1].h);
            left=lower_bound(x,x+cntx,ss[j].l)-x;
            right=lower_bound(x,x+cntx,ss[j].r)-x-1;
            update(left,right,ss[j].flag,0,cntx-1,1);
        }
        ans+=area*(z[i+1]-z[i]);
    }
    return ans;
}
int Case=1;
int main(){
//    freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        cntx=cntz=0;
        for(int i=1;i<=n;i++){
            cube[i].a.get();
            x[cntx++]=cube[i].a.x;
            z[cntz++]=cube[i].a.z;
            cube[i].b.get();
            x[cntx++]=cube[i].b.x;
            z[cntz++]=cube[i].b.z;
        }
        if(n<3){
            printf("Case %d: 0\n",Case++);
            continue;
        }
        lld ans=solve();
        printf("Case %d: %I64d\n",Case++,ans);
    }
    return 0;
}

HDU 4553

题目要求

Problem Description
寒假来了，又到了小明和女神们约会的季节。
小明虽为屌丝级码农，但非常活跃，女神们常常在小明网上的大段发言后热情回复“呵呵”，所以，小明的最爱就是和女神们约会。
与此同时，也有很多基友找他开黑，由于数量实在过于巨大，怎么安排时间便成了小明的一大心事。
我们已知小明一共有T的空闲时间，期间会有很多女神或者基友来找小明。
作为一个操作系统曾经怒考71分的大神，小明想到了一个算法，即“首次适应算法”，根据操作系统课本的描述，就是找一段最靠前的符合要求的连续空间分配给每个请求，由此小明做出了一个决定：
当一个基友来找小明时，小明就根据“首次适应算法”来找一段空闲的时间来和基友约好，如果找到，就说“X,let’s fly”（此处，X为开始时间），否则就说“fly with yourself”；
当女神来找小明时，先使用一次“首次适应算法”，如果没有找到，小明就冒着木叽叽的风险无视所有屌丝基友的约定，再次使用“无视基友首次适应算法”，两次只要有一次找到，就说“X,don’t put my gezi”（此处，X为开始时间），否则就说“wait for me”
当然，我们知道小明不是一个节操负无穷的人，如果和女神约会完，还有剩余时间，他还是会和原来约好的基友去dota的。（举个例子：小西（屌丝）和小明约好在1~5这个时间单位段内打dota，这时候，女神来和小明预约长度为3的时间段，那么最终就是1~3小明去和女神约会，搞定后在4~5和小西打dota）
小明偶尔也会想要学习新知识，此时小明就会把某一个时间区间的所有已经预定的时间全部清空用来学习并且怒吼“I am the hope of chinese chengxuyuan!!”，不过小明一般都是三分钟热度，再有人来预定的话，小明就会按耐不住寂寞把学习新知识的时间分配出去。

Input
输入第一行为CASE，表示有CASE组测试数据；
每组数据以两个整数T，N开始，T代表总共的时间，N表示预约请求的个数；
接着的N行，每行表示一个女神或者基友的预约，“NS QT”代表一个女神来找小明约一段长为QT的时间，“DS QT”则代表一个屌丝的长为QT的请求，当然也有可能是小明想学知识了，“STUDY!! L R”代表清空L~R区间内的所有请求。

Output
对于每一个case，第一行先输出“Case C:”代表是第几个case，然后N行，每行对应一个请求的结果(参照描述)。
输出样本(可复制此处)：
“X,let’s fly”,”fly with yourself”,”X,don’t put my gezi”,”wait for me”,”I am the hope of chinese chengxuyuan!!”

参考AC代码

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int T,n,m;
struct Node{
    int l,r;
    int Max,Lmax,Rmax;
    int Max1,Lmax1,Rmax1;
}segTree[maxn*4];
void push_up(int x){
    if(segTree[x].l==segTree[x].r)return;
    int lson=2*x,rson=2*x+1;
    segTree[x].Lmax=segTree[lson].Lmax;
    if(segTree[lson].Lmax==segTree[lson].r-segTree[lson].l+1)segTree[x].Lmax+=segTree[rson].Lmax;
    segTree[x].Rmax=segTree[rson].Rmax;
    if(segTree[rson].Rmax==segTree[rson].r-segTree[rson].l+1)segTree[x].Rmax+=segTree[lson].Rmax;
    segTree[x].Max=max(segTree[lson].Max,segTree[rson].Max);
    segTree[x].Max=max(segTree[x].Max,max(segTree[x].Lmax,segTree[x].Rmax));
    segTree[x].Max=max(segTree[x].Max,segTree[lson].Rmax+segTree[rson].Lmax);
    //
    segTree[x].Lmax1=segTree[lson].Lmax1;
    if(segTree[lson].Lmax1==segTree[lson].r-segTree[lson].l+1)segTree[x].Lmax1+=segTree[rson].Lmax1;
    segTree[x].Rmax1=segTree[rson].Rmax1;
    if(segTree[rson].Rmax1==segTree[rson].r-segTree[rson].l+1)segTree[x].Rmax1+=segTree[lson].Rmax1;
    segTree[x].Max1=max(segTree[lson].Max1,segTree[rson].Max1);
    segTree[x].Max1=max(segTree[x].Max1,max(segTree[x].Lmax1,segTree[x].Rmax1));
    segTree[x].Max1=max(segTree[x].Max1,segTree[lson].Rmax1+segTree[rson].Lmax1);
}
void push_down(int x){
    if(segTree[x].l==segTree[x].r)return;
    int lson=2*x,rson=2*x+1;
    if(segTree[x].Max==0){
        segTree[lson].Max=segTree[lson].Lmax=segTree[lson].Rmax=0;
        segTree[rson].Max=segTree[rson].Lmax=segTree[rson].Rmax=0;
    }
    if(segTree[x].Max==segTree[x].r-segTree[x].l+1){
        segTree[lson].Max=segTree[lson].Lmax=segTree[lson].Rmax=segTree[lson].r-segTree[lson].l+1;
        segTree[rson].Max=segTree[rson].Lmax=segTree[rson].Rmax=segTree[rson].r-segTree[rson].l+1;
    }
    if(segTree[x].Max1==0){
        segTree[lson].Max1=segTree[lson].Lmax1=segTree[lson].Rmax1=0;
        segTree[rson].Max1=segTree[rson].Lmax1=segTree[rson].Rmax1=0;
    }
    if(segTree[x].Max1==segTree[x].r-segTree[x].l+1){
        segTree[lson].Max1=segTree[lson].Lmax1=segTree[lson].Rmax1=segTree[lson].r-segTree[lson].l+1;
        segTree[rson].Max1=segTree[rson].Lmax1=segTree[rson].Rmax1=segTree[rson].r-segTree[rson].l+1;
    }
}
void build(int rt,int l,int r){
    segTree[rt].l=l;
    segTree[rt].r=r;
    segTree[rt].Max=segTree[rt].Lmax=segTree[rt].Rmax=r-l+1;
    segTree[rt].Max1=segTree[rt].Lmax1=segTree[rt].Rmax1=r-l+1;
    if(l==r) return;
    int mid=(l+r)/2;
    build(rt<<1,l,mid);
    build((rt<<1)|1,mid+1,r);
}
int query(int rt,int x){
    if(segTree[rt].Max<x) return 0;
    if(segTree[rt].Lmax>=x) return segTree[rt].l;
    if(segTree[rt<<1].Max>=x) return query(rt<<1,x);
    if(segTree[rt<<1].Rmax+segTree[(rt<<1)|1].Lmax>=x) return segTree[rt<<1].r-segTree[rt<<1].Rmax+1;
    return query((rt<<1)|1,x);
}
int query1(int rt,int x){
    if(segTree[rt].Max1<x) return 0;
    if(segTree[rt].Lmax1>=x) return segTree[rt].l;
    if(segTree[rt<<1].Max1>=x) return query1(rt<<1,x);
    if(segTree[rt<<1].Rmax1+segTree[(rt<<1)|1].Lmax1>=x) return segTree[rt<<1].r-segTree[rt<<1].Rmax1+1;
    return query1((rt<<1)|1,x);
}
void update(int rt,int l,int r){
    if(segTree[rt].l==l && segTree[rt].r==r){
        segTree[rt].Max=segTree[rt].Lmax=segTree[rt].Rmax=segTree[rt].r-segTree[rt].l+1;
        segTree[rt].Max1=segTree[rt].Lmax1=segTree[rt].Rmax1=segTree[rt].r-segTree[rt].l+1;
        return;
    }
    push_down(rt);
    int mid=(segTree[rt].l+segTree[rt].r)/2;
    if(r<=mid) update(rt<<1,l,r);
    else if(l>mid) update((rt<<1)|1,l,r);
    else update(rt<<1,l,mid),update((rt<<1)|1,mid+1,r);
    push_up(rt);
}
void zhan1(int rt,int l,int r){
    if(segTree[rt].l==l && segTree[rt].r==r){
        segTree[rt].Max=segTree[rt].Lmax=segTree[rt].Rmax=0;
        return;
    }
    push_down(rt);
    int mid=(segTree[rt].l+segTree[rt].r)/2;
    if(r<=mid) zhan1(rt<<1,l,r);
    else if(l>mid) zhan1((rt<<1)|1,l,r);
    else zhan1(rt<<1,l,mid),zhan1((rt<<1)|1,mid+1,r);
    push_up(rt);
}
void zhan2(int rt,int l,int r){
    if(segTree[rt].l==l && segTree[rt].r==r){
        segTree[rt].Max=segTree[rt].Lmax=segTree[rt].Rmax=0;
        segTree[rt].Max1=segTree[rt].Lmax1=segTree[rt].Rmax1=0;
        return;
    }
    push_down(rt);
    int mid=(segTree[rt].l+segTree[rt].r)/2;
    if(r<=mid) zhan2(rt<<1,l,r);
    else if(l>mid) zhan2((rt<<1)|1,l,r);
    else zhan2(rt<<1,l,mid),zhan2((rt<<1)|1,mid+1,r);
    push_up(rt);
}
char op[20];
int Case=1;
int x;
int main(){
//	freopen("input.txt","r",stdin);
    scanf("%d",&T);
    while(T--){
        printf("Case %d:\n",Case++);
        scanf("%d%d",&n,&m);
        build(1,1,n);
        while(m--){
            scanf("%s",op);
            if(op[0]=='D'){
				scanf("%d",&x);
                int tmp=query(1,x);
                if(tmp==0) printf("fly with yourself\n");
                else{
                    zhan1(1,tmp,tmp+x-1);
                    printf("%d,let's fly\n",tmp);
                }
            }
            else if(op[0]=='N'){
                scanf("%d",&x);
                int tmp=query(1,x);
                if(tmp!=0){
                    zhan2(1,tmp,tmp+x-1);
                    printf("%d,don't put my gezi\n",tmp);
                    continue;
                }
                tmp=query1(1,x);
                if(tmp!=0){
                    zhan2(1,tmp,tmp+x-1);
                    printf("%d,don't put my gezi\n",tmp);
                    continue;
                }
                printf("wait for me\n");
            }
            else{
            	int l,r;
                scanf("%d%d",&l,&r);
                printf("I am the hope of chinese chengxuyuan!!\n");
                update(1,l,r);
            }
        }
    }
    return 0;
}

思路

相当于2个线段树维护屌丝和女神的空余时间
线段树用来合并连续的时间段 分别维护2个部分即可
query查找第一个能放得下某个时间的区间左端点
zhan1 zhan2和update是三个区间更新操作
分别表示更新屌丝占用的时间 女神占有的时间 和区间清空
这里注意女神时间的优先级是大于屌丝的 所以维护时也会把屌丝的时间更新

本文标题:线段树代码仓库

文章作者:Hippopmonkey

发布时间:2017-11-17, 13:34:24

最后更新:2017-11-21, 13:37:45

原始链接:http://xuboming8.github.io/2017/11/17/线段树代码仓库/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 线段树代码仓库
    1. 1.1. zoj 1610
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. poj 2528
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. HDU 4027
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. HDU 3308
    5. 1.5. HDU 1540
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. bzoj 1135
      1. 1.6.1. 参考AC代码
    7. 1.7. HDU 4614
      1. 1.7.1. 题目要求
      2. 1.7.2. 参考AC代码
      3. 1.7.3. 思路
    8. 1.8. HDU 1225
      1. 1.8.1. 题目要求
      2. 1.8.2. 参考AC代码
    9. 1.9. HDU 3642
      1. 1.9.1. 题目要求
      2. 1.9.2. 参考AC代码
    10. 1.10. HDU 4553
      1. 1.10.1. 题目要求
      2. 1.10.2. 参考AC代码
      3. 1.10.3. 思路
|