Solve

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 (省选)