线段树总结

寒假到现在这一个月断断续续的做了一些有关线段树的题目，有句话确实说的没错：量的积累必将产生质的变化，可能是先学习了伸展树吧，学习起线段树感觉上手很多。一直ym各路大神，看着比自己牛X几倍的人一直比我努力着，我不甘。虽然现在依然很菜，但是我会加油的。

一、单点更新

1、 hdu1166 地兵布阵

题目大意：有N个工兵营，每个工兵营开始有a个人，然后有一些操作。Add i j 第i个工兵营加j个人 Sub 第i个工兵营减j个人，Q i j 询问第i到第j个工兵营的总人数。

解题思路：O(-1)

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 
 5 #define lz 2*u,l,mid
 6 #define rz 2*u+1,mid+1,r
 7 const int maxn=55555;
 8 int sum[2*maxn], a[maxn];
 9 
10 void build(int u, int l, int r)
11 {
12     sum[u]=0;
13     if(l==r)
14     {
15         sum[u]=a[l];
16         return ;
17     }
18     int mid=(l+r)>>1;
19     build(lz);
20     build(rz);
21     sum[u]=sum[2*u]+sum[2*u+1];
22 }
23 
24 void Update(int u, int l, int r, int pos, int c)
25 {
26     if(l==r)
27     {
28         sum[u]+=c;
29         return ;
30     }
31     int mid=(l+r)>>1;
32     if(pos<=mid) Update(lz,pos,c);
33     else Update(rz,pos,c);
34     sum[u]=sum[2*u]+sum[2*u+1];
35 }
36 
37 int Query(int u, int l, int r, int tl, int tr)
38 {
39     if(tl<=l&&r<=tr) return sum[u];
40     int mid=(l+r)>>1;
41     if(tr<=mid) return Query(lz,tl,tr);
42     else if(tl>mid) return Query(rz,tl,tr);
43     else
44     {
45         int t1=Query(lz,tl,mid);
46         int t2=Query(rz,mid+1,tr);
47         return t1+t2;
48     }
49 }
50 
51 int main()
52 {
53     int n, T, tcase=0;
54     cin >> T;
55     while(T--)
56     {
57         printf("Case %d:\n",++tcase);
58         cin >> n;
59         for(int i=1; i<=n; i++)
60             scanf("%d",a+i);
61         build(1,1,n);
62         char op[10];;
63         while(scanf("%s",op))
64         {
65             if(op[0]=='E') break;
66             else
67             {
68                 int l, r;
69                 scanf("%d%d",&l,&r);
70                 if(op[0]=='Q') printf("%d\n",Query(1,1,n,l,r));
71                 else
72                 {
73                     if(op[0]=='S') r*=-1;
74                     Update(1,1,n,l,r);
75                 }
76             }
77         }
78     }
79     return 0;
80 }

2、hdu2795 billbord

题目大意：有一块板子，长宽分别为W，H，然后有n块1*w海报，让你把这n快海报贴在这块板子上，尽量板子的上方贴，同一行尽量往板子的左边贴。对于第i块海报如果能够贴下则输出能贴在第几行，否则输出-1。

解题思路：设线段树的操作长度为H，则对应的叶子节点的最大值为W。设每次找到符合要求的位置（板子最上最左，对应线段树中最下最左）减去相应的w值。

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 
 5 #define lz 2*u,l,mid
 6 #define rz 2*u+1,mid+1,r
 7 const int maxn=200005;
 8 int tree[4*maxn];
 9 int t_max[4*maxn];
10 int n, m, max_w, nn;
11 
12 void build(int u, int l, int r)
13 {
14     tree[u]=max_w;
15     if(l==r)
16     {
17         return ;
18     }
19     int mid=(l+r)>>1;
20     build(lz);
21     build(rz);
22 }
23 
24 void Update(int u, int l, int r, int id, int w)
25 {
26     if(l==id&&id==r)
27     {
28         tree[u]-=w;
29         return ;
30     }
31     int mid=(l+r)>>1;
32     if(id<=mid)
33         Update(lz,id,w);
34     else Update(rz,id,w);
35     tree[u]=max(tree[2*u],tree[2*u+1]);  ///向上更新最大子区间段
36 
37 }
38 
39 int Query(int u, int l, int r, int w)
40 {
41     if(tree[u]<w) return -1;  ///只需要判断此区间最大空余w是否大于w即可，节省好多时间
42     if(l==r)
43     {
44         return l;
45     }
46     int mid=(l+r)>>1;
47     if(tree[2*u]>=w)
48         return  Query(lz,w);
49     else
50         return  Query(rz,w);
51 }
52 
53 int main()
54 {
55     while(cin >> n >> max_w >> m)
56     {
57         nn=min(n,m);
58         build(1,1,nn);
59         while(m--)
60         {
61             int w;
62             scanf("%d",&w);
63             int id=Query(1,1,nn,w);
64             if(id==-1) puts("-1");
65             else
66             {
67                 printf("%d\n",id);
68                 Update(1,1,nn,id,w);
69             }
70         }
71     }
72 }

3、hdu1754 I hate it

题目大意：给你N个数，M个操作，操作分两类。(1)"Q A B“，查询区间[A,B]内的最大值。(2)"U A B"，将第A个数的值改成B。

解题思路：O(-1)

View Code

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 #define lz l , m , rt << 1
 6 #define rz m + 1 , r , rt << 1 | 1
 7 const int maxn = 222222;
 8 int maxx[maxn<<2];
 9 
10 void push_up(int rt)
11 {
12     maxx[rt] = max(maxx[rt<<1] , maxx[rt<<1|1]);
13 }
14 void build(int l,int r,int rt)
15 {
16     if (l == r)
17     {
18         scanf("%d",&maxx[rt]);
19         return ;
20     }
21     int m = (l + r) >> 1;
22     build(lz);
23     build(rz);
24     push_up(rt);
25 }
26 void update(int p,int sc,int l,int r,int rt)
27 {
28     if (l == r)
29     {
30         maxx[rt] = sc;
31         return ;
32     }
33     int m = (l + r) >> 1;
34     if (p <= m) update(p , sc , lz);
35     else update(p , sc , rz);
36     push_up(rt);
37 }
38 int query(int L,int R,int l,int r,int rt)
39 {
40     if (L <= l && r <= R)
41     {
42         return maxx[rt];
43     }
44     int m = (l + r) >> 1;
45     int ret = 0;
46     if (L <= m) ret = max(ret , query(L , R , lz));
47     if (R > m) ret = max(ret , query(L , R , rz));
48     return ret;
49 }
50 int main()
51 {
52     int n , m;
53     while (~scanf("%d%d",&n,&m))
54     {
55         build(1 , n , 1);
56         while (m --)
57         {
58             char op[2];
59             int a , b;
60             scanf("%s%d%d",op,&a,&b);
61             if (op[0] == 'Q') printf("%d\n",query(a , b , 1 , n , 1));
62             else update(a , b , 1 , n , 1);
63         }
64     }
65     return 0;
66 }

4、poj2828 Buy Tickets

题目大意：有n个人排队买票对应n个操作，每个操作有两个值 pos val ，代表第i个人会插到第pos个人后面，他手上票的值为val。n个操作完后让你输出n个人排成一队的总状态。

解题思路：题目转了一个弯，不是让你直接求第几位的值是多少。但是其实道理是一样的，从后往前开始排，每个人在他自己前面留pos个空位置，有人的位置不算，因为我们是倒着来的，后面的人肯定会把自己给挤掉的。

View Code

 1 #include <cstdio>
 2 #include <iostream>
 3 using namespace std;
 4 
 5 #define lz 2*u,l,mid
 6 #define rz 2*u+1,mid+1,r
 7 const int maxn = 222222;
 8 int tree[4*maxn];
 9 int sum[4*maxn];
10 int a[maxn], b[maxn];
11 int n, cnt;
12 
13 void build(int u, int l, int r)
14 {
15     if(l==r)
16     {
17         sum[u]=1;
18         return ;
19     }
20     int mid=(l+r)>>1;
21     build(lz);
22     build(rz);
23     sum[u]=sum[2*u]+sum[2*u+1];
24 }
25 
26 void Update(int u, int l, int r, int pos, int val)
27 {
28     if(l==r)
29     {
30         tree[l]=val;
31         sum[u]=0;
32         return ;
33     }
34     int mid=(l+r)>>1;
35     if(sum[2*u]>=pos)    ///只需判断前面有多少个空格
36           Update(lz,pos,val);
37     else
38     {
39         pos-=sum[2*u];
40         Update(rz,pos,val);
41     }
42     sum[u]=sum[2*u]+sum[2*u+1];
43 }
44 
45 int main()
46 {
47     while(cin >> n)
48     {
49         for(int i=0; i<n; i++)
50             scanf("%d%d",a+i,b+i);
51         build(1,1,n);
52         for(int i=n-1; i>=0; i--)  ///从后往前
53             Update(1,1,n,a[i]+1,b[i]);
54         printf("%d",tree[1]);
55         for(int i=2; i<=n; i++)
56             printf(" %d",tree[i]);
57         puts("");
58     }
59     return 0;
60 }

5、poj2886 Who Gets the Most Candies?

题目大意：n个小孩围成一圈，他们被顺时针编号为 1 到 n。每个小孩手中有一个数字非0的卡片，游戏从第 K 个小孩开始，他告诉其他小孩他卡片上的数字并离开这个圈，他卡片上的数字 A 表明了下一个离开的小孩，A大于0表示顺时针小于0表示逆时针。游戏将直到所有小孩都离开，在游戏中，第 p 个离开的小孩将得到 F(p) 个糖果，F(p) 是 p 的约数的个数，问谁将得到最多的糖果，输出最幸运的小孩的名字和他可以得到的糖果的数量。

解题思路：因为题目只要求得到出幸运的孩子是谁并且他得到的糖果的数量，所以我们不必将前n的数都处理完，只需先建立反素数表（1-n中含素数最多的数），每次更新到n之前那个最大的反素数即可。

View Code

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 #define lz 2*u,l,mid
 8 #define rz 2*u+1,mid+1,r
 9 const int maxn = 500005;
