线段树板子

学习NotOnlySuccess的~~

单点更新类(不常用)

HDU 1166 敌兵布阵

经典入门题

中文题...题意略...

数据小可以单点更新区间求和

 1 #define lson l, m, rt<<1
 2 #define rson m+1, r, rt<<1|1  
 3 int sum[500005];
 4 void pushup(int rt)
 5 {
 6     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
 7 }
 8 void build(int l, int r, int rt)
 9 {
10     if(l==r)
11     {
12         scanf("%d", &sum[rt]);
13         return ;
14     }
15     int m=(l+r)>>1;
16     build(lson);
17     build(rson);
18     pushup(rt);
19 }
20 void update(int p, int add, int l, int r, int rt)
21 {
22     if(l==r)
23     {
24         sum[rt]+=add;
25         return ;
26     }
27     int m=(l+r)>>1;
28     if(p<=m)
29         update(p, add, lson);
30     else
31         update(p, add, rson);
32     pushup(rt);
33 }
34 int query(int L, int R, int l, int r, int rt)
35 {
36     if(L<=l && r<=R)
37         return sum[rt];
38     int m=(l+r)>>1;
39     int ret=0;
40     if(L<=m)
41         ret+=query(L, R, lson);
42     if(R>m)
43         ret+=query(L, R, rson);
44     return ret;
45 }
46 int main()
47 {
48 #ifndef ONLINE_JUDGE
49     freopen("in.txt", "r", stdin);
50     freopen("out.txt", "w", stdout);
51 #endif
52     int t, n, ca=1;
53     int a, b;
54     scanf("%d", &t);
55     while(t--)
56     {
57         printf("Case %d:
", ca++);
58         scanf("%d", &n);
59         build(1, n, 1);
60         char op[10];
61         while(~scanf("%s", op))
62         {
63             if(strcmp(op, "End")==0)
64                 break;
65             scanf("%d%d", &a, &b);
66             if(strcmp(op, "Query")==0)
67                 printf("%d
", query(a, b, 1, n, 1));
68             else if(strcmp(op, "Sub")==0)
69                 update(a, -b, 1, n, 1);
70             else
71                 update(a, b, 1, n, 1);
72         }
73     }
74     return 0;
75 }

View Code

HDU 1754 I Hate It

中文题...题意略...

单点更新区间最值

 1 #define lson l, m, rt<<1
 2 #define rson m+1, r, rt<<1|1 
 3 #define M 200005
 4 int num[M<<2];
 5 void pushup(int rt)
 6 {
 7     num[rt]=max(num[rt<<1],num[rt<<1|1]);    
 8 }
 9 void build(int l, int r, int rt)
10 {
11     if(l==r)
12     {
13         scanf("%d", &num[rt]);
14         return ;
15     }
16     int m=(l+r)>>1;
17     build(lson);
18     build(rson);
19     pushup(rt);
20 }
21 void update(int p, int ma, int l, int r, int rt)
22 {
23     if(l==r)
24     {
25         num[rt]=ma;
26         return ;
27     }
28     int m=(l+r)>>1;
29     if(p<=m)
30         update(p, ma, lson);
31     else 
32         update(p, ma, rson);
33     pushup(rt);
34 }
35 int query(int L, int R, int l, int r, int rt)
36 {
37     if(L<=l && R>=r)
38         return num[rt];
39     int m=(l+r)>>1;
40     int ret=0;
41     if(L<=m)
42         ret=max(ret, query(L, R, lson));
43     if(m<R)
44         ret=max(ret, query(L, R, rson));
45     return ret;
46 }
47 int main()
48 {
49 #ifndef ONLINE_JUDGE
50     freopen("in.txt", "r", stdin);
51     freopen("out.txt", "w", stdout);
52 #endif
53     int n, m;
54     int a, b;
55     char op[10];
56     while(~scanf("%d%d", &n, &m))
57     {
58         build(1, n, 1);
59         while(m--)
60         {
61             scanf("%s%d%d", op, &a, &b);
62             if(strcmp(op, "Q")==0)
63                 printf("%d
", query(a, b, 1, n, 1));
64             else 
65                 update(a, b, 1, n, 1);
66         }
67     }
68     return 0;
69 }

View Code

HDU 2795 Billboard

题意:有一块h*w的板子, 要在上面贴n张1*a的海报, 要贴的尽量高, 高度相同的情况, 选择尽量靠左的。输出每张海报的高度位置.

每次找最大的位置减去a即可此题在query里面update了

单点更新区间最值

 1 #define M 200005
 2 #define lson l, m, rt<<1
 3 #define rson m+1, r, rt<<1|1
 4 
 5 int w;
 6 int num[M<<2];
 7 void pushup(int rt)
 8 {
 9     num[rt]=max(num[rt<<1], num[rt<<1|1]);
10 }
11 void build(int l, int r, int rt)
12 {
13     num[rt]=w;
14     if(r==l)
15         return ;
16     int m=(l+r)>>1;
17     build(lson);
18     build(rson);
19 }
20 int query(int p, int l, int r, int rt)
21 {
22     if(l==r)
23     {
24         num[rt]-=p;
25         return l;
26     }
27     int m=(l+r)>>1;
28     int ret;
29     if(p<=num[rt<<1])
30         ret=query(p, lson);
31     else 
32         ret=query(p, rson);
33     pushup(rt);
34     return ret;
35 }
36 /*void update(int p, int l, int r, int rt)
37 {
38     if(l==r)
39     {
40         num[rt]-=p;
41         return ;
42     }
43     int m=(l+r)>>1;
44     if(p<=m)
45         update(p, lson);
46     else 
47         update(p, rson);
48     pushup(rt);
49 }*/
50 int main()
51 {
52 #ifndef ONLINE_JUDGE
53     freopen("in.txt", "r", stdin);
54     freopen("out.txt", "w", stdout);
55 #endif
56     int h, n, a;
57     while(~scanf("%d%d%d", &h, &w, &n))
58     {
59         if(h>n)
60             h=n;
61         build(1, h, 1);
62         while(n--)
63         {
64             scanf("%d", &a);
65             if(a>num[1])
66                 printf("-1
");
67             else 
68             {
69                 printf("%d
",query(a, 1, h, 1));
70             //    update(a, 1, h, 1);
71             }
72         }
73     }
74     return 0;
75 }

View Code

成段更新类

HDU 1698 Just a Hook

题意:n个钩子, 每个初始值是1, m个询问, (a, b)之间的变为c. 最后求整段和.

由于只询问一次, 直接输出sum[1]即可, 不用query了.

 1 #define N 100005
 2 #define lson l, m, rt<<1
 3 #define rson m+1, r, rt<<1|1
 4 
 5 int col[N<<2];
 6 int sum[N<<2];
 7 void pushup(int rt)
 8 {
 9     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
10 }
11 void pushdown(int rt, int m)
12 {
13     if(col[rt])
14     {
15         col[rt<<1]=col[rt<<1|1]=col[rt];
16         sum[rt<<1]=(m-(m>>1))*col[rt];
17         sum[rt<<1|1]=(m>>1)*col[rt];
18         col[rt]=0;
19     }
20 }
21 
22 void build(int l, int r, int rt)
23 {
24     col[rt]=0;
25     sum[rt]=1;
26     if(l==r)
27         return ;
28     int m=(l+r)>>1;
29     build(lson);
30     build(rson);
31     pushup(rt);
32 }
33 
34 void update(int L, int R, int c, int l, int r, int rt)
35 {
36     if(L<=l && r<=R)
37     {
38         col[rt]=c;
39         sum[rt]=c*(r-l+1);
40         return ;
41     }
42     pushdown(rt, r-l+1);
43     int m=(l+r)>>1;
44     if(L<=m)
45         update(L, R, c, lson);
46     if(R>m)
47         update(L, R, c, rson);
48     pushup(rt);
49 }
50 
51 int main()
52 {
53 #ifndef ONLINE_JUDGE
54     freopen("in.txt", "r", stdin);
55     freopen("out.txt", "w", stdout);
56 #endif
57     int t, ca=1, n, m;
58     scanf("%d", &t);
59     while(t--)
60     {
61         scanf("%d%d", &n, &m);
62         build(1, n, 1);
63         while(m--)
64         {
65             int a, b, c;
66             scanf("%d%d%d", &a, &b, &c);
67             update(a, b, c, 1, n, 1);
68         }
69         printf("Case %d: The total value of the hook is %d.
", ca++, sum[1]);
70     }
71     return 0;
72 }

View Code

POJ 3468 ASimple Problem With Integers

题意:给一个数列, 每次给(a, b)之间的加上c, 询问(a, b)的和.

成段更新区间求和

 1 typedef long long LL;
 2 #define N 100005
 3 #define lson l, m, rt<<1
 4 #define rson m+1, r, rt<<1|1
 5 
 6 LL col[N<<2];
 7 LL sum[N<<2];
 8 void pushup(int rt)
 9 {
10     sum[rt]=sum[rt<<1]+sum[rt<<1|1];
11 }
12 void pushdown(int rt, int m)
13 {
14     if(col[rt])
15     {
16         col[rt<<1]+=col[rt];
17         col[rt<<1|1]+=col[rt];
18         sum[rt<<1]+=col[rt]*(m-(m>>1));
19         sum[rt<<1|1]+=col[rt]*(m>>1);
20         col[rt]=0;
21     }
22 }
23 
24 void build(int l, int r, int rt)
25 {
26     col[rt]=0;
27     if(r==l)
28     {
29         scanf("%lld", &sum[rt]);
30         return ;
31     }
32     int m=(l+r)>>1;
33     build(lson);
34     build(rson);
35     pushup(rt);
36 }
37 
38 void update(int L, int R, int c, int l, int r, int rt)
39 {
40     if(L<=l && r<=R)
41     {
42         col[rt]+=c;
43         sum[rt]+=(LL)c*(r-l+1);
44         return ;
45     }
46     pushdown(rt, r-l+1);
47     int m=(l+r)>>1;
48     if(L<=m)
49         update(L, R, c, lson);
50     if(m<R)
51         update(L, R, c, rson);
52     pushup(rt);
53 }
54 
55 LL query(int L, int R, int l, int r, int rt)
56 {
57     if(L<=l && r<=R)
58         return sum[rt];
59     pushdown(rt, r-l+1);
60     int m=(l+r)>>1;
61     LL ret=0;
62     if(L<=m)
63         ret+=query(L, R, lson);
64     if(m<R)
65         ret+=query(L, R, rson);
66     return ret;
67 }
68 
69 int main()
70 {
71 #ifndef ONLINE_JUDGE
72     freopen("in.txt", "r", stdin);
73     freopen("out.txt", "w", stdout);
74 #endif
75     int n, q;
76     scanf("%d%d", &n, &q);
77     build(1, n, 1);
78     while(q--)
79     {
80         char op[2];
81         int a, b, c;
82         scanf("%s", op);
83         scanf("%d%d", &a, &b);
84         if(op[0]=='Q')
85         {
86             printf(LLD, query(a, b, 1, n, 1));
87             puts("");
88         }
89         else
90         {
91             scanf("%d", &c);
92             update(a, b, c, 1, n, 1);
93         }
94     }
95     return 0;
96 }

View Code

上两篇NotOnlySuccess的成段更新的结题报告 (关于Hash的)

poj2528 Mayor’s posters

题意:在墙上贴海报, 海报可以互相覆盖, 问最后可以看见几张海报
思路:这题数据范围很大,直接搞超时+超内存,需要离散化: 离散化简单的来说就是只取我们需要的值来用,比如说区间[1000,2000],[1990,2012]
我们
用不到[-∞,999][1001,1989][1991,1999][2001,2011][2013,+∞]这些值,所以我只需要1000,1990,2000,2012就够了, 将其分别映射到0,1,2,3,在于复杂度就大大的降下来了所以离散化要保存所有需要用到的值,排序后,分别映射到1~n,这样复杂度就会小很多很多而这题的难点在于每个数字其实表示的是一个单位长度(并且一个点),这样普通的离散化会造成许多错误(包括我以前的代码,poj这题数据奇弱)
给出下面两个简单的例子应该能体现普通离散化的缺陷:
1-10 1-4 5-10
1-10 1-4 6-10
为了解决这种缺陷,我们可以在排序后的数组上加些处理,比如说[1,2,6,10] 如果相邻数字间距大于1的话,在其中加上任意一个数字,比如加成[1,2,3,6,7,10],然后再做线段树就好了.
线段树功能:update:成段替换query:简单hash

  1 #define N 10005
  2 #define lson l, m, rt<<1
  3 #define rson m+1, r, rt<<1|1
  4 
  5 int col[N<<4], x[N<<4];
  6 bool hash[N<<2];
  7 int cnt;
  8 void pushdown(int rt)
  9 {
 10     if(col[rt]!=-1)
 11     {
 12         col[rt<<1]=col[rt<<1|1]=col[rt];
 13         col[rt]=-1;
 14     }
 15 }
 16 
 17 void update(int L, int R, int c, int l, int r, int rt)
 18 {
 19     if(L<=l && r<=R)
 20     {
 21         col[rt]=c;
 22         return ;
 23     }
 24     pushdown(rt);
 25     int m=(l+r)>>1;
 26     if(L<=m)
 27         update(L, R, c, lson);
 28     if(m<R)
 29         update(L, R, c, rson);
 30 }
 31 
 32 void query(int l, int r, int rt)
 33 {
 34     if(col[rt]!=-1)
 35     {
 36         if(hash[col[rt]]==0)
 37             cnt++;
 38         hash[col[rt]]=1;
 39         return ;
 40     }
 41     if(l==r)
 42         return ;
 43     int m=(l+r)>>1;
 44     query(lson);
 45     query(rson);
 46 }
 47 
 48 int bin(int key, int n)
 49 {
 50     int l=0, r=n-1;
 51     while(l<=r)
 52     {
 53         int m=(l+r)>>1;
 54         if(x[m]==key)
 55             return m;
 56         if(x[m]<key)
 57             l=m+1;
 58         else
 59             r=m-1;
 60     }
 61     return -1;
 62 }
 63 
 64 int a[N<<2], b[N<<2];
 65 
 66 int main()
 67 {
 68 #ifndef ONLINE_JUDGE
 69     freopen("in.txt", "r", stdin);
 70     freopen("out.txt", "w", stdout);
 71 #endif
 72     int t, n;
 73     scanf("%d", &t);
 74     while(t--)
 75     {
 76         scanf("%d", &n);
 77         int  d=0;
 78         for(int i=0;i<n;i++)
 79         {
 80             scanf("%d%d", &a[i], &b[i]);
 81             x[d++]=a[i];
 82             x[d++]=b[i];
 83         }
 84         sort(x, x+d);
 85         int num=1;
 86         for(int i=1;i<d;i++)
 87             if(x[i]!=x[i-1])
 88                 x[num++]=x[i];
 89         for(int i=num-1;i>0;i--)
 90             if(x[i]!=x[i-1]+1)
 91                 x[num++]=x[i-1]+1;
 92         sort(x, x+num);
 93         fill(col, col+(N<<4), -1);
 94  //       memset(col, -1, sizeof(col));
 95         for(int i=0;i<n;i++)
 96         {
 97             int l=bin(a[i], num);
 98             int r=bin(b[i], num);
 99             update(l, r, i, 0, num-1, 1);
100         }
101         cnt=0;
102         memset(hash, 0, sizeof(hash));
103         query(0, num-1, 1);
104         printf("%d
", cnt);
105     }
106     return 0;
107 }

View Code

poj3225 Help with Intervals

题意:区间操作, 交, 并, 补等
思路: 我们一个一个操作来分析:(用0和1表示是否包含区间,-1表示该区间内既有包含又有不包含)
U:把区间[l,r]覆盖成1
I:把[-∞,l)(r,∞]覆盖成0
D:把区间[l,r]覆盖成0
C:把[-∞,l)(r,∞]覆盖成0 , 且[l,r]区间0/1互换
S:[l,r]区间0/1互换
成段覆盖的操作很简单,比较特殊的就是区间0/1互换这个操作,我们可以称之为异或操作
很明显我们可以知道这个性质:当一个区间被覆盖后,不管之前有没有异或标记都没有意义了
所以当一个节点得到覆盖标记时把异或标记清空
而当一个节点得到异或标记的时候,先判断覆盖标记,如果是0或1,直接改变一下覆盖标记,不然的话改变异或标记
开区间闭区间只要数字乘以2就可以处理(偶数表示端点,奇数表示两端点间的区间)
线段树功能:update:成段替换,区间异或 query:简单hash

  1 #define N 100005
  2 #define lson l, m, rt<<1
  3 #define rson m+1, r, rt<<1|1
  4 const int maxn=131072;
  5 int cover[maxn<<2], Xor[maxn<<2];
  6 bool hash[maxn<<2];
  7 void pushdown(int rt)
  8 {
  9     if(cover[rt]!=-1)
 10     {
 11         cover[rt<<1]=cover[rt<<1|1]=cover[rt];
 12         Xor[rt<<1]=Xor[rt<<1|1]=0;
 13         cover[rt]=-1;
 14     }
 15     if(Xor[rt])
 16     {
 17         if(cover[rt<<1]!=-1)
 18             cover[rt<<1]^=1;
 19         else
 20             Xor[rt<<1]^=1;
 21         if(cover[rt<<1|1]!=-1)
 22             cover[rt<<1|1]^=1;
 23         else
 24             Xor[rt<<1|1]^=1;
 25         Xor[rt]=0;
 26     }
 27 }
 28 
 29 void update(char op, int L, int R, int l, int r, int rt)
 30 {
 31     if(L<=l && r<=R)
 32     {
 33         if(op=='U')
 34         {
 35             cover[rt]=1;
 36             Xor[rt]=0;
 37         }
 38         else if(op=='D')
 39         {
 40             cover[rt]=0;
 41             Xor[rt]=0;
 42         }
 43         else if(op=='C' || op=='S')
 44         {
 45             if(cover[rt]!=-1)
 46                 cover[rt]^=1;
 47             else
 48                 Xor[rt]^=1;
 49         }
 50         return ;
 51     }
 52     pushdown(rt);
 53     int m=(l+r)>>1;
 54     if(L<=m)
 55         update(op, L, R, lson);
 56     else if(op=='I' || op=='C')
 57         Xor[rt<<1]=cover[rt<<1]=0;
 58     if(m<R)
 59         update(op, L, R, rson);
 60     else if(op=='I' || op=='C')
 61         Xor[rt<<1|1]=cover[rt<<1|1]=0;
 62 }
 63 
 64 void query(int l, int r, int rt)
 65 {
 66     if(cover[rt]==1)
 67     {
 68         fill(hash+l, hash+r+1, 1);
 69         return ;
 70     }
 71     else if(cover[rt]==0)
 72         return ;
 73     pushdown(rt);
 74     int m=(l+r)>>1;
 75     query(lson);
 76     query(rson);
 77 }
 78 
 79 int main()
 80 {
 81 #ifndef ONLINE_JUDGE
 82     freopen("in.txt", "r", stdin);
 83     freopen("out.txt", "w", stdout);
 84 #endif
 85     cover[1]=Xor[1]=0;
 86     char op, l, r;
 87     int a, b;
 88     while(~scanf("%c %c%d,%d%c%*c", &op, &l, &a, &b, &r))
 89     {
 90         a<<=1, b<<=1;
 91         if(l=='(')
 92             a++;
 93         if(r==')')
 94             b--;
 95         if(a>b)
 96         {
 97             if(op=='C' || op=='I')
 98                 cover[1]=Xor[1]=0;
 99         }
100         else
101             update(op, a, b, 0, maxn, 1);
102     }
103     query(0, maxn, 1);
104     bool flag=0;
105     int s=-1, e;
106     for(int i=0; i<=maxn; i++)
107     {
108         if(hash[i])
109         {
110             if(s==-1)
111                 s=i;
112             e=i;
113         }
114         else if(s!=-1)
115         {
116             if(flag)
117                 printf(" ");
118             flag=1;
119             printf("%c%d,%d%c", s&1? '(':'[', s>>1, (e+1)>>1, e&1? ')':']');
120             s=-1;
121         }
122     }
123     if(flag==0)
124         printf("empty set");
125     printf("
");
126     return 0;
127 }

View Code

区间合并类(在pushup里合并左右儿子)

POJ 3667 Hotel

题意:1 a:询问是不是有连续长度为a的空房间,有的话住进最左边
2 a b:将[a,a+b-1]的房间清空

区间替换询问左端点

 1 #define lson l, m, rt<<1
 2 #define rson m+1, r, rt<<1|1
 3 
 4 int lsum[500005], msum[500005], rsum[500005];
 5 int col[500005];
 6 
 7 void pushdown(int rt, int m)
 8 {
 9     if(col[rt]!=-1)
10     {
11         col[rt<<1]=col[rt<<1|1]=col[rt];
12         lsum[rt<<1]=msum[rt<<1]=rsum[rt<<1]=col[rt]? 0:m-(m>>1);
13         lsum[rt<<1|1]=msum[rt<<1|1]=rsum[rt<<1|1]=col[rt]? 0:(m>>1);
14         col[rt]=-1;
15     }
16 }
17 void pushup(int rt, int m)
18 {
19     lsum[rt]=lsum[rt<<1];
20     rsum[rt]=rsum[rt<<1|1];
21     if(lsum[rt]==m-(m>>1))
22         lsum[rt]+=lsum[rt<<1|1];
23     if(rsum[rt]==(m>>1))
24         rsum[rt]+=rsum[rt<<1];
25     msum[rt]=max(lsum[rt<<1|1]+rsum[rt<<1], max(msum[rt<<1], msum[rt<<1|1]));
26 }
27 void build(int l, int r, int rt)
28 {
29     lsum[rt]=msum[rt]=rsum[rt]=r-l+1;
30     col[rt]=-1;
31     if(l==r)
32         return ;
33     int m=(l+r)>>1;
34     build(lson);
35     build(rson);
36 }
37 void update(int L, int R, int c, int l, int r, int rt)
38 {
39     if(L<=l && r<=R)
40     {
41         lsum[rt]=msum[rt]=rsum[rt]=c? 0: r-l+1;
42         col[rt]=c;
43         return ;
44     }
45     pushdown(rt, r-l+1);
46     int m=(l+r)>>1;
47     if(L<=m)
48         update(L, R, c, lson);
49     if(m<R)
50         update(L, R, c, rson);
51     pushup(rt, r-l+1);
52 }
53 int query(int p, int l, int r, int rt)
54 {
55     if(l==r)
56         return l;
57     pushdown(rt, r-l+1);
58     int m=(l+r)>>1;
59     if(msum[rt<<1]>=p)
60         return query(p, lson);
61     else if(lsum[rt<<1|1]+rsum[rt<<1]>=p)
62         return m-rsum[rt<<1]+1;
63     return query(p, rson);
64 }
65 int main()
66 {
67     int n, m, op, a, b, p;
68     scanf("%d%d", &n, &m);
69     build(1, n, 1);
70     while(m--)
71     {
72         scanf("%d", &op);
73         if(op==1)
74         {
75             scanf("%d", &a);
76             if(msum[1]<a)
77                 printf("0
");
78             else
79             {
80                 p=query(a, 1, n, 1);
81                 printf("%d
", p);
82                 update(p, p+a-1, 1, 1, n, 1);
83             }
84         }
85         else
86         {
87             scanf("%d%d", &a, &b);
88             update(a, a+b-1, 0, 1, n, 1);
89         }
90     }
91     return 0;
92 }

View Code

  1 const int N=50005;
  2 int lsum[N<<2], rsum[N<<2], msum[N<<2];
  3 struct node
  4 {
  5     int l, r;
  6 }segTree[N<<2];
  7 //int col[N<<2];
  8 int X[N];
  9 void pushup(int rt, int m)
 10 {
 11     lsum[rt]=lsum[rt<<1];
 12     rsum[rt]=rsum[rt<<1|1];
 13     if(lsum[rt<<1]==segTree[rt<<1].r-segTree[rt<<1].l+1)
 14         lsum[rt]+=lsum[rt<<1|1];
 15     if(rsum[rt<<1|1]==segTree[(rt<<1)|1].r-segTree[(rt<<1)|1].l+1)
 16         rsum[rt]+=rsum[rt<<1];
 17 //    if(lsum[rt]==m)
 18 //        lsum[rt]+=lsum[rt<<1|1];
 19 //    if(rsum[rt]==m)
 20 //        rsum[rt]+=rsum[rt<<1];
 21     msum[rt]=max(lsum[rt<<1|1]+rsum[rt<<1], max(msum[rt<<1], msum[rt<<1|1]));
 22 }
 23 //void pushdown(int rt, int m)
 24 //{
 25 //    if(col[rt]!=-1)
 26 //    {
 27 //        col[rt<<1]=col[rt<<1|1]=col[rt];
 28 //        lsum[rt<<1]=msum[rt<<1]=rsum[rt<<1]=col[rt]? 0:m-(m>>1);
 29 //        lsum[rt<<1|1]=msum[rt<<1|1]=rsum[rt<<1|1]=col[rt]? 0:(m>>1);
 30 //        col[rt]=-1;
 31 //    }
 32 //}
 33 void build(int l, int r, int rt)
 34 {
 35     segTree[rt].l=l;
 36     segTree[rt].r=r;
 37     lsum[rt]=rsum[rt]=msum[rt]=r-l+1;
 38 //    col[rt]=-1;
 39     if(l==r)
 40         return ;
 41     int m=(l+r)>>1;
 42     build(lson);
 43     build(rson);
 44 }
 45 void update(int p, int c, int l, int r, int rt)
 46 {
 47     if(l==r)
 48     {
 49         lsum[rt]=rsum[rt]=msum[rt]=c;
 50         return ;
 51     }
 52     int m=(l+r)>>1;
 53     if(p<=m)
 54         update(p, c, lson);
 55     else
 56         update(p, c, rson);
 57     pushup(rt, r-l+1);
 58 }
 59 int query(int p, int l, int r, int rt)
 60 {
 61     if(l==r || msum[rt]==0 || msum[rt]==r-l+1)
 62         return msum[rt];
 63 //    pushdown(rt, r-l+1);
 64     int m=(l+r)>>1;
 65     if(m>=p)
 66     {
 67 //        if(p>=(r>>1)-rsum[rt]+1)
 68         if(p>=segTree[rt<<1].r-rsum[rt<<1]+1)
 69             return query(p, lson)+query(m+1, rson);
 70         else
 71             return query(p, lson);
 72     }
 73     else
 74     {
 75 //        if(p<=(l>>1|1)+lsum[rt]-1)
 76         if(p<=segTree[(rt<<1)|1].l+lsum[rt<<1|1]-1)
 77             return query(m, lson)+query(p, rson);
 78         else
 79             return query(p, rson);
 80     }
 81 }
 82 int main()
 83 {
 84     int n, m;
 85     while(~scanf("%d%d", &n, &m))
 86     {
 87         build(1, n, 1);
 88         int d=0, a;
 89         while(m--)
 90         {
 91             char op[2];
 92             scanf("%s", op);
 93             if(op[0]=='D')
 94             {
 95                 scanf("%d", &a);
 96                 X[d++]=a;
 97                 update(a, 0, 1, n, 1);
 98             }
 99             else if(op[0]=='Q')
100             {
101                 scanf("%d", &a);
102                 printf("%d
", query(a, 1, n, 1));
103             }
104             else
105             {
106                 if(d)
107                 {
108                     a=X[--d];
109                     update(a, 1, 1, n, 1);
110                 }
111             }
112         }
113     }
114     return 0;
115 }

HDOJ 1540

扫描线类(求面积或周长)

HDU 1542 Atlantis

题意:给n个海报的左上和右下坐标, 问最后有多少露出来的面积.

 1 #define lson l, m, rt<<1
 2 #define rson m+1, r, rt<<1|1
 3 #define N 2005
 4 
 5 int cnt[N<<2];
 6 double sum[N<<2];
 7 double X[N];
 8 struct Seg
 9 {
10     double h, l, r;
11     int s;
12     Seg() {}
13     Seg(double a, double b, double c, int d) : l(a), r(b), h(c), s(d) {}
14     bool operator < (const Seg &cmp) const
15     {
16         return h<cmp.h;
17     }
18 }ss[N];
19 void pushup(int rt, int l, int r)
20 {
21     if(cnt[rt])
22         sum[rt]=X[r+1]-X[l];
23     else if(l==r)
24         sum[rt]=0;
25     else
26         sum[rt]=sum[rt<<1]+sum[rt<<1|1];
27 }
28 void update(int L, int R, int c, int l, int r, int rt)
29 {
30     if(L<=l && r<=R)
31     {
32         cnt[rt]+=c;
33         pushup(rt, l, r);
34         return ;
35     }
36     int m=(l+r)>>1;
37     if(L<=m)
38         update(L, R, c, lson);
39     if(m<R)
40         update(L, R, c, rson);
41     pushup(rt, l, r);
42 }
43 
44 int main()
45 {
46 #ifndef ONLINE_JUDGE
47     freopen("in.txt", "r", stdin);
48     freopen("out.txt", "w", stdout);
49 #endif
50     int n, ca=1;
51     while(~scanf("%d", &n) && n)
52     {
53         int m=0;
54         while(n--)
55         {
56             double a, b, c, d;
57             scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
58             X[m]=a;
59             ss[m++]=Seg(a, c, b, 1);
60             X[m]=c;
61             ss[m++]=Seg(a, c, d, -1);
62         }
63         sort(X, X+m);
64         sort(ss, ss+m);
65         int k=1;
66         for(int i=1;i<m;i++)
67             if(X[i]!=X[i-1])
68                 X[k++]=X[i];
69         memset(cnt, 0, sizeof(cnt));
70         memset(sum, 0, sizeof(sum));
71         double ret=0;
72         for(int i=0;i<m-1;i++)
73         {
74             int l=lower_bound(X, X+k, ss[i].l)-X;
75             int r=lower_bound(X, X+k, ss[i].r)-X-1;
76             if(l<=r)
77                 update(l, r, ss[i].s, 0, k-1, 1);
78             ret+=sum[1]*(ss[i+1].h-ss[i].h);
79         }
80         printf("Test case #%d
Total explored area: %.2lf

", ca++, ret);
81     }
82     return 0;
83 }

View Code

HDU 4419 Colorful Rectangle

题意:有RGB三种颜色, 给出方块要涂的颜色以及左上和右下坐标, 然后依次输出颜色为R, G, B, RG, RB, GB, RGB的面积.

  1 #define lson l , m , rt << 1
  2 #define rson m + 1 , r , rt << 1 | 1
  3 const int maxn = 10005;
  4 int X[maxn<<3];
  5 
  6 struct Seg
  7 {
  8     int h , l , r, s;
  9     Seg() {}
 10     Seg(int a,int b,int c,int d) : l(a) , r(b) , h(c) , s(d) {}
 11     bool operator < (const Seg &cmp) const
 12     {
 13         return h < cmp.h;
 14     }
 15 } ss[maxn<<3];
 16 
 17 int len[maxn<<3][8],cnt[maxn<<3][8];
 18 void PushUp(int rt, int l, int r)
 19 {
 20     memset(len[rt],0, sizeof(len[rt]));
 21     int color=0;
 22     if(cnt[rt][1]>0)
 23         color+=1;
 24     if(cnt[rt][2]>0)
 25         color+=2;
 26     if(cnt[rt][4]>0)
 27         color+=4;
 28     if(cnt[rt][1] || cnt[rt][2] || cnt[rt][4])
 29     {
 30         len[rt][color]+=X[r]-X[l-1];
 31         for(int i=1; i<8; i++)
 32         {
 33             if(color!=(color|i))
 34             {
 35                 int tmp=len[rt<<1][i]+len[rt<<1|1][i];
 36                 len[rt][color|i]+=tmp;
 37                 len[rt][color]-=tmp;
 38             }
 39         }
 40     }
 41     else if(l!=r)
 42         for(int i=1; i<8; i++)
 43             len[rt][i]=len[rt<<1][i]+len[rt<<1|1][i];
 44 }
 45 
 46 void Update(int L,int R,int c, int l , int r, int rt)
 47 {
 48     if(L<=l&&r<=R)
 49     {
 50         if(c>0)
 51             cnt[rt][c]++;
 52         else
 53             cnt[rt][-c]--;
 54         //cnt[rt] += c;
 55         PushUp(rt, l, r);
 56         return ;
 57     }
 58     int m=(l+r)>>1;
 59     if(L<=m)
 60         Update(L,R,c, lson);
 61     if(m<R)
 62         Update(L,R,c, rson);
 63     PushUp(rt, l, r);
 64 }
 65 int Bin(int key,int n,int X[])
 66 {
 67     int l = 0 , r = n - 1;
 68     while(l <= r)
 69     {
 70         int m = (l + r) >> 1;
 71         if (X[m] == key) return m;
 72         if (X[m] < key) l = m + 1;
 73         else r = m - 1;
 74     }
 75     return -1;
 76 }
 77 void print(LL x)
 78 {
 79     printf(LLD, x);
 80     puts("");
 81 }
 82 int main()
 83 {
 84 #ifndef ONLINE_JUDGE
 85     freopen("in.txt", "r", stdin);
 86     freopen("out.txt", "w", stdout);
 87 #endif
 88     int t,n, ca=1;
 89     char ch;
 90     int a,b,c,d;
 91     scanf("%d",&t);
 92     while(t--)
 93     {
 94         scanf("%d",&n);
 95         int m=0;
 96         while(n--)
 97         {
 98             int e;
 99             getchar();
100             scanf("%c%d%d%d%d",&ch,&a,&b,&c,&d);
101             if(ch=='R')
102                 e=1;
103             else if(ch=='G')
104                 e=2;
105             else
106                 e=4;
107             X[m]=a;
108             ss[m++]=Seg(a,c,b,e);
109             X[m]=c;
110             ss[m++]=Seg(a,c,d,-e);
111         }
112         sort(X,X+m);
113         sort(ss,ss+m);
114         int k=1;
115         for(int i=1; i<m; i++)
116             if(X[i]!=X[i-1])
117                 X[k++]=X[i];
118         LL ans[8];
119         memset(len, 0, sizeof(len));
120         memset(cnt, 0, sizeof(cnt));
121         memset(ans,0, sizeof(ans));
122         for(int i=0; i<m; i++)
123         {
124 //            int l=Bin(ss[i].l, k, X);
125 //            int r=Bin(ss[i].r, k, X)-1;
126             int l=lower_bound(X,X+k,ss[i].l)-X+1;
127             int r=lower_bound(X,X+k,ss[i].r)-X;
128             Update(l,r,ss[i].s, 1, k-1, 1);
129             if(ss[i].h!=ss[i+1].h)
130                 for(int j=1; j<8; j++)
131                     ans[j]+=(LL)len[1][j]*(ss[i+1].h-ss[i].h);
132         }
133         printf("Case %d:
",ca++);
134         print(ans[1]);
135         print(ans[2]);
136         print(ans[4]);
137         print(ans[3]);
138         print(ans[5]);
139         print(ans[6]);
140         print(ans[7]);
141     }
142     return 0;
143 }

View Code

HDU 3255 Farming

题意:给方土地的左上和右下坐标以及可以种的种子编号(1/2/3), 每种种子有不同收入, 输出最大收益

  1 typedef long long LL;
  2 #define lson l, m, rt<<1
  3 #define rson m+1, r, rt<<1|1
  4 #define N 1000005
  5 
  6 int X[60005];
  7 int len[N][8], cnt[N][8];
  8 struct Seg
  9 {
 10     int h, l, r, s;
 11     Seg() {}
 12     Seg(int a, int b, int c, int d) :l(a), r(b), h(c), s(d) {}
 13     bool operator < (const Seg &cmp) const
 14     {
 15         return h<cmp.h;
 16     }
 17 }ss[N<<1];
 18 
 19 void pushup(int rt, int l, int r)
 20 {
 21     memset(len[rt], 0, sizeof(len[0]));
 22     int color=0;
 23     if(cnt[rt][1]>0)
 24         color+=1;
 25     if(cnt[rt][2]>0)
 26         color+=2;
 27     if(cnt[rt][4]>0)
 28         color+=4;
 29     if(cnt[rt][1] || cnt[rt][2] || cnt[rt][4])
 30     {
 31         len[rt][color]+=X[r]-X[l-1];
 32         for(int i=1;i<8;i++)
 33             if(color!=(color|i))
 34             {
 35                 int tmp=len[rt<<1][i]+len[rt<<1|1][i];
 36                 len[rt][color|i]+=tmp;
 37                 len[rt][color]-=tmp;
 38             }
 39     }
 40     else if(l!=r)
 41         for(int i=1;i<8;i++)
 42             len[rt][i]=len[rt<<1][i]+len[rt<<1|1][i];
 43 }
 44 void update(int L, int R, int c, int l, int r, int rt)
 45 {
 46     if(L<=l && r<=R)
 47     {
 48         if(c>0)
 49             cnt[rt][c]++;
 50         else
 51             cnt[rt][-c]--;
 52         pushup(rt, l, r);
 53         return ;
 54     }
 55     int m=(l+r)>>1;
 56     if(L<=m)
 57         update(L, R, c, lson);
 58     if(m<R)
 59        update(L, R, c, rson);
 60     pushup(rt, l, r);
 61 }
 62 int Bin(int key, int n, int X[])
 63 {
 64     int l=0, r=n-1;
 65     while(l<=r)
 66     {
 67         int m=(l+r)>>1;
 68         if(X[m]==key)
 69             return m;
 70         if(X[m]<key)
 71             l=m+1;
 72         else
 73             r=m-1;
 74     }
 75     return -1;
 76 }
 77 void print(LL x)
 78 {
 79     printf(LLD, x);
 80     puts("");
 81 }
 82 int style[5];
 83 int main()
 84 {
 85     int t, ca=1;
 86     scanf("%d", &t);
 87     while(t--)
 88     {
 89         int n, M;
 90         scanf("%d%d", &n, &M);
 91         for(int i=0;i<M;i++)
 92             scanf("%d", &style[i]);
 93         int m=0;
 94         for(int i=0;i<n;i++)
 95         {
 96             int a, b, c, d, e, s;
 97             scanf("%d%d%d%d%d", &a, &b, &c, &d, &s);
 98             if(s==1)
 99                 e=1;
100             else if(s==2)
101                 e=2;
102             else
103                 e=4;
104             X[m]=a;
105             ss[m++]=Seg(a, c, b, e);
106             X[m]=c;
107             ss[m++]=Seg(a, c, d, -e);
108         }
109         sort(X, X+m);
110         sort(ss, ss+m);
111         int k=1;
112         for(int i=1;i<m;i++)
113             if(X[i]!=X[i-1])
114                 X[k++]=X[i];
115         LL ans[8];
116         memset(ans, 0, sizeof(ans));
117         memset(len, 0, sizeof(len));
118         memset(cnt, 0, sizeof(cnt));
119         for(int i=0;i<m;i++)
120         {
121             int l=Bin(ss[i].l, k, X)+1;
122             int r=Bin(ss[i].r, k, X);
123             update(l, r, ss[i].s, 1, k, 1);
124             if(ss[i].h!=ss[i+1].h)
125                 for(int j=1;j<8;j++)
126                     ans[j]+=(LL)len[1][j]*(ss[i+1].h-ss[i].h);
127         }
128         printf("Case %d: ", ca++);
129         if(n==1)
130             print(ans[1]*style[0]);
131         else if(n==2)
132             print(ans[1]*style[0]+ans[2]*style[1]+ans[3]*max(style[0], style[1]));
133         else
134         {
135             ans[1]*=style[0];
136             ans[2]*=style[1];
137             ans[3]*=max(style[0], style[1]);
138             ans[4]*=style[2];
139             ans[5]*=max(style[0], style[2]);
140             ans[6]*=max(style[1], style[2]);
141             ans[7]*=max(max(style[0], style[1]), style[2]);
142             print(ans[1]+ans[2]+ans[4]+ans[3]+ans[5]+ans[6]+ans[7]);
143         }
144     }
145     return 0;
146 }

View Code

HDU 1828 Picture

题意:给n个方块的左下和右上的坐标求周长

求周长, 除了求面积要用到的, 还要记录竖的, 合并重合的

  1 #define lson l, m, rt<<1
  2 #define rson m+1, r, rt<<1|1
  3 #define N 20005
  4 
  5 int cnt[N<<2];
  6 int sum[N<<2];
  7 int numseg[N<<2], len[N<<2];
  8 bool lbd[N<<2], rbd[N<<2];
  9 struct Seg
 10 {
 11     int h, l, r, s;
 12     Seg() {}
 13     Seg(int a, int b, int c, int d) : l(a), r(b), h(c), s(d) {}
 14     bool operator < (const Seg &cmp) const
 15     {
 16         if(h==cmp.h)
 17             return s>cmp.s;
 18         return h<cmp.h;
 19     }
 20 }ss[N];
 21 void pushup(int rt, int l, int r)
 22 {
 23     if(cnt[rt])
 24     {
 25         lbd[rt]=rbd[rt]=1;
 26         len[rt]=r-l+1;
 27         numseg[rt]=2;
 28     }
 29     else if(l==r)
 30         len[rt]=numseg[rt]=lbd[rt]=rbd[rt]=0;
 31     else
 32     {
 33         lbd[rt]=lbd[rt<<1];
 34         rbd[rt]=rbd[rt<<1|1];
 35         len[rt]=len[rt<<1]+len[rt<<1|1];
 36         numseg[rt]=numseg[rt<<1]+numseg[rt<<1|1];
 37         if(lbd[rt<<1|1] && rbd[rt<<1])
 38             numseg[rt]-=2;
 39     }
 40 }
 41 void update(int L, int R, int c, int l, int r, int rt)
 42 {
 43     if(L<=l && r<=R)
 44     {
 45         cnt[rt]+=c;
 46         pushup(rt, l, r);
 47         return ;
 48     }
 49     int m=(l+r)>>1;
 50     if(L<=m)
 51         update(L, R, c, lson);
 52     if(m<R)
 53         update(L, R, c, rson);
 54     pushup(rt, l, r);
 55 }
 56 int Bin(double key, int n, double X[])
 57 {
 58     int l=0, r=n-1;
 59     while(l<=r)
 60     {
 61         int m=(l+r)>>1;
 62         if(X[m]==key)
 63             return m;
 64         if(X[m]<key)
 65             l=m+1;
 66         else
 67             r=m-1;
 68     }
 69     return -1;
 70 }
 71 int main()
 72 {
 73 #ifndef ONLINE_JUDGE
 74     freopen("in.txt", "r", stdin);
 75     freopen("out.txt", "w", stdout);
 76 #endif
 77     int n;
 78     while(~scanf("%d", &n))
 79     {
 80         int m=0;
 81         int minn=INT_MAX, maxn=-INT_MAX;
 82         while(n--)
 83         {
 84             int a, b, c, d;
 85             scanf("%d%d%d%d", &a, &b, &c, &d);
 86             minn=min(minn, a);
 87             maxn=max(maxn, c);
 88             ss[m++]=Seg(a, c, b, 1);
 89             ss[m++]=Seg(a, c, d, -1);
 90         }
 91         sort(ss, ss+m);
 92         int ret=0, last=0;
 93         for(int i=0;i<m;i++)
 94         {
 95             if(ss[i].l<ss[i].r)
 96                 update(ss[i].l, ss[i].r-1, ss[i].s, minn, maxn-1, 1);
 97             ret+=numseg[1]*(ss[i+1].h-ss[i].h);
 98             ret+=abs(len[1]-last);
 99             last=len[1];
100         }
101         printf("%d
", ret);
102     }
103     return 0;
104 }

View Code