POJ3667线段树

题目解答

裸的线段树,线段树能解决的问题很多,这道题目是非常典型的线段染色问题。有三种状态,无色(空),满色(有人),杂色。主要考察的也就是实现线段树的惰性,即懒操作。修改颜色时不是一改到底的,在适当粒度的区间做好标记,当出现更细粒度(小于某个区间)的操作时再下放。例如:区间[1,10]标记为客满,同时区间[1,2]标记为空是可以在某些时刻共存的,想想为什么。

运行情况

POJ3667

程序清单

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
#include<iostream>
#define MAX(a,b) ((a)>(b)?(a):(b))
using namespace std;

const long MAX=999999;
struct node{
long lch,rch,left,right,lnum,rnum,num,mid,all;
int mark; //0空,1满,2杂色
}tree[400001];
long tot=1,n,q;
class regtree{
public:
void build(long left,long right,long index){
tree[index].left=left;
tree[index].right=right;
tree[index].mid=(left+right)/2;
tree[index].all=right-left+1;
tree[index].lnum=tree[index].rnum=tree[index].num=tree[index].all;
tree[index].mark=0;
if(left<right){
tree[index].lch=++tot;
build(left,tree[index].mid,tot);
tree[index].rch=++tot;
build(tree[index].mid+1,right,tot);
}
}
void refresh(long index){
long Max=0,lch=tree[index].lch,rch=tree[index].rch;
Max=MAX(Max,tree[lch].rnum+tree[rch].lnum);
Max=MAX(MAX(Max,tree[lch].num),tree[rch].num);
tree[index].num=Max;
if(tree[lch].lnum<tree[lch].all) tree[index].lnum=tree[lch].lnum;
else tree[index].lnum=tree[lch].lnum+tree[rch].lnum;
if(tree[rch].rnum<tree[rch].all) tree[index].rnum=tree[rch].rnum;
else tree[index].rnum=tree[rch].rnum+tree[lch].rnum;
if(tree[lch].mark!=tree[rch].mark) tree[index].mark=2;
else tree[index].mark=tree[lch].mark;
}
void downset(long index,int mark){
long lch=tree[index].lch,rch=tree[index].rch;
if(mark==1){
tree[lch].num=tree[lch].lnum=tree[lch].rnum=0;
tree[rch].num=tree[rch].lnum=tree[rch].rnum=0;
}else{
tree[lch].num=tree[lch].lnum=tree[lch].rnum=tree[lch].all;
tree[rch].num=tree[rch].lnum=tree[rch].rnum=tree[rch].all;
}
tree[lch].mark=tree[rch].mark=mark;
tree[index].mark=2;
}
long find(long size,long index){
if(!index) return MAX;
long temp=MAX;
if(tree[index].lnum>=size) temp=tree[index].left;
else{
if(tree[tree[index].lch].num>=size) temp=find(size,tree[index].lch);
else if(tree[tree[index].lch].rnum+tree[tree[index].rch].lnum>=size)
temp=tree[tree[index].lch].right-tree[tree[index].lch].rnum+1;
else if(tree[tree[index].rch].num>=size) temp=find(size,tree[index].rch);
}
return temp;
}
void insert(long left,long right,long index,bool del){
if(!index) return;
if(tree[index].left>=left && tree[index].right<=right){
if(!del) {tree[index].lnum=tree[index].rnum=tree[index].num=0;tree[index].mark=1;}
else {tree[index].lnum=tree[index].rnum=tree[index].num=tree[index].all;tree[index].mark=0;}
}else{
if(tree[index].mark!=2) downset(index,tree[index].mark);
if(left<=tree[index].mid) insert(left,right,tree[index].lch,del);
if(right>tree[index].mid) insert(left,right,tree[index].rch,del);
refresh(index);
}
}
}line;
int main(){
scanf("%d%d",&n,&q);
line.build(1,n,tot);
long a,b,c;
for(long i=1;i<=q;i++){
scanf("%d",&a);
if(a==1){
scanf("%d",&b);
if(tree[1].num<b) printf("0\n");
else{
c=line.find(b,1);
printf("%d\n",c);
line.insert(c,c+b-1,1,false);
}
}else{
scanf("%d%d",&b,&c);
line.insert(b,b+c-1,1,true);
}
}
return 0;
}

难易等级

Middle (省选)