10 int tree[4*maxn];
11 int pos;
12 
13 const int antiprime[]={1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,
14 332640,498960,554400,665280};
15 /// 反素数表, 反素数指1-n中含有素因子数最多的数
16 
17 const int factorNum[]={1,2,3,4,6,8,9,10,12,16,18,20,24,30,32,36,40,48,60,64,72,80,84,
18 90,96,100,108,120,128,144,160,168,180,192,200,216,224};
19 /// 反素数对应的约数个数
20 
21 struct node
22 {
23     char name[15];
24     int val;
25 }f[maxn];
26 
27 void build(int u, int l, int r)
28 {
29     tree[u]=r-l+1;
30     if(l==r) return ;
31     int mid=(l+r)>>1;
32     build(lz);
33     build(rz);
34 }
35 
36 void Update(int u, int l, int r, int pp)
37 {
38      tree[u]--;
39      if(l==r)
40      {
41          pos=l;
42          return ;
43      }
44      int mid=(l+r)>>1;
45      if(tree[2*u]>=pp) Update(lz,pp);
46      else
47          Update(rz,pp-tree[2*u]);
48 }
49 
50 int main()
51 {
52     int n, k, &mod=tree[1];  ///mod随tree[1]变，赋的是地址
53     while(cin >> n >> k)
54     {
55         for(int i=1; i<=n; i++)
56             scanf("%s%d",&f[i].name,&f[i].val);
57         int cnt=0;
58         while(cnt<35&&antiprime[cnt]<=n) cnt++;
59         cnt--;
60         pos=0;
61         f[pos].val=0;
62         build(1,1,n);
63         for(int i=0; i<antiprime[cnt]; i++)
64         {
65             if(f[pos].val>0)  k=((k+f[pos].val-2)%mod+mod)%mod+1;
66             else  k=((k+f[pos].val-1)%mod+mod)%mod+1;
67             Update(1,1,n,k);
68         }
69         printf("%s %d\n",f[pos].name,factorNum[cnt]);
70     }
71     return 0;
72 }

二、成段更新

说实话，当初我学这里的时候确实纠结了良久，有点抽象，没事走在路上多想想就好了。成段更新需要用到延迟标记（或者说懒惰标记），简单的说就是每次更新的时候不要更新到底，用延迟标记使得更新延迟到下次需要更新或者询问到的时候再传递下去。延迟标记的意思是：这个区间的左右儿子都需要被更新，但是当前区间已经更新了。

1、hdu 1698 Just a Hook

题目大意：给你n个数（初始时每个数的值为1），m个操作，每个操作把区间[l,r]里的数更新为c，问最后这n个数的和是多少。

解题思路：O(-1)

View Code

 1 #include <cstdio>
 2 #include <iostream>
 3 using namespace std;
 4 
 5 const int maxn=100005;
 6 int tree[4*maxn];
 7 int flag[4*maxn];
 8 
 9 void down(int u, int l, int r)
10 {
11     if(flag[u])
12     {
13         int mid=(l+r)>>1;
14         tree[2*u]=(mid-l+1)*flag[u];
15         tree[2*u+1]=(r-mid)*flag[u];
16         flag[2*u]=flag[u];
17         flag[2*u+1]=flag[u];
18         flag[u]=0;
19     }
20 }
21 
22 void build(int u, int l, int r)
23 {
24     flag[u]=0;
25     if(l==r)
26     {
27         tree[u]=1;
28         return ;
29     }
30     int mid=(l+r)>>1;
31     build(u*2,l,mid);
32     build(u*2+1,mid+1,r);
33     tree[u]=tree[2*u]+tree[2*u+1];
34 }
35 
36 void update(int u, int l, int r, int tl, int tr, int val)
37 {
38     if(tl<=l&&r<=tr)
39     {
40         tree[u]=(r-l+1)*val;
41         flag[u]=val;
42         return ;
43     }
44     down(u,l,r);
45     int mid=(l+r)>>1;
46     if(tr<=mid)  update(2*u,l,mid,tl,tr,val);
47     else if(tl>mid) update(2*u+1,mid+1,r,tl,tr,val);
48     else
49     {
50         update(2*u,l,mid,tl,tr,val);
51         update(2*u+1,mid+1,r,tl,tr,val);
52     }
53     tree[u]=tree[2*u]+tree[2*u+1];
54 
55 }
56 
57 int getsum(int u, int l, int r, int tl, int tr)
58 {
59     if(tl<=l&&r<=tr)
60     {
61         return tree[u];
62     }
63     down(u,l,r);
64     int mid=(l+r)>>1;
65     if(tr<=mid) return getsum(2*u,l,mid,tl,tr);
66     else if(tl>mid) return getsum(2*u+1,mid+1,r,tl,tr);
67     else
68     {
69         int t1=getsum(2*u,l,mid,tl,tr);
70         int t2=getsum(2*u+1,mid+1,r,tl,tr);
71         return t1+t2;
72     }
73 }
74 
75 int main()
76 {
77     int  T, n, Q, tcase=0;
78     cin >> T;
79     while(T--)
80     {
81         cin >> n>> Q;
82         build(1,1,n);
83         while(Q--)
84         {
85             int l, r, val;
86             scanf("%d%d%d",&l,&r,&val);
87             update(1,1,n,l,r,val);
88         }
89         int ans=getsum(1,1,n,1,n);
90         printf("Case %d: The total value of the hook is %d.\n",++tcase,ans);
91     }
92     return 0;
93 }

2、poj3468 A Simple Problem with Integers

题目大意：给你n个附有起始值的数，然后m次询问。C a b val ：表示区间[a，b]的数都加上一个val值，Q a b ：询问区间[a，b]的综合。

解题思路：O(-1)

View Code

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 using namespace std;
  5 
  6 #define lz 2*u,l,mid
  7 #define rz 2*u+1,mid+1,r
  8 const int maxn=100005;
  9 __int64 a[maxn];     ///还要注意范围
 10 __int64 tree[4*maxn];
 11 __int64 flag[4*maxn];
 12 
 13 void push_up(int u)
 14 {
 15     tree[u]=tree[2*u]+tree[2*u+1];
 16 }
 17 
 18 void push_down(int u, int l, int r)
 19 {
 20     if(flag[u])
 21     {
 22         int mid=(l+r)>>1;
 23         flag[2*u]+=flag[u];  ///!!!
 24         flag[2*u+1]+=flag[u];  ///!!!
 25         tree[2*u]+=flag[u]*(mid-l+1);
 26         tree[2*u+1]+=flag[u]*(r-mid);
 27         flag[u]=0;
 28     }
 29 }
 30 
 31 void build(int u, int l, int r)
 32 {
 33     flag[u]=0;
 34     if(l==r)
 35     {
 36         tree[u]=a[l];
 37         return ;
 38     }
 39     int mid=(l+r)>>1;
 40     build(lz);
 41     build(rz);
 42     push_up(u);
 43 }
 44 
 45 void Update(int u, int l, int r, int tl, int tr, __int64 val)
 46 {
 47     if(tl<=l&&r<=tr)
 48     {
 49         tree[u]+=val*(r-l+1);
 50         flag[u]+=val;  ///!!!加上一个值 并非重新赋新值
 51         return ;
 52     }
 53     push_down(u,l,r);
 54     int mid=(l+r)>>1;
 55     if(tr<=mid)
 56         Update(lz,tl,tr,val);
 57     else if(tl>mid)
 58          Update(rz,tl,tr,val);
 59     else
 60     {
 61         Update(lz,tl,mid,val);
 62         Update(rz,mid+1,tr,val);
 63     }
 64     push_up(u);
 65 }
 66 
 67 __int64 Query(int u, int l, int r, int tl, int tr)
 68 {
 69     if(tl<=l&&r<=tr)
 70     {
 71         return tree[u];
 72     }
 73     push_down(u,l,r);
 74     int mid=(l+r)>>1;
 75     if(tr<=mid)
 76         return Query(lz,tl,tr);
 77     else if(tl>mid)
 78          return Query(rz,tl,tr);
 79     else
 80     {
 81         __int64 t1=Query(lz,tl,mid);
 82         __int64 t2=Query(rz,mid+1,tr);
 83         return t1+t2;
 84     }
 85     push_up(u);
 86 }
 87 
 88 int main()
 89 {
 90     int n, m, l, r;
 91     while(cin >> n >> m)
 92     {
 93         for(int i=1; i<=n; i++)
 94             scanf("%I64d",a+i);
 95         build(1,1,n);
 96         while(m--)
 97         {
 98             char ch[5];
 99             __int64 val;
100             scanf("%s",ch);
101             if(ch[0]=='C')
102             {
103                 scanf("%d%d%I64d",&l,&r,&val);
104                 Update(1,1,n,l,r,val);
105             }
106             else
107             {
108                 scanf("%d%d",&l,&r);
109                 printf("%I64d\n",Query(1,1,n,l,r));
110             }
111         }
112     }
113     return 0;
114 }

3、poj 2528 Mayor’s posters

题目大意：首先给出一个n，然后按顺序在墙上贴n张海报，海报可以相互覆盖，后面贴的海报可以覆盖前面贴的海报，问你最后能看见几张不同的海报。

解题思路：操作区间比较大，这里我们需要进行离散化，说实话离散化确实比较简单，但是对于这题就有学问了。

先说说离散化：给你区间[1，10],[10，20],[20，100],[1000，10000000], 这里我们[2，9]，[11,19],[21，99],[101，999],[1000000，+oo]这些区间我们其实都用不上，而且线段树开这么大空间肯定是超内存的。所以我们取每个区间不重复的端点值进行映射，1,10,11,20,100,1000,100000分别映射到1,2,3,4,5,6,7上面去。

但是上面普通的离散化藐视对这题没有用（这题数据有些弱，所以看不出来，说实话我也是过了之后去傻崽空间打酱油看到的），下面的话引自傻崽的原创。

给出下面两个简单的例子应该能体现普通离散化的缺陷:
例子一:1-10 1-4 5-10
例子二:1-10 1-4 6-10
普通离散化后都变成了[1,4][1,2][3,4]
线段2覆盖了[1,2],线段3覆盖了[3,4],那么线段1是否被完全覆盖掉了呢?
例子一是完全被覆盖掉了,而例子二没有被覆盖。 (这里就是我说的学问所在)

为了解决这种缺陷,我们可以在排序后的数组上加些处理,比如说[1,2,6,10]
如果相邻数字间距大于1的话,在其中加上任意一个数字,比如加成[1,2,3,6,7,10],然后再做线段树就好了.

View Code

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <map>
  5 #include <cmath>
  6 #include <algorithm>
  7 using namespace std;
  8 
  9 #define lz 2*u,l,mid
 10 #define rz 2*u+1,mid+1,r
 11 const int maxn=20005;
 12 int flag[4*maxn];
 13 int A[maxn], B[2*maxn];
 14 int visit[2*maxn];
 15 int ans=0;
 16 
 17 struct node
 18 {
 19     int l, r;
 20 }f[maxn];
 21 
 22 void build(int u, int l, int r)
 23 {
 24     flag[u]=0;
 25     if(l==r)  return ;
 26     int mid=(l+r)>>1;
 27     build(2*u,l,mid);
 28     build(2*u+1,mid+1,r);
 29 }
 30 
 31 void Update(int u, int l, int r, int tl, int tr, int c)
 32 {
 33     if(flag[u]) return ;  ///此段已经贴满了海报，不必再查询下去了
 34     if(tl<=l&&r<=tr)
 35     {
 36         flag[u]=1;  ///标记
 37         if(!visit[c])
 38         {
 39             ans++;
 40             visit[c]=1;
 41         }
 42         return ;
 43     }
 44     int mid=(l+r)>>1;
 45     if(tr<=mid) Update(lz,tl,tr,c);
 46     else if(tl>mid) Update(rz,tl,tr,c);
 47     else
 48     {
 49         Update(lz,tl,mid,c);
 50         Update(rz,mid+1,tr,c);
 51     }
 52     if(flag[2*u]&&flag[2*u+1]) flag[u]=1; ///!!标记上传
 53 }
 54 
 55 int getid(int x, int n)
 56 {
 57     int l=1, r=n, mid;
 58     while(l<=r)
 59     {
 60         mid=(l+r)>>1;
 61         if(B[mid]==x) return mid;
 62         else if(B[mid]<x) l=mid+1;
 63         else r=mid-1;
 64     }
 65 }
 66 
 67 int main()
 68 {
 69     int T, n;
 70     cin >> T;
 71     while(T--)
 72     {
 73         cin >> n;
 74         memset(visit,0,sizeof(visit));
 75         int num=0;
 76         for(int i=0; i<n; i++)
 77         {
 78             scanf("%d%d",&f[i].l,&f[i].r);
 79             A[++num]=f[i].l;
 80             A[++num]=f[i].r;
 81         }
 82         sort(A+1,A+num+1);
 83         int ep=1;
 84         B[1]=A[1];
 85         for(int i=2; i<=num; i++)  ///离散化
 86             if(B[ep]!=A[i]) B[++ep]=A[i];
 87         for(int i=ep; i>1; i--)
 88             if(B[i]!=B[i-1]+1) B[++ep]=B[i-1]+1;
 89         sort(B+1,B+ep+1);
 90         build(1,1,ep);
 91         ans=0;
 92         for(int i=n-1; i>=0; i--)
 93         {
 94             int l=getid(f[i].l,ep);
 95             int r=getid(f[i].r,ep);
 96             Update(1,1,ep,l,r,i+1);
 97         }
 98         printf("%d\n",ans);
 99     }
100     return 0;
101 }

4、poj3277 City Horizon

题目大意：平面上有[1,40000]个建筑，每个建筑有一个区间[Ai,Bi]表示它的跨度，Hi表示其高度。要求这n个建筑的平面覆盖面积。

解题思路：和上一题差不多，只是多了一个求面积操作，数据范围过大，同理也要用到离散化。

View Code

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <algorithm>
  5 using namespace std;
  6 
  7 #define lz 2*u,l,mid
  8 #define rz 2*u+1,mid+1,r
  9 const int maxn = 100005;
 10 typedef long long lld;
 11 lld  flag[4*maxn];
 12 lld A[maxn], B[maxn];
 13 lld sum;
 14 
 15 struct node
 16 {
 17     lld l, w, h;
 18 }f[maxn];
 19 
 20 bool cmp(node A, node B)
 21 {
 22     return A.h<B.h;
 23 }
 24 
 25 lld find(lld x, lld n)
 26 {
 27     lld l=1, r=n, mid;
 28     while(l<=r)
 29     {
 30         mid=(l+r)>>1;
 31         if(B[mid]==x) return mid;
 32         else if(B[mid]<x) l=mid+1;
 33         else r=mid-1;
 34     }
 35 }
 36 
 37 void push_down(int u)
 38 {
 39     if(flag[u])
 40     {
 41         flag[2*u]=flag[2*u+1]=flag[u];
 42         flag[u]=0;
 43     }
 44 }
 45 
 46 void build(int u, int l, int r)
 47 {
 48     flag[u]=0;
 49     if(l==r)
 50         return ;
 51     int mid=(l+r)>>1;
 52     build(lz);
 53     build(rz);
 54 }
 55 
 56 void Update(int u, int l, int r, int tl, int tr, lld c)
 57 {
 58     if(tl<=l&&r<=tr)
 59     {
 60         flag[u]=c;
 61         return ;
 62     }
 63     push_down(u);
 64     int mid=(l+r)>>1;
 65     if(tr<=mid) Update(lz,tl,tr,c);
 66     else if(tl>mid) Update(rz,tl,tr,c);
 67     else
 68     {
 69         Update(lz,tl,mid,c);
 70         Update(rz,mid+1,tr,c);
 71     }
 72 }
 73 
 74 void Query(int u, int l, int r)
 75 {
 76     if(l==r)
 77     {
 78         sum+=flag[u]*(B[l+1]-B[l]);
 79         return ;
 80     }
 81     push_down(u);
 82     int mid=(l+r)>>1;
 83     Query(lz);
 84     Query(rz);
 85 }
 86 
 87 int main()
 88 {
 89     int n;
 90     while(cin >> n)
 91     {
 92         int num=0;
 93         for(int i=1; i<=n; i++)
 94         {
 95             scanf("%d%d%d",&f[i].l,&f[i].w,&f[i].h);
 96             A[++num]=f[i].l;
 97             A[++num]=f[i].w;
 98         }
 99         sort(A+1,A+num+1);
100         sort(f+1,f+n+1,cmp);
101         int ep=1;
102         B[1]=A[1];
103         for(int i=2; i<=num; i++)
104             if(A[i]!=B[ep]) B[++ep]=A[i];
105         build(1,1,ep);
106         for(int i=1; i<=n; i++)
107         {
108             int l=find(f[i].l,ep);
109             int r=find(f[i].w,ep);
110             Update(1,1,ep,l,r-1,f[i].h);
111         }
112         sum=0;
113         Query(1,1,ep);
114         cout << sum <<endl;
115     }
116     return 0;
117 }

5、poj3255 Help with Intervals

题目大意：集合的基本操作，具体地说就是并、交、相对补和对称差。五种操作 ‘U’、‘I’、‘D’、‘C’和‘S’中的一个加上一个区间（T），形式为(a,b)、(a,b]、[a,b)和[a,b]。

解题思路： U:把区间[l,r]覆盖成1； I：把区间把[-∞,l)(r,∞]覆盖成0； D：把区间[l,r]覆盖成0。

C：把区间[-∞,l)(r,∞]，再对[l，r]区间0/1异或一次。 S：区间[l，r]内0/1异或一次。

这里要注意的一点就是先覆盖再异或 and 先异或再覆盖的区别了，两者是不同的。

View Code

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #define lz l,m,rt<<1
 5 #define rz m+1,r,rt<<1|1
 6 using namespace std;
 7 
 8 const int mm=133333;
 9 int col[mm<<2],turn[mm<<2],cov[mm+5];
10 
11 void T(int rt)
12 {
13     if(col[rt])col[rt]^=3;
14     else turn[rt]^=1;
15 }
16 void pushdown(int rt)
17 {
18     if(col[rt])
19     {
20         col[rt<<1]=col[rt<<1|1]=col[rt];
21         col[rt]=turn[rt<<1]=turn[rt<<1|1]=0;
22     }
23     if(turn[rt])
24     {
25         T(rt<<1);
26         T(rt<<1|1);
27         turn[rt]=0;
28     }
29 }
30 void updata(int L,int R,int op,int l,int r,int rt)
31 {
32     if(L<=l&&R>=r)
33     {
34         if(op)col[rt]=op,turn[rt]=0;
35         else T(rt);
36         return;
37     }
38     pushdown(rt);
39     int m=(l+r)>>1;
40     if(L<=m)updata(L,R,op,lz);
41     if(R>m)updata(L,R,op,rz);
42 }
43 void query(int l,int r,int rt)
44 {
45     if(col[rt])
46     {
47         if(col[rt]<2)
48             for(int i=l; i<=r; ++i)cov[i]=1;
49         return;
50     }
51     if(l==r)return;
52     pushdown(rt);
53     int m=(l+r)>>1;
54     query(lz);
55     query(rz);
56 }
57 int main()
58 {
59     char op,l,r;
60     int i,a,b,flag;
61     updata(0,mm,2,0,mm,1);
62     while(~scanf("%c %c%d,%d%c\n",&op,&l,&a,&b,&r))
63     {
64         a=(a<<1)+(l=='(');
65         b=(b<<1)-(r==')');
66         if(a>b)
67         {
68             if(op=='I'||op=='C')updata(0,mm,2,0,mm,1);
69         }
70         else
71         {
72             if(op=='U')updata(a,b,1,0,mm,1);
73             if(op=='I'||op=='C')
74             {
75                 if(a>0)updata(0,a-1,2,0,mm,1);
76                 if(b<mm)updata(b+1,mm,2,0,mm,1);
77             }
78             if(op=='D')updata(a,b,2,0,mm,1);
79             if(op=='C'||op=='S')updata(a,b,0,0,mm,1);
80         }
81     }
82     memset(cov,0,sizeof(cov));
83     query(0,mm,1);
84     for(a=b=-1,flag=i=0; i<=mm; ++i)
85         if(cov[i])b=i,a=a<0?i:a;
86         else if(a>=0)
87         {
88             if(flag)printf(" ");
89             flag=1;
90             printf("%c%d,%d%c",a&1?'(':'[',a>>1,(b+1)>>1,b&1?')':']');
91             a=b=-1;
92         }
93     if(!flag)printf("empty set");
94     puts("");
95     return 0;
96 }

三、区间合并

这样的问题一般都是问你区间中满足条件最长的序列，你关键需要知道怎样操作对线段树左右儿子进行合并。

这样的问题一般都要定义三个数组lm（定义从区间左边第一个点开始的满足条件的序列）， rm（定义以区间右边最后一个点结束的满足条件的序列）， sm（定义整个区间满足条件的最长序列）。

1、hdu3308 LCIS

题目大意：给你n个整数，有两种操作，（1）"U A B",表示把第A个数变成B，"Q A B"，表示查询区间[A,B]的最长连续上升序列。

解题思路：O（-1）

View Code

  1 #include <cstdio>
  2 #include <cmath>
  3 #include <iostream>
  4 #include <algorithm>
  5 using namespace std;
  6 
  7 #define lz 2*u,l,mid
  8 #define rz 2*u+1,mid+1,r
  9 const int maxn=100005;
 10 int a[maxn];
 11 
 12 struct node
 13 {
 14     int lm;  ///定义从左边第一个点开始的LCIS
 15     int rm;  ///定义以右边最后一个点结束的LCIS
 16     int sm;  ///定义整段最大的LCIS
 17 }tree[4*maxn];
 18 
 19 void push_up(int u, int l, int r)
 20 {
 21     tree[u].lm=tree[2*u].lm;
 22     tree[u].rm=tree[2*u+1].rm;
 23     tree[u].sm=max(tree[2*u].sm,tree[2*u+1].sm);
 24     int mid=(l+r)>>1;
 25     if(a[mid]<a[mid+1])
 26     {
 27         if(tree[2*u].lm==mid-l+1) tree[u].lm=tree[2*u].lm+tree[2*u+1].lm;
 28         if(tree[2*u+1].rm==r-mid)  tree[u].rm=tree[2*u].rm+tree[2*u+1].rm;
 29         int t=tree[2*u].rm+tree[2*u+1].lm;
 30         if(t>tree[u].sm)  tree[u].sm=t;
 31     }
 32 }
 33 
 34 void build(int u, int l, int r)
 35 {
 36     if(l==r)
 37     {
 38         tree[u].lm=tree[u].rm=tree[u].sm=1;
 39         return ;
 40     }
 41     int mid=(l+r)>>1;
 42     build(lz);
 43     build(rz);
 44     push_up(u,l,r);
 45 }
 46 
 47 void Update(int u, int l, int r, int p, int d)
 48 {
 49     if(l==r)
 50     {
 51         a[l]=d;  return ;
 52     }
 53     int mid=(l+r)>>1;
 54     if(p<=mid)  Update(lz,p,d);
 55     else    Update(rz,p,d);
 56     push_up(u,l,r);
 57 }
 58 
 59 int Query(int u, int l, int r, int tl, int tr)
 60 {
 61     if(tl<=l&&r<=tr)
 62     {
 63         return tree[u].sm;
 64     }
 65     int mid=(l+r)>>1;
 66     if(tr<=mid)  return Query(lz,tl,tr);
 67     else if(tl>mid) return Query(rz,tl,tr);
 68     else
 69     {
 70         int t1=Query(lz,tl,mid);
 71         int t2=Query(rz,mid+1,tr);
 72         int t=max(t1,t2);
 73         if(a[mid]<a[mid+1])
 74         {
 75             t1=min(tree[2*u].rm,mid-tl+1);  ///!!!
 76             t2=min(tree[2*u+1].lm,tr-mid);  ///!!!
 77             t1+=t2;
 78         }
 79         return max(t,t1);
 80     }
 81 }
 82 
 83 int main()
 84 {
 85     int n, m, tcase;
 86     cin >> tcase;
 87     while(tcase--)
 88     {
 89         cin >> n >> m;
 90         for(int i=1; i<=n; i++)
 91             scanf("%d",a+i);
 92         build(1,1,n);
 93         while(m--)
 94         {
 95             char ch[5];
 96             int l, r;
 97             scanf("%s%d%d",ch,&l,&r);
 98             if(ch[0]=='U')
 99             {
100                 l++;
101                 Update(1,1,n,l,r);
102             }
103             else
104             {
105                 l++, r++;
106                 int ans=Query(1,1,n,l,r);
107                 printf("%d\n",ans);
108             }
109         }
110     }
111     return 0;
112 }

2、poj3667 Hotel （此题代码有详细注释，作为初学者可以参考代码理解）

题目大意：让你对一个区间进行操作。输入Q C 或者 Q C D。

Q ==1 输入 C：表示让你求1-n中是否有连续的C个空hotel，如果有多个连续的C个空hotel，则取最左边的，并输出最左边的第一间hotel标号。让人住进去，那么这些空房就不能住人了。如果不存在连续的C个hotel，则输出 0。

Q==2 输入 C D：表示从标号C到C+D-1的hotel的房间全部要退房，那么这么hotel都变成空。

解题思路：记录整段区间最长的空房间。

View Code

  1 #include <cstdio>
  2  #include <cmath>
  3  #include <iostream>
  4  #include <algorithm>
  5  using namespace std;
  6  
  7  #define lz 2*u,l,mid
  8  #define rz 2*u+1,mid+1,r
  9  const int maxn=50005;
 10  int  flag[4*maxn];   ///标记
 11  
 12  struct node
 13  {
 14      int lm; ///从左边第一个点开始最长的连续空hotel
 15      int rm; ///以右边最后一个结束的最长的连续空hotel
 16      int sm; ///整段区间最大的连续空hotel 
 17  } tree[4*maxn];
 18  
 19  void push_up(int u, int l, int r)   ///向上更新
 20  {
 21      tree[u].lm=tree[2*u].lm;          
 22      tree[u].rm=tree[2*u+1].rm;
 23      tree[u].sm=max(tree[2*u].sm,tree[2*u+1].sm);
 24      int mid=(l+r)>>1;
 25      if(tree[2*u].lm==mid-l+1) tree[u].lm+=tree[2*u+1].lm;  ///!!这里注意，当左孩子左边连续的达到整个区间时，要加上右孩子的左边区间
 26      if(tree[2*u+1].rm==r-mid) tree[u].rm+=tree[2*u].rm;   ///!!考虑右区间，同上
 27      int t=tree[2*u].rm+tree[2*u+1].lm;
 28      if(t>tree[u].sm) tree[u].sm=t;
 29  }
 30  
 31  void push_down(int u, int l, int r)  ///向下更新
 32  {
 33      if(flag[u]==-1) return ;
 34      if(flag[u])
 35      {
 36          flag[2*u]=flag[2*u+1]=flag[u];
 37          tree[2*u].lm=tree[2*u].rm=tree[2*u].sm=0;
 38          tree[2*u+1].lm=tree[2*u+1].rm=tree[2*u+1].sm=0;
 39          flag[u]=-1;
 40      }
 41      else
 42      {
 43          flag[2*u]=flag[2*u+1]=flag[u];
 44          int mid=(l+r)>>1;
 45          tree[2*u].lm=tree[2*u].rm=tree[2*u].sm=mid-l+1;
 46          tree[2*u+1].lm=tree[2*u+1].rm=tree[2*u+1].sm=r-mid;
 47          flag[u]=-1;
 48      }
 49  }
 50  
 51  void build(int u, int l, int r)  ///建树
 52  {
 53      flag[u]=-1;
 54      if(l==r)
 55      {
 56          tree[u].lm=tree[u].rm=tree[u].sm=1;
 57          return ;
 58      }
 59      int mid=(l+r)>>1;
 60      build(lz);
 61      build(rz);
 62      push_up(u,l,r);
 63  }
 64  
 65  void Update(int u, int l, int r, int tl, int tr, int c)   ///更新操作
 66  {
 67      if(tl<=l&&r<=tr)
 68      {
 69          tree[u].sm=tree[u].lm=tree[u].rm=(c==1?0:r-l+1);
 70          flag[u]= c;  
 71          return ;
 72      }
 73      push_down(u,l,r);   ///再次遇见此段区间时，延迟标记同步向下更新
 74      int mid=(l+r)>>1;
 75      if(tr<=mid) Update(lz,tl,tr,c);
 76      else if(tl>mid) Update(rz,tl,tr,c);
 77      else
 78      {
 79          Update(lz,tl,mid,c);    ///注意区间分隔开，tl，tr跨越两个左右区间
 80          Update(rz,mid+1,tr,c);
 81      }
 82      push_up(u,l,r);     ///递归的时候同步向上更新
 83  }
 84  
 85  int Query(int u, int l, int r, int num)   ///询问操作
 86  {
 87      if(l==r)
 88          return l;
 89      push_down(u,l,r);     ///延迟标记向下传递
 90      int mid=(l+r)>>1;
 91      if(tree[2*u].sm>=num) return Query(lz,num);
 92      else if(tree[2*u].rm+tree[2*u+1].lm>=num&&tree[2*u].rm>=1) return mid-tree[2*u].rm+1;   ///满足条件时，返回左边rm连续的hotel第一个房间标号
 93      else
 94          return Query(rz,num);
 95  }
 96  
 97  int main()
 98  {
 99      int n, m;
100      while(~scanf("%d%d",&n,&m))
101      {
102          build(1,1,n);
103          while(m--)
104          {
105              int p, u, v;
106              scanf("%d",&p);
107              if(p==1)
108              {
109                  scanf("%d",&u);
110                  if(tree[1].sm<u)  ///特判一下是否有这么多个连续的空hotel，没有则直接输出，不用操作
111                  {
112                      puts("0"); continue;
113                  }
114                  int p=Query(1,1,n,u);
115                  printf("%d\n",p);
116                  Update(1,1,n,p,p+u-1,1);
117              }
118              else
119              {
120                  scanf("%d%d",&u,&v);
121                  Update(1,1,n,u,u+v-1,0);
122              }
123          }
124      }
125      return 0;
126  }

3、hdu3397 Sequence operation

题目大意：有n个数，可能为0或为1。接下来是m个操作，操作有5种类型。（1）“0 a b”，表示将区间[a,b]范围内的数全部置0；（2）“1 a b”，表示将区间[a,b]内的数全部置1；（3）"2 a b"，表示将区间[a,b]内的数0变成1，1变成0；（4）"3 a b"，表示查询[a,b]范围内1的数；（5）"4 a b"，表示查询[a,b]范围内最长的连续的1；

解题思路：开一个结构体，记录一个区间内0的个数sum0,1的个数sum1，lm0：从左端点开始最长的连续0，lm1：从左端点开始最长的连续1，rm0：以右端点结束最长的0，rm1：以右端点结束最长的1，sm0：整段区间最长的连续0，sm1：整段区间最长的连续1。

这里也要注意先覆盖再异或和先异或再覆盖的区别。先异或再覆盖会把异或标记给覆盖掉，先覆盖再异或则不能把之前的更新覆盖掉。

View Code

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 using namespace std;
  6 
  7 #define lz 2*u,l,mid
  8 #define rz 2*u+1,mid+1,r
  9 const int maxn=100005;
 10 int a[maxn];
 11 int flag[4*maxn];
 12 
 13 struct node
 14 {
 15     int lm0, rm0, sm0;
 16     int lm1, rm1, sm1;
 17     int sum0, sum1;
 18 } tree[4*maxn];
 19 
 20 void Xor(int u)
 21 {
 22     swap(tree[u].sum1,tree[u].sum0);
 23     swap(tree[u].lm1,tree[u].lm0);
 24     swap(tree[u].rm1,tree[u].rm0);
 25     swap(tree[u].sm1,tree[u].sm0);
 26 
 27     if(flag[u]==0) flag[u]=3;
 28     else if(flag[u]==1) flag[u]=2;
 29     else if(flag[u]==2) flag[u]=1;
 30     else if(flag[u]==3) flag[u]=0;
 31 }
 32 
 33 void push_up(int u, int l, int r)
 34 {
 35     tree[u].sum1=tree[2*u].sum1+tree[2*u+1].sum1;
 36     tree[u].sum0=tree[2*u].sum0+tree[2*u+1].sum0;
 37     tree[u].lm0=tree[2*u].lm0;
 38     tree[u].lm1=tree[2*u].lm1;
 39     tree[u].rm0=tree[2*u+1].rm0;
 40     tree[u].rm1=tree[2*u+1].rm1;
 41     tree[u].sm0=max(tree[2*u].sm0,tree[2*u+1].sm0);
 42     tree[u].sm1=max(tree[2*u].sm1,tree[2*u+1].sm1);
 43     int mid=(l+r)>>1;
 44 
 45     if(tree[2*u].lm1==mid-l+1) tree[u].lm1+=tree[2*u+1].lm1;
 46     if(tree[2*u+1].rm1==r-mid) tree[u].rm1+=tree[2*u].rm1;
 47     int t=tree[2*u].rm1+tree[2*u+1].lm1;
 48     if(t>tree[u].sm1) tree[u].sm1=t;
 49 
 50     if(tree[2*u].lm0==mid-l+1) tree[u].lm0+=tree[2*u+1].lm0;
 51     if(tree[2*u+1].rm0==r-mid) tree[u].rm0+=tree[2*u].rm0;
 52     int h=tree[2*u].rm0+tree[2*u+1].lm0;
 53     if(h>tree[u].sm0) tree[u].sm0=h;
 54 }
 55 
 56 void push_down(int u, int l, int r)
 57 {
 58     if(flag[u])
 59     {
 60         int mid=(l+r)>>1;
 61         if(flag[u]==1)
 62         {
 63             tree[2*u].sum1=tree[2*u].lm1=tree[2*u].rm1=tree[2*u].sm1=0;
 64             tree[2*u].sum0=tree[2*u].lm0=tree[2*u].rm0=tree[2*u].sm0=mid-l+1;
 65 
 66             tree[2*u+1].sum1=tree[2*u+1].lm1=tree[2*u+1].rm1=tree[2*u+1].sm1=0;
 67             tree[2*u+1].sum0=tree[2*u+1].lm0=tree[2*u+1].rm0=tree[2*u+1].sm0=r-mid;
 68             flag[2*u]=flag[2*u+1]=1;
 69         }
 70         else if(flag[u]==2)
 71         {
 72             tree[2*u].sum1=tree[2*u].lm1=tree[2*u].rm1=tree[2*u].sm1=mid-l+1;
 73             tree[2*u].sum0=tree[2*u].lm0=tree[2*u].rm0=tree[2*u].sm0=0;
 74 
 75             tree[2*u+1].sum1=tree[2*u+1].lm1=tree[2*u+1].rm1=tree[2*u+1].sm1=r-mid;
 76             tree[2*u+1].sum0=tree[2*u+1].lm0=tree[2*u+1].rm0=tree[2*u+1].sm0=0;
 77             flag[2*u]=flag[2*u+1]=2;
 78         }
 79         else
 80         {
 81             Xor(2*u);
 82             Xor(2*u+1);
 83         }
 84         flag[u]=0;
 85     }
 86 }
 87 
 88 void build(int u, int l, int r)
 89 {
 90     flag[u]=0;
 91     if(l==r)
 92     {
 93         tree[u].sum1=tree[u].lm1=tree[u].rm1=tree[u].sm1=a[l]?1:0;
 94         tree[u].sum0=tree[u].lm0=tree[u].rm0=tree[u].sm0=a[l]?0:1;
 95         return ;
 96     }
 97     int mid=(l+r)>>1;
 98     build(lz);
 99     build(rz);
100     push_up(u,l,r);
101 }
102 
103 void Update(int u, int l, int r, int tl, int tr, int c)
104 {
105     if(tl<=l&&r<=tr)
106     {
107         if(c==1)
108         {
109             tree[u].sum1=tree[u].lm1=tree[u].rm1=tree[u].sm1=0;
110             tree[u].sum0=tree[u].lm0=tree[u].rm0=tree[u].sm0=r-l+1;
111             flag[u]=1;
112         }
113         else if(c==2)
114         {
115             tree[u].sum1=tree[u].lm1=tree[u].rm1=tree[u].sm1=r-l+1;
116             tree[u].sum0=tree[u].lm0=tree[u].rm0=tree[u].sm0=0;
117             flag[u]=2;
118         }
119         else    /// 这里要特别注意，对于异或操作不能把此前的标记给覆盖掉，必须进行相应的更新才能保证向下延迟标记不出错，这里错了好久
120         {
121             Xor(u);
122         }
123         return ;
124     }
125     push_down(u,l,r);
126     int mid=(l+r)>>1;
127     if(tr<=mid) Update(lz,tl,tr,c);
128     else if(tl>mid) Update(rz,tl,tr,c);
129     else
130     {
131         Update(lz,tl,mid,c);
132         Update(rz,mid+1,tr,c);
133     }
134     push_up(u,l,r);
135 }
136 
137 int Query1(int u,int l, int r, int tl, int tr)
138 {
139     if(tl<=l&&r<=tr)
140     {
141         return tree[u].sum1;
142     }
143     push_down(u,l,r);
144     int mid=(l+r)>>1;
145     if(tr<=mid) return Query1(lz,tl,tr);
146     else if(tl>mid) return Query1(rz,tl,tr);
147     else
148     {
149         int t1=Query1(lz,tl,mid);
150         int t2=Query1(rz,mid+1,tr);
151         return t1+t2;
152     }
153 }
154 
155 int Query2(int u, int l, int r, int tl, int tr)
156 {
157     if(tl<=l&&r<=tr)
158     {
159         return tree[u].sm1;
160     }
161     push_down(u,l,r);
162     int mid=(l+r)>>1;
163     if(tr<=mid) return Query2(lz,tl,tr);
164     else if(tl>mid) return Query2(rz,tl,tr);
165     else
166     {
167         int t1=Query2(lz,tl,mid);
168         int t2=Query2(rz,mid+1,tr);
169         int  t=max(t1,t2);
170         t1=min(tree[2*u].rm1,mid-tl+1);
171         t2=min(tree[2*u+1].lm1,tr-mid);
172         t1+=t2;
173         return max(t,t1);
174     }
175 }
176 
177 int main()
178 {
179     int T, n, m;
180     cin >> T;
181     while(T--)
182     {
183         cin >> n >> m;
184         for(int i=0; i<n; i++)
185             scanf("%d",a+i);
186         build(1,0,n-1);
187         while(m--)
188         {
189             int op, l, r;
190             scanf("%d%d%d",&op,&l,&r);
191             op++;
192             if(op==1) Update(1,0,n-1,l,r,1);
193             else if(op==2) Update(1,0,n-1,l,r,2);
194             else if(op==3) Update(1,0,n-1,l,r,3);
195             else if(op==4)
196             {
197                 int sum=Query1(1,0,n-1,l,r);
198                 printf("%d\n",sum);
199             }
200             else
201             {
202                 int len=Query2(1,0,n-1,l,r);
203                 printf("%d\n",len);
204             }
205         }
206     }
207     return 0;
208 }

4、hdu2871 Memory control

题目大意：给n个单元内存，有四个操作：

1、New x 找一段长为x的空区间段填满。（下面用0表示空单元，1表示非空单元。）

2、Free x 释放包含x的区间段

3、 Get x 找到第x个区间段

4、将整个区间都置为空。

解题思路：可以说这题应该算是线段树之区间操作里面比较好的经典题了。要注意的地方很多。对vector容器的用法又了解了很多。赞一个

View Code

  1 #include <cstdio>
  2 #include <vector>
  3 #include <iostream>
  4 using namespace std;
  5 
  6 #define  lz  2*u,l,mid
  7 #define  rz  2*u+1,mid+1,r
  8 const int maxn=50005;
  9 int flag[4*maxn];
 10 
 11 struct segment
 12 {
 13     int lm; // 从区间左端点开始的连续0个数;
 14     int rm; // 以区间右端点结束的连续0个数;
 15     int sm; // 整个区间最长连续的0个数;
 16 } tree[4*maxn];
 17 
 18 struct node
 19 {
 20     int s, d;
 21 };
 22 node tmp;
 23 vector<node>vt;
 24 
 25 void push_up(int u, int l, int r)
 26 {
 27     int mid= (l+r)>>1;
 28     tree[u].lm= tree[u*2].lm;
 29     tree[u].rm= tree[u*2+1].rm;
 30     tree[u].sm= max( tree[u*2].sm, tree[u*2+1].sm );
 31     if( tree[u*2].lm == mid-l+1 ) tree[u].lm += tree[u*2+1].lm;
 32     if( tree[u*2+1].rm == r-mid ) tree[u].rm += tree[u*2].rm;
 33     int t= tree[u*2].rm + tree[u*2+1].lm;
 34     if( t > tree[u].sm )  tree[u].sm= t;
 35 }
 36 
 37 void push_down(int u, int l, int r)
 38 {
 39     if(flag[u]>=0)
 40     {
 41         int mid=(l+r)>>1;
 42         flag[2*u]=flag[2*u+1]=flag[u];
 43         tree[2*u].lm= tree[2*u].rm= tree[2*u].sm= flag[u]?0:mid-l+1;
 44         tree[2*u+1].lm= tree[2*u+1].rm= tree[2*u+1].sm= flag[u]?0:r-mid;
 45         flag[u]=-1;
 46     }
 47 }
 48 
 49 void build(int u, int l, int r)
 50 {
 51     flag[u]=-1;
 52     if(l==r)
 53     {
 54         tree[u].lm= tree[u].rm= tree[u].sm= 1;
 55         return;
 56     }
 57     int mid= (l+r)>>1;
 58     build(lz);
 59     build(rz);
 60     push_up(u, l, r);
 61 }
 62 
 63 void Update(int u, int l, int r, int tl, int tr, int c)
 64 {
 65     if(tl<=l&&r<=tr)
 66     {
 67         tree[u].lm=tree[u].rm=tree[u].sm=c?0:r-l+1;
 68         flag[u]=c;
 69         return ;
 70     }
 71     push_down(u,l,r);
 72     int mid=(l+r)>>1;
 73     if(tr<=mid) Update(lz,tl,tr,c);
 74     else if(tl>mid) Update(rz,tl,tr,c);
 75     else
 76     {
 77         Update(lz,tl,mid,c);
 78         Update(rz,mid+1,tr,c);
 79     }
 80     push_up(u,l,r);
 81 }
 82 
 83 int  Query(int u, int l, int r, int p)
 84 {
 85     if(tree[u].sm==p&&r-l+1==p)   ///不仅要tree[u].sm==p而且要整个区间都被0覆盖，否则会出错
 86     {
 87         return l;
 88     }
 89     push_down(u,l,r);
 90     int mid= (l+r)>>1, t;
 91     if(p<=tree[2*u].sm)  return Query(lz,p);
 92     else if(tree[2*u].rm+tree[2*u+1].lm>=p) return mid-tree[2*u].rm+1;
 93     else return Query(rz,p);
 94 }
 95 
 96 int find(int tp)    
 97 {
 98     int l=0, r=vt.size()-1, mid, ans=-1;
 99     while(l<=r)
100     {
101         int mid=(l+r)>>1;
102         if(vt[mid].s<=tp)
103         {
104             ans=mid;
105             l=mid+1;
106         }
107         else r=mid-1;
108     }
109     return ans;
110 }
111 
112 int main()
113 {
114     int n, m;
115     while(cin >> n >> m)
116     {
117         build(1,1,n);
118         vt.clear();
119         while(m--)
120         {
121             char ch[6];
122             scanf("%s",ch);
123             if(ch[0]=='R')
124             {
125                 vt.clear();
126                 Update(1,1,n,1,n,0);
127                 puts("Reset Now");
128                 continue;
129             }
130             int op;
131             scanf("%d",&op);
132             if(ch[0]=='N')
133             {
134                 if(tree[1].sm>=op)
135                 {
136                     int st=Query(1,1,n,op);
137                     tmp.s=st, tmp.d=st+op-1;
138                     int id=find(tmp.s);
139                     vt.insert(vt.begin()+id+1,tmp); 
140                     
141                     printf("New at %d\n",tmp.s);
142                     Update(1,1,n,tmp.s,tmp.d,1);  ///!!!这里注意了，查询完了还要进行相应的更新
143                 }
144                 else
145                     puts("Reject New");
146             }
147             else if(ch[0]=='G')
148             {
149                 if(vt.size()>=op)
150                     printf("Get at %d\n",vt[op-1].s);
151                 else puts("Reject Get");
152             }
153             else if(ch[0]=='F')
154             {
155                 int id=find(op);
156                 if(id==-1||vt[id].d<op) puts("Reject Free");
157                 else
158                 {
159                     Update(1,1,n,vt[id].s,vt[id].d,0);
160                     printf("Free from %d to %d\n",vt[id].s,vt[id].d);
161                     vt.erase(vt.begin()+id,vt.begin()+id+1); ///删除区间[s，d)内的元素，左闭右开
162                 }
163             }
164         }
165         puts("");
166     }
167     return 0;
168 }

5、hdu1540 Tunnel Warfare

题目大意：有N个村子排成一条直线，每个村子都连接了它的左右两个村子（除了最左边和最右边的外），有3种操作，（1）"D x"，表示将第x个村子摧毁。（2）"Q x"，表示查询与第x个村子直接和间接相连的村子有多少个。（3）"R"，表示将最早摧毁的村子复原。

解题思路：O(-1)

View Code

  1 #include <cstdio>
  2 #include <vector>
  3 #include <map>
  4 #include <iostream>
  5 using namespace std;
  6 
  7 #define  lz  2*u,l,mid
  8 #define  rz  2*u+1,mid+1,r
  9 const int maxn=50005;
 10 int flag[4*maxn];
 11 int stack[maxn];
 12 int top;
 13 
 14 struct segment
 15 {
 16     int lm;
 17     int rm;
 18     int sm;
 19 } tree[4*maxn];
 20 
 21 
 22 void push_up(int u, int l, int r)
 23 {
 24     int mid= (l+r)>>1;
 25     tree[u].lm= tree[u*2].lm;
 26     tree[u].rm= tree[u*2+1].rm;
 27     tree[u].sm= max( tree[u*2].sm, tree[u*2+1].sm );
 28     if( tree[u*2].lm == mid-l+1 ) tree[u].lm += tree[u*2+1].lm;
 29     if( tree[u*2+1].rm == r-mid ) tree[u].rm += tree[u*2].rm;
 30     int t= tree[u*2].rm + tree[u*2+1].lm;
 31     if( t > tree[u].sm )  tree[u].sm= t;
 32 }
 33 
 34 void build(int u, int l, int r)
 35 {
 36     flag[u]=-1;
 37     if(l==r)
 38     {
 39         tree[u].lm= tree[u].rm= tree[u].sm= 1;
 40         return;
 41     }
 42     int mid= (l+r)>>1;
 43     build(lz);
 44     build(rz);
 45     push_up(u, l, r);
 46 }
 47 
 48 void Update(int u, int l, int r, int pos, int c)
 49 {
 50     if(l==r)
 51     {
 52         tree[u].lm=tree[u].rm=tree[u].sm=c;
 53         return ;
 54     }
 55     int mid=(l+r)>>1;
 56     if(pos<=mid) Update(lz,pos,c);
 57     else  Update(rz,pos,c);
 58     push_up(u,l,r);
 59 }
 60 
 61 int  Query(int u, int l, int r, int p)
 62 {
 63     if(tree[u].sm==r-l+1) return tree[u].sm;
 64     if(l==r) return 0;
 65     int mid=(l+r)>>1;
 66     if(mid-tree[2*u].rm+1<=p&&p<=mid+tree[2*u+1].lm)
 67         return tree[2*u].rm+tree[2*u+1].lm;
 68     else if(p<=mid)  return Query(lz,p);
 69     else return Query(rz,p);
 70 }
 71 
 72 int main()
 73 {
 74     int n, m, op;
 75     while(cin >> n >> m)
 76     {
 77         map<int,int>mp;
 78         top=0;
 79         build(1,1,n);
 80         while(m--)
 81         {
 82             char ch[5];
 83             scanf("%s",ch);
 84             if(ch[0]=='D')
 85             {
 86                 scanf("%d",&op);
 87                 Update(1,1,n,op,0);
 88                 stack[++top]=op;
 89             }
 90             else if(ch[0]=='R')
 91             {
 92                 if(top)  Update(1,1,n,stack[top--],1);
 93             }
 94             else
 95             {
 96                 scanf("%d",&op);
 97                 int ans=Query(1,1,n,op);
 98                 printf("%d\n",ans);
 99             }
100         }
101     }
102     return 0;
103 }

四、扫描线

这类题目一般都要用到离散化排序之类，把每个矩阵的上下边先存储起来，每条边在我们意想看来都是一条扫描线，一条接一条的从下往上扫描（像接力赛一样的），每次扫描到的区间覆盖到的区间cover值会发生变化，但是n条扫描线只在总区间上变化，换句话说：覆盖区间只在总区间上变化，总区间一直保持不变。有点抽象，看下面的题理解吧。

1、hdu1542 Atlantis （入门题）

题目大意：给你n个矩形，求他们的总面积之和（覆盖区域只算一次）。

解题思路：详解请移步到here。

View Code

  1 View Code 
  2  #include <iostream>
  3  #include <cstdio>
  4  #include <cstring>
  5  #include <algorithm>
  6  using namespace std;
  7  
  8  #define lz 2*u,l,mid
  9  #define rz 2*u+1,mid+1,r
 10  const int maxn=4222;
 11  double sum[maxn];
 12  int flag[maxn];
 13  double X[maxn];
 14  
 15  struct Node
 16  {
 17      double lx, rx, y;
 18      int s;
 19      Node(){};
 20      Node(double lx_, double rx_, double y_, int s_)
 21      {
 22          lx=lx_, rx=rx_, y=y_, s=s_;
 23      }
 24      bool operator <(const Node &S) const
 25      {
 26          return y<S.y;
 27      }
 28  }line[maxn];
 29  
 30  int find(double tmp, int n)
 31  {
 32      int l=1, r=n, mid;
 33      while(l<=r)
 34      {
 35          mid=(l+r)>>1;
 36          if(X[mid]==tmp) return mid;
 37          else if(X[mid]<tmp) l=mid+1;
 38          else r=mid-1;
 39      }
 40  }
 41  
 42  void push_up(int u, int l, int r)
 43  {
 44      if(flag[u]) sum[u]=X[r+1]-X[l];
 45      else if(l==r) sum[u]=0;
 46      else sum[u]=sum[2*u]+sum[2*u+1];
 47  }
 48  
 49  void Update(int u, int l, int r, int tl, int tr, int c)
 50  {
 51      if(tl<=l&&r<=tr)
 52      {
 53          flag[u]+=c;
 54          push_up(u,l,r);
 55          return ;
 56      }
 57      int mid=(l+r)>>1;
 58      if(tr<=mid) Update(lz,tl,tr,c);
 59      else if(tl>mid) Update(rz,tl,tr,c);
 60      else
 61      {
 62          Update(lz,tl,mid,c);
 63          Update(rz,mid+1,tr,c);
 64      }
 65      push_up(u,l,r);
 66  }
 67  
 68  int main()
 69  {
 70      int n,tcase=0;
 71      while(cin >> n,n)
 72      {
 73          int num=0;
 74          memset(flag,0,sizeof(flag));
 75          memset(sum,0,sizeof(sum));
 76          for(int i=0; i<n; i++)
 77          {
 78              double x1,x2,y1,y2;
 79              scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
 80              line[++num]=Node(x1,x2,y1,1);
 81              X[num]=x1;
 82              line[++num]=Node(x1,x2,y2,-1);
 83              X[num]=x2;
 84          }
 85          sort(X+1,X+num+1);
 86          sort(line+1,line+num+1);
 87          int k=1;
 88          for(int i=2; i<=num; i++)
 89              if(X[i]!=X[i+1]) X[++k]=X[i];
 90          double ans=0;
 91          for(int i=1; i<num; i++)
 92          {
 93              int l=find(line[i].lx,k);
 94              int r=find(line[i].rx,k)-1;
 95              Update(1,1,k,l,r,line[i].s);
 96              ans+=sum[1]*(line[i+1].y-line[i].y);
 97          }
 98          printf("Test case #%d\n",++tcase);
 99          printf("Total explored area: %.2lf\n\n",ans);
100      }
101      return 0;
102  }

2、hdu1828 Picture

题目大意：给你多个矩形，求他们合并后的周长，被覆盖的边不能算进周长之内。

解题思路：其实周长并和面积并没什么很大的区别，只不过周长并增加了判断左右端点是否被覆盖的标记 lbd 和rbd 数组，以及numseg 数组记录连续区间段数。

numseg : 一根扫描线扫描过去，会记录有多少个连续的区间段，每个连续的区间段都有两条相等的竖边，而每次扫描过去竖边长度都相等。

参考文献 :陈宏《数据结构的选择与算法效率》。

View Code

  1 View Code 
  2  #include <iostream>
  3  #include <cstdio>
  4  #include <cstring>
  5  #include <algorithm>
  6  using namespace std;
  7  
  8  #define lz 2*u,l,mid
  9  #define rz 2*u+1,mid+1,r
 10  const int maxn=22222;
 11  int sum[4*maxn];              ///记录被覆盖区间的长度
 12  int lbd[4*maxn], rbd[4*maxn]; ///记录左右端点是否被覆盖
 13  int numseg[4*maxn];            ///记录该区间连续的段数
 14  int flag[4*maxn];              /// 记录该区间是否被覆盖
 15  
 16  struct Node
 17  {
 18      int lx, rx, y, s;
 19      int lbd, rbd;
 20      Node() {};
 21      Node(int lx_, int rx_, int y_, int s_)
 22      {
 23          lx=lx_, rx=rx_, y=y_, s=s_;
 24      }
 25      bool operator <(const Node &S) const
 26      {
 27          if(y==S.y) return s>S.s;
 28          return y<S.y;
 29      }
 30  } line[maxn];
 31  
 32  void push_up(int u, int l, int r)
 33  {
 34      if(flag[u])
 35      {
 36          lbd[u]=1;
 37          rbd[u]=1;
 38          sum[u]=r-l+1;
 39          numseg[u]=2;
 40      }
 41      else if(l==r)
 42      {
 43          sum[u]=numseg[u]=lbd[u]=rbd[u]=0;
 44      }
 45      else
 46      {
 47          lbd[u]=lbd[2*u];
 48          rbd[u]=rbd[2*u+1];
 49          sum[u]=sum[2*u]+sum[2*u+1];
 50          numseg[u]=numseg[2*u]+numseg[2*u+1];
 51          if(rbd[2*u]&&lbd[2*u+1]) numseg[u]-=2;
 52      }
 53  }
 54  
 55  void Update(int u, int l, int r, int tl, int tr, int c)
 56  {
 57      if(tl<=l&&r<=tr)
 58      {
 59          flag[u]+=c;
 60          push_up(u,l,r);
 61          return ;
 62      }
 63      int mid=(l+r)>>1;
 64      if(tr<=mid) Update(lz,tl,tr,c);
 65      else if(tl>mid) Update(rz,tl,tr,c);
 66      else
 67      {
 68          Update(lz,tl,mid,c);
 69          Update(rz,mid+1,tr,c);
 70      }
 71      push_up(u,l,r);
 72  }
 73  
 74  int main()
 75  {
 76      int n;
 77      while(cin >> n)
 78      {
 79          int x1, x2, y1, y2;
 80          int num=0, lbd=10000, rbd=-10000;
 81          for(int i=0; i<n; i++)
 82          {
 83              scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
 84              line[++num]=Node(x1,x2,y1,1);
 85              line[++num]=Node(x1,x2,y2,-1);
 86              lbd=min(lbd,x1);
 87              rbd=max(rbd,x2);
 88          }
 89          sort(line+1,line+num+1);
 90          int ans=0, last=0;
 91          for(int i=1; i<=num; i++)
 92          {
 93              Update(1,lbd,rbd-1,line[i].lx,line[i].rx-1,line[i].s);
 94              ans+=numseg[1]*(line[i+1].y-line[i].y);
 95              ans+=abs(sum[1]-last);
 96              last=sum[1];
 97          }
 98          cout << ans <<endl;
 99      }
100      return 0;
101  }

3、hdu3265 Posters

题目大意：给你n张矩形海报，每张矩形海报在中间剪去一块矩形区域后贴在窗户上，问你贴完所有的海报之后窗户被海报覆盖的区域有多大。

解题思路：其实这题和第一题差不多。对于每张剪出矩形东东的海报，我们可以这样处理：挨着中间空矩形的两条横边或者两条竖边画两条线，那么每张海报不就变成四个实心矩形了么，接下来的解法和第一题一样。

这里要注意的是x1==x2的处理，不然会导致RE。

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5 using namespace std;
 6 
 7 #define  lz  2*u,l,mid
 8 #define  rz  2*u+1,mid+1,r
 9 const int maxn=50005;
10 typedef long long lld;
11 lld sum[4*maxn];
12 int flag[4*maxn];
13 
14 struct Node
15 {
16     int lx, rx, h, s;
17     Node(){}
18     Node(int lx_, int rx_, int h_, int s_)
19     {
20         lx=lx_, rx=rx_, h=h_, s=s_;
21     }
22     bool operator<(const Node &S)const
23     {
24         return h<S.h;
25     }
26 }line[8*maxn];
27 
28 void push_up(int u, int l, int r)
29 {
30     if(flag[u]) sum[u]=r-l+1;
31     else if(l==r) sum[u]=0;
32     else sum[u]=sum[2*u]+sum[2*u+1];
33 }
34 
35 void Update(int u, int l, int r, int tl, int tr, int c)
36 {
37     if(tl>tr) return ;  ///!!!注意 当x1==x2时，会导致RE，因为算区间的时候x2会减-1
38     if(tl<=l&&r<=tr)
39     {
40         flag[u]+=c;
41         push_up(u,l,r);
42         return ;
43     }
44     int mid=(l+r)>>1;
45     if(tr<=mid) Update(lz,tl,tr,c);
46     else if(tl>mid) Update(rz,tl,tr,c);
47     else
48     {
49         Update(lz,tl,mid,c);
50         Update(rz,mid+1,tr,c);
51     }
52     push_up(u,l,r);
53 }
54 
55 int main()
56 {
57     int n;
58     while(cin >> n,n)
59     {
60         memset(flag,0,sizeof(flag));
61         memset(sum,0,sizeof(sum));
62         int num=0;
63         int x1, y1, x2, y2, x3, y3, x4, y4;
64         int lbd=maxn, rbd=-1;
65         for(int i=0; i<n; i++)
66         {
67             scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x4,&y4,&x2,&y2,&x3,&y3);
68             line[++num]=Node(x1,x4,y1,1);
69             line[++num]=Node(x1,x4,y2,-1);
70             line[++num]=Node(x1,x4,y3,1);
71             line[++num]=Node(x1,x4,y4,-1);
72             line[++num]=Node(x1,x2,y2,1);
73             line[++num]=Node(x1,x2,y3,-1);
74             line[++num]=Node(x3,x4,y2,1);
75             line[++num]=Node(x3,x4,y3,-1);
76             lbd=min(x1,lbd);
77             rbd=max(x4,rbd);
78         }
79         sort(line+1,line+num+1);
80         lld ans=0;
81         for(int i=1; i<num; i++)
82         {
83             Update(1,lbd,rbd,line[i].lx,line[i].rx-1,line[i].s);
84             ans+=sum[1]*(lld)(line[i+1].h-line[i].h);
85         }
86         cout << ans <<endl;
87     }
88     return 0;
89 }

4、poj2482 Stars in Your Window

题目大意：给你一些星星的坐标以及这些星星的亮度（x y c），然后给你一个矩形的框框，长宽分别为W、H，让你用这个框框去围住一个矩形的区域，要求区域内的星星亮度总和最大，并且矩形边框的星星不计入气内。

解题思路：对于每颗星星我们都对它进行一次构造，构造一个（W-1）*（H-1）的矩形（为什么不用W*H,因为边框的星星不算入内啦），让星星对应相应的构造矩形区域的最左下角，题目不就可以转化成求某点最大的覆盖亮度了么。每次更新前，记录总区间内某点覆盖亮度的最大值，最后取得最大值。

题目上半部分：很优美的情书。题目下半部分：很经典的扫描线构造题。赞一个。

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <iostream>
  5 using namespace std;
  6 
  7 #define  lz  2*u,l,mid
  8 #define  rz  2*u+1,mid+1,r
  9 const int maxn=50005;
 10 __int64 max_sum[4*maxn];
 11 __int64 flag[4*maxn];
 12 __int64 X[maxn];
 13 
 14 struct Node
 15 {
 16     __int64 lx, rx, h, s;
 17     Node() {}
 18     Node(__int64 lx_, __int64 rx_, __int64 h_, __int64 s_)
 19     {
 20         lx=lx_, rx=rx_, h=h_, s=s_;
 21     }
 22     bool operator<(const Node &S)const
 23     {
 24         if(h==S.h) return s>S.s; ///!!!注意这里，错了无数次
 25         return h<S.h;
 26     }
 27 } line[2*maxn];
 28 
 29 void push_down(int u, int l, int r)
 30 {
 31     if(flag[u]!=0)
 32     {
 33         flag[2*u]+=flag[u];
 34         flag[2*u+1]+=flag[u];
 35         max_sum[2*u]+=flag[u];
 36         max_sum[2*u+1]+=flag[u];
 37         flag[u]=0;
 38     }
 39 }
 40 
 41 void Update(int u, int l, int r, int tl, int tr, int c)
 42 {
 43     if(tl>tr) return ;  ///!!!注意 当x1==x2时，会导致RE，因为算区间的时候x2会减-1
 44     if(tl<=l&&r<=tr)
 45     {
 46         flag[u]+=c;
 47         max_sum[u]+=c;
 48         return ;
 49     }
 50     push_down(u,l,r);
 51     int mid=(l+r)>>1;
 52     if(tr<=mid) Update(lz,tl,tr,c);
 53     else if(tl>mid) Update(rz,tl,tr,c);
 54     else
 55     {
 56         Update(lz,tl,mid,c);
 57         Update(rz,mid+1,tr,c);
 58     }
 59     max_sum[u]=max(max_sum[2*u],max_sum[2*u+1]);
 60 }
 61 
 62 int find(__int64 tmp, int n)
 63 {
 64     int l=1, r=n, mid;
 65     while(l<=r)
 66     {
 67         mid=(l+r)>>1;
 68         if(X[mid]==tmp) return mid;
 69         else if(X[mid]<tmp) l=mid+1;
 70         else r=mid-1;
 71     }
 72 }
 73 
 74 int main()
 75 {
 76     int n, w, h;
 77     while(cin >> n >> w >> h)
 78     {
 79         memset(flag,0,sizeof(flag));
 80         memset(max_sum,0,sizeof(max_sum));
 81         int num=0, ep=1;
 82         __int64 x,y,c;
 83         for(int i=0; i<n; i++)
 84         {
 85             scanf("%I64d%I64d%I64d",&x,&y,&c);
 86             line[++num]=Node(x,x+w-1,y,c);
 87             X[num]=x;
 88             line[++num]=Node(x,x+w-1,y+h-1,-c);
 89             X[num]=x+w-1;
 90         }
 91         sort(X+1,X+num+1);
 92         sort(line+1,line+num+1);
 93         for(int i=2; i<=num; i++)
 94             if(X[i]!=X[ep])  X[++ep]=X[i];
 95         __int64 ans=0, lbd=1, rbd=ep;
 96         for(int i=1; i<num; i++)
 97         {
 98             int l=find(line[i].lx,ep);
 99             int r=find(line[i].rx,ep);
100             Update(1,lbd,rbd,l,r,line[i].s);
101             ans=max(ans,max_sum[1]);
102         }
103         cout << ans <<endl;
104     }
105     return 0;
106 }

5、hdu3642 Get The Treasury

题目大意：给你n个立方体，求相交区域大于等于三次的体积和。

解题思路：其实吧，三维的和二维的其实差不多。如果一个立方体的高为h，那么我们可以把它分割成h层，对每一层进行面积并的扫描，注意是从下往上。

这题离散化x坐标是为了方便建树，离散化z坐标是为了节约时间。剩下的问题就变成了如何求覆盖大于等于三次体积范围。

问题同样可以转化为二维的面积并求解，对每一层进行扫描，每层求覆盖大于等于三次的面积区域。每层求的结果加起来就是答案了。

View Code

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 using namespace std;
  6 
  7 #define lz 2*u,l,mid
  8 #define rz 2*u+1,mid+1,r
  9 const int maxn=2222;
 10 typedef long long lld;
 11 int flag[4*maxn];
 12 lld sum1[4*maxn], sum2[4*maxn], sum3[4*maxn];
 13 int X[maxn], Z[maxn];
 14 
 15 struct Node
 16 {
 17     int lx, rx, y, z1, z2, s;
 18     Node() {}
 19     Node(int lx_, int rx_ , int y_, int zm_, int zl_, int s_)
 20     {
 21         lx=lx_, rx=rx_, y=y_, z1=zm_, z2=zl_, s=s_;
 22     }
 23     bool operator<(const Node &S) const
 24     {
 25         if(y==S.y) return s>S.s;
 26         else return y<S.y;
 27     }
 28 } line[maxn], tmp[maxn];
 29 
 30 void push_up(int u, int l, int r)
 31 {
 32     if(flag[u]>=3)   ///开始写成了flag[u]==3， wrong answer了一个晚上
 33     {
 34         sum3[u]=sum2[u]=sum1[u]=X[r+1]-X[l];
 35     }
 36     else if(flag[u]==2)
 37     {
 38 
 39         sum2[u]=sum1[u]=X[r+1]-X[l];
 40         if(l==r)sum3[u]=0;
 41         else
 42             sum3[u]=sum1[2*u]+sum1[2*u+1];
 43     }
 44     else if(flag[u]==1)
 45     {
 46         sum1[u]=X[r+1]-X[l];
 47         if(l==r)sum2[u]=sum3[u]=0;
 48         else
 49         {
 50             sum2[u]=sum1[2*u]+sum1[2*u+1];
 51             sum3[u]=sum2[2*u]+sum2[2*u+1];
 52         }
 53     }
 54     else
 55     {
 56         if(l==r)sum1[u]=sum2[u]=sum3[u]=0;
 57         else
 58         {
 59             sum1[u]=sum1[2*u]+sum1[2*u+1];
 60             sum2[u]=sum2[2*u]+sum2[2*u+1];
 61             sum3[u]=sum3[2*u]+sum3[2*u+1];
 62         }
 63     }
 64 }
 65 
 66 void Update(int u, int l, int r, int tl, int tr, int c)
 67 {
 68     if(tl>tr) return ;
 69     if(tl<=l&&r<=tr)
 70     {
 71         flag[u]+=c;
 72         push_up(u,l,r);
 73         return ;
 74     }
 75     int mid=(l+r)>>1;
 76     if(tr<=mid) Update(lz,tl,tr,c);
 77     else if(tl>mid) Update(rz,tl,tr,c);
 78     else
 79     {
 80         Update(lz,tl,mid,c);
 81         Update(rz,mid+1,tr,c);
 82     }
 83     push_up(u,l,r);
 84 }
 85 
 86 int find(int tmp, int n)
 87 {
 88     int l=1, r=n, mid;
 89     while(l<=r)
 90     {
 91         mid=(l+r)>>1;
 92         if(X[mid]==tmp) return mid;
 93         else if(X[mid]<tmp) l=mid+1;
 94         else r=mid-1;
 95     }
 96 }
 97 
 98 int main()
 99 {
100     int T, n, tcase=0;
101     cin >> T;
102     while(T--)
103     {
104         cin >> n ;
105         int num=0;
106         for(int i=0; i<n; i++)
107         {
108             int x1, y1, x2, y2, z1, z2;
109             scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
110             line[++num]=Node(x1,x2,y1,z1,z2,1);
111             X[num]=x1, Z[num]=z1;
112             line[++num]=Node(x1,x2,y2,z1,z2,-1);
113             X[num]=x2, Z[num]=z2;
114         }
115         sort(line+1,line+num+1);
116         sort(X+1,X+num+1);
117         sort(Z+1,Z+num+1);
118         int ep=1, m=1;
119         for(int i=2; i<=num; i++)
120             if(X[i]!=X[ep]) X[++ep]=X[i];
121         for(int i=2; i<=num; i++)
122             if(Z[i]!=Z[m]) Z[++m]=Z[i];
123         lld ans=0;
124         for(int j=1; j<m; j++)
125         {
126             memset(flag,0,sizeof(flag));
127             memset(sum1,0,sizeof(sum1));
128             memset(sum2,0,sizeof(sum2));
129             memset(sum3,0,sizeof(sum3));
130             lld tp=0, cnt=0;
131             for(int i=1; i<=num; i++)
132             {
133                 if(line[i].z1<=Z[j]&&Z[j]<line[i].z2)
134                     tmp[++cnt]=line[i];
135             }
136             for(int i=1; i<cnt; i++)
137             {
138                 int l=find(tmp[i].lx,ep);
139                 int r=find(tmp[i].rx,ep)-1;
140                 Update(1,1,ep-1,l,r,tmp[i].s);
141                 tp+=(lld)sum3[1]*(lld)(tmp[i+1].y-tmp[i].y);
142             }
143             ans+=(lld)tp*(lld)(Z[j+1]-Z[j]);
144         }
145         printf("Case %d: %I64d\n",++tcase,ans);
146     }
147     return 0;
148 }

6、hdu3255 Farming

题目大意：有n块蔬菜地，每块蔬菜地中种一种作物，每种作物都有一个价格，当在同一区域内种植了两种不同的作物时，作物价格大的生存下来，作物价格小的死亡。问你最后能得到的最大利润是多少。

解题思路：每块蔬菜地种植蔬菜收获的利润为 val=x*y*price。面积乘以价格，题目的重点转换在于如何确定重叠区域怎么让它种植最贵的蔬菜。

观察利润计算公式 : x*y*price <==> x*y*h 可以转换为求体积并。

说实话，这题一看真的很简单，一交就是一直错，代码每个部分都有调试N遍，重拍了几次。昨天一个就一直在调试，五个小时无果。和别人一对照，思路一点都没错，今天下午再重拍了一遍代码，又开始了Wrong answer之路，然后带着那颗受伤的心去改数组范围。点最大3W，我线段树开12W多，存X的点开6W多。点开4W错， 6W TLE，索性所有数组范围开150005，错。 150101 AC。把我整伤心了！！！

View Code

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 using namespace std;
  6 
  7 #define lson l,mid,ID<<1
  8 #define rson mid+1,r,ID<<1|1
  9 const int maxn=150101;
 10 typedef long long lld;
 11 int flag[maxn];
 12 lld sum[maxn];
 13 int X[maxn], Z[maxn];
 14 
 15 struct Node   ///这题快把我整哭了
 16 {
 17     int lx, rx, y, z, s;
 18     Node(){}
 19     Node(int lx_, int rx_ , int y_, int z_, int s_)
 20     {
 21         lx=lx_, rx=rx_, y=y_, z=z_, s=s_;
 22     }
 23     bool operator<(const Node &S) const
 24     {
 25         if(y==S.y) return s>S.s;
 26         else return y<S.y;
 27     }
 28 }line[maxn], tmp[maxn];
 29 
 30 
 31 int find(int x, int M)
 32 {
 33     int l,r,m;
 34     l=1;
 35     r=M;
 36     while(l<=r)
 37     {
 38         m=(l+r)>>1;
 39         if(X[m]==x)
 40             return m;
 41         if(X[m]<x)
 42             l=m+1;
 43         else
 44             r=m-1;
 45     }
 46 }
 47 void Push_up(int ID,int l,int r)
 48 {
 49     if(flag[ID])sum[ID]=X[r+1]-X[l];
 50     else if(l==r)sum[ID]=0;
 51     else sum[ID]=sum[ID<<1]+sum[ID<<1|1];
 52 }
 53 void Update(int x,int y,int z,int l,int r,int ID)
 54 {
 55     int mid;
 56     if(x<=l&&r<=y)
 57     {
 58         flag[ID]+=z;
 59         Push_up(ID,l,r);
 60         return ;
 61     }
 62     mid=(l+r)>>1;
 63     if(x<=mid)
 64         Update(x,y,z,lson);
 65     if(y>mid)
 66         Update(x,y,z,rson);
 67     Push_up(ID,l,r);
 68 }
 69 
 70 int main()
 71 {
 72     int n, m, T, tcase=0;
 73     cin >> T;
 74     while(T--)
 75     {
 76         cin >> n >> m;
 77         Z[0]=0;
 78         for(int i=1; i<=m; i++)
 79             cin >> Z[i];
 80         int num=0;
 81         for(int i=0; i<n; i++)
 82         {
 83             int x1, x2, y1, y2, id;
 84             scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&id);
 85             line[++num]=Node(x1,x2,y1,Z[id],1);
 86             X[num]=x1;
 87             line[++num]=Node(x1,x2,y2,Z[id],-1);
 88             X[num]=x2;
 89         }
 90         sort(Z,Z+m+1);
 91         sort(X+1,X+num+1);
 92         sort(line+1,line+num+1);
 93         int ep=1;
 94         for(int i=2; i<=num; i++)
 95             if(X[i]!=X[ep]) X[++ep]=X[i];
 96         lld ans=0;
 97         for(int i=0; i<m; i++)
 98         {
 99             memset(sum,0,sizeof(sum));
100             memset(flag,0,sizeof(flag));
101             lld tp=0, cnt=0;
102             for(int j=1; j<=num; j++)
103                if(line[j].z>Z[i]) tmp[++cnt]=line[j];
104             for(int j=1; j<cnt; j++)
105             {
106                 int l=find(tmp[j].lx,ep);
107                 int r=find(tmp[j].rx,ep)-1;
108                 Update(l,r,tmp[j].s,1,ep-1,1);
109                 tp+=sum[1]*(lld)(tmp[j+1].y-tmp[j].y);
110             }
111             ans+=tp*(lld)(Z[i+1]-Z[i]);
112         }
113         printf("Case %d: %I64d\n",++tcase,ans);
114     }
115     return 0;
116 }