[关闭]
@sensitive-cs 2017-03-30T20:33:10.000000Z 字数 8596 阅读 905

CQUPT 线段树

题解

HDU 1166：敌兵布阵
题意：
给出n个数，有3种操作，一种是对某个数加上一个数，一种是对某个数减去一个数，一种是查询一个区间内的数的和。
思路：
线段树裸题，主要是点更新，也可以用树状数组做。(巨坑的是位运算的时候以为除以2，就写的2，导致wa了几发，引以为戒。
代码：

  1. #include <stdio.h>
  2. #include <string.h>
  4. int a[50005];
  5. int sum[200005];
  7. void pushup(int rt)
  8. {
  9.     sum[rt] = sum[rt<<1] + sum[rt << 1|1];
  10. }
  12. void build(int l,int r,int rt)
  13. {
  14.     if (l == r)
  15.     {
  16.         sum[rt] = a[l];
  17.         return;
  18.     }
  20.     int m = (l+r) >> 1;
  22.     build(l,m,rt << 1);
  23.     build(m+1,r,rt << 1|1);
  25.     pushup(rt);
  26. }
  28. void update(int ll,int c,int l,int r,int rt)
  29. {
  30.     if (l == r)
  31.     {
  32.         sum[rt] += c;
  34.         return;
  35.     }
  37.     int m = (l+r) >> 1;
  39.     if (ll <= m) update(ll,c,l,m,rt << 1);
  40.     else update(ll,c,m+1,r,rt << 1|1);
  42.     pushup(rt);
  43. }
  45. int query(int ll,int rr,int l,int r,int rt)
  46. {
  47.     if (ll <= l && r <= rr)
  48.     {
  49.         return sum[rt];
  50.     }
  52.     int m = (l+r) >> 1;
  54.     int ans = 0;
  56.     if (ll <= m) ans += query(ll,rr,l,m,rt << 1);
  57.     if (rr > m) ans += query(ll,rr,m+1,r,rt << 1|1);
  59.     return ans;
  60. }
  62. int main()
  63. {
  64.     int t;
  66.     scanf("%d",&t);
  68.     for (int o = 1;o <= t;o++)
  69.     {
  70.         int n;
  72.         scanf("%d",&n);
  74.         for (int i = 1;i <= n;i++)
  75.             scanf("%d",&a[i]);
  77.         build(1,n,1);
  79.         char ch[20];
  81.         printf("Case %d:\n",o);
  83.         while (scanf("%s",ch) != EOF)
  84.         {
  85.             if (ch[0] == 'E') break;
  87.             int x,y;
  88.             scanf("%d%d",&x,&y);
  90.             if (ch[0] == 'S')
  91.             {
  92.                 update(x,-y,1,n,1);
  93.             }
  94.             if (ch[0] == 'A')
  95.             {
  96.                 update(x,y,1,n,1);
  97.             }
  98.             if (ch[0] == 'Q')
  99.             {
  100.                 int ans = 0;
  101.                 ans = query(x,y,1,n,1);
  102.                 printf("%d\n",ans);
  103.             }
  104.         }
  105.     }
  107.     return 0;
  108. }

poj 3468：A SIMPLE PROBLEM WITH INTEGERS
题意：
给出n个数字，两种操作，一种是给给定区间内的每一个数加上一个数，另一种是查询某个区间内的数字之和。
思路：
纯线段树裸题，直接套模板。不过要注意先建树（又差点卡死2333，再进行操作。
代码：

  1. #include <string.h>
  2. #include <stdio.h>
  4. int a[100005];
  5. long long add[400005];
  6. long long sum[400005];
  8. void pushup(int rt)
  9. {
  10.     sum[rt] = sum[rt << 1] + sum[rt << 1|1];
  11. }
  13. void build(int l,int r,int rt)
  14. {
  15.     if (l == r)
  16.     {
  17.         sum[rt] = a[l];
  18.         return;
  19.     }
  21.     int m = (l+r) >> 1;
  23.     build(l,m,rt << 1);
  24.     build(m+1,r,rt << 1|1);
  26.     pushup(rt);
  27. }
  29. void pushdown(int rt,int ln,int rn)
  30. {
  31.     if (add[rt])
  32.     {
  33.         add[rt << 1] += add[rt];
  34.         add[rt << 1|1] += add[rt];
  36.         sum[rt << 1] += ln * add[rt];
  37.         sum[rt << 1|1] += rn *add[rt];
  39.         add[rt] = 0;
  40.     }
  41. }
  43. void update(int ll,int rr,int c,int l,int r,int rt)
  44. {
  45.     if (ll <= l && r <= rr)
  46.     {
  47.         sum[rt] += c*(r-l+1);
  48.         add[rt] += c;
  49.         return;
  50.     }
  52.     int m = (l+r) >> 1;
  54.     pushdown(rt,m-l+1,r-m);
  56.     if (ll <= m) update(ll,rr,c,l,m,rt << 1);
  57.     if (rr > m) update(ll,rr,c,m+1,r,rt << 1|1);
  59.     pushup(rt);
  60. }
  62. long long query(int ll,int rr,int l,int r,int rt)
  63. {
  64.     if (ll <= l && r <= rr)
  65.     {
  66.         return sum[rt];
  67.     }
  69.     int m = (l+r) >> 1;
  71.     pushdown(rt,m-l+1,r-m);
  73.     long long ans = 0;
  75.     if (ll <= m) ans += query(ll,rr,l,m,rt << 1);
  76.     if (rr > m) ans += query(ll,rr,m+1,r,rt << 1|1);
  78.     return ans;
  79. }
  81. int main()
  82. {
  83.     int n,q;
  85.     scanf("%d%d",&n,&q);
  87.     memset(a,0,sizeof(a));
  88.     memset(add,0,sizeof(add));
  89.     memset(sum,0,sizeof(sum));
  91.     for (int i = 1;i <= n;i++)
  92.         scanf("%d",&a[i]);
  94.     build(1,n,1);
  96.     for (int i = 1;i <= q;i++)
  97.     {
  98.         char s[10];
  100.         scanf("%s",s);
  101.         int x,y,z;
  103.         if (s[0] == 'Q')
  104.         {
  105.             scanf("%d%d",&x,&y);
  107.             long long res = query(x,y,1,n,1);
  109.             printf("%I64d\n",res);
  110.         }
  111.         else
  112.         {
  113.             scanf("%d%d%d",&x,&y,&z);
  115.             update(x,y,z,1,n,1);
  116.         }
  117.     }
  119.     return 0;
  120. }

HDU 1556:COLOR THE BALL
题意：
给出n个区间，每次对1个区间进行更新，对区间的每个数都加1，问每个数被更新了多少次。
思路：
线段树裸题，区间更新，单点查询，也可以用区间查询，左右端点相同就可以了。
代码：

  1. #include <string.h>
  2. #include <stdio.h>
  4. int a[100005];
  5. int add[400005];
  6. int sum[400005];
  8. void pushup(int rt)
  9. {
  10.     sum[rt] = sum[rt << 1] + sum[rt << 1|1];
  11. }
  13. void build(int l,int r,int rt)
  14. {
  15.     if (l == r)
  16.     {
  17.         sum[rt] = a[l];
  18.         return;
  19.     }
  21.     int m = (l+r) >> 1;
  23.     build(l,m,rt << 1);
  24.     build(m+1,r,rt << 1|1);
  26.     pushup(rt);
  27. }
  29. void pushdown(int rt,int ln,int rn)
  30. {
  31.     if (add[rt])
  32.     {
  33.         add[rt << 1] += add[rt];
  34.         add[rt << 1|1] += add[rt];
  36.         sum[rt << 1] += ln * add[rt];
  37.         sum[rt << 1|1] += rn *add[rt];
  39.         add[rt] = 0;
  40.     }
  41. }
  43. void update(int ll,int rr,int c,int l,int r,int rt)
  44. {
  45.     if (ll <= l && r <= rr)
  46.     {
  47.         sum[rt] += c*(r-l+1);
  48.         add[rt] += c;
  49.         return;
  50.     }
  52.     int m = (l+r) >> 1;
  54.     pushdown(rt,m-l+1,r-m);
  56.     if (ll <= m) update(ll,rr,c,l,m,rt << 1);
  57.     if (rr > m) update(ll,rr,c,m+1,r,rt << 1|1);
  59.     pushup(rt);
  60. }
  62. long long query(int ll,int rr,int l,int r,int rt)
  63. {
  64.     if (ll <= l && r <= rr)
  65.     {
  66.         return sum[rt];
  67.     }
  69.     int m = (l+r) >> 1;
  71.     pushdown(rt,m-l+1,r-m);
  73.     long long ans = 0;
  75.     if (ll <= m) ans += query(ll,rr,l,m,rt << 1);
  76.     if (rr > m) ans += query(ll,rr,m+1,r,rt << 1|1);
  78.     return ans;
  79. }
  81. int main()
  82. {
  83.     int n;
  85.     while (scanf("%d",&n) == 1&& n)
  86.     {
  87.         memset(a,0,sizeof(a));
  88.         memset(add,0,sizeof(add));
  89.         memset(sum,0,sizeof(sum));
  91.         build(1,n,1);
  93.         for (int i = 1;i <= n;i++)
  94.         {
  95.             int a,b;
  97.             scanf("%d%d",&a,&b);
  99.             update(a,b,1,1,n,1);
  100.         }
  102.         for (int i = 1;i <= n;i++)
  103.         {
  104.             int res = query(i,i,1,n,1);
  106.             if (i == 1) printf("%d",res);
  107.             else printf(" %d",res);
  108.         }
  110.         printf("\n");
  111.     }
  113.     return 0;
  114. }

HDU1540:tunnel warfare
题意：
有n个村庄，他们是连着的，由于战争，有些村庄被毁了，被毁了之后又恢复。现在有3种指令，一种是毁灭村庄，另一种是回复村庄，还有一种是查询一个村庄连着的村庄有多少个。
思路1：
由于是跟区间有关，求区间的最大长度，所以说用线段树的区间合并，注释在代码中。
思路2：
看了一篇博客，博主天纵奇才，想到只用线段树的单点更新。
比如现在有1 2 3 4 5 6 7 8有8个村庄，我回去2和7，查询4的时候就是7-2-1。
博主想到最大值树和最小值树，最大值树就用一个很大的之来初始化，最小值数就用-1初始化，每次毁掉村庄，就用这个村庄的端点去覆盖-1或者最大值。当查询的时候，就用查询点左边的最大值，和查询点右边的最小值，进行如7-2-1这样的操作就行了。
注意防止越界的方法，把0点赋值为-1，n+1点赋值为无穷大就行了。
代码1：

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <algorithm>
  4. using namespace std;
  6. const int cnt = 50010;
  8. struct ss
  9. {
  10.     int l,r;
  11.     int ls,rs,ms;
  12. }node[4*cnt];
  14. int st[cnt];
  16. void build(int l,int r,int rt)
  17. {
  18.     node[rt].l = l,node[rt].r = r;
  20.     node[rt].ls = node[rt].rs = node[rt].ms = r - l + 1;
  22.     if (l != r)
  23.     {
  24.         int mid = (l+r) >> 1;
  25.         build(l,mid,rt << 1);
  26.         build(mid+1,r,rt << 1|1);
  27.     }
  29.     return;
  30. }
  32. void update(int rt,int x,int flag)
  33. {
  34.     if (node[rt].l == node[rt].r)
  35.     {
  36.         node[rt].ls = node[rt].ms = node[rt].rs = flag;
  37.         return;
  38.     }
  40.     int mid = (node[rt].l + node[rt].r) >> 1;
  42.     if (x <= mid) update(rt << 1,x,flag);
  43.     else update(rt << 1|1,x,flag);
  45.     node[rt].ls = node[rt << 1].ls;
  46.     node[rt].rs = node[rt << 1|1].rs;
  48.     if (node[rt << 1].ms == node[rt << 1].r - node[rt << 1].l + 1)
  49.         node[rt].ls += node[rt << 1|1].ls;
  51.     if (node[rt << 1|1].ms == node[rt << 1|1].r - node[rt << 1|1].l+1)
  52.         node[rt].rs += node[rt << 1].rs;
  54.     node[rt].ms = max(max(node[rt<<1].ms,node[rt << 1|1].ms),node[rt << 1].rs + node[rt << 1|1].ls);
  55. }
  57. int query(int rt,int x)
  58. {
  59.     if (node[rt].r == node[rt].l || node[rt].ms == 0 || node[rt].ms == node[rt].r - node[rt].l + 1)
  60.     {
  61.         return node[rt].ms;
  62.     }
  64.     int mid = (node[rt].l + node[rt].r) >> 1;
  66.     if (x <= mid)
  67.     {
  68.         if (x < node[rt << 1].r - node[rt << 1].rs + 1)
  69.             return query(rt << 1,x);
  70.         else
  71.             return node[rt << 1].rs + node[rt << 1|1].ls;
  72.     }
  73.     else
  74.     {
  75.         if (x > node[rt << 1|1].l + node[rt << 1|1].ls - 1)
  76.             return query(rt << 1|1,x);
  77.         else
  78.             return node[rt << 1].rs + node[rt << 1|1].ls;
  79.     }
  80. }
  82. int main()
  83. {
  84.     int n,m;
  86.     while (scanf("%d%d",&n,&m) != EOF)
  87.     {
  88.         memset(st,0,sizeof(st));
  89.         build(1,n,1);
  91.         int top = 0;
  93.         for (int i = 0;i < m;i++)
  94.         {
  95.             char t[5];
  97.             scanf("%s",t);
  99.             if (t[0] == 'D')
  100.             {
  101.                 int x;
  102.                 scanf("%d",&x);
  103.                 update(1,x,0);
  104.                 st[top++] = x;
  105.             }
  107.             if (t[0] == 'R')
  108.             {
  109.                 int x = st[--top];
  111.                 update(1,x,1);
  112.             }
  114.             if (t[0] == 'Q')
  115.             {
  116.                 int x;
  117.                 scanf("%d",&x);
  118.                 int sum = query(1,x);
  120.                 printf("%d\n",sum);
  121.             }
  122.         }
  123.     }
  125.     return 0;
  126. }

代码2

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <algorithm>
  4. using namespace std;
  6. const int inf = 0x3f3f3f3f;
  7. const int cnt = 5e4+10;
  9. int ma[cnt << 2];
  10. int mi[cnt << 2];
  11. int st[cnt];
  13. int g = inf,v = -1;
  14. int m,n;
  16. void update(int rt,int x,int flag,int l,int r)
  17. {
  18.     if (l == r)
  19.     {
  21.         if (flag)
  22.         {
  23.             ma[rt] = -1;
  24.             mi[rt] = inf;
  25.         }
  26.         else
  27.             mi[rt] = ma[rt] = x;
  29.         return;
  30.     }
  32.     int mid = (l+r) >> 1;
  34.     if (x <= mid) update(rt << 1,x,flag,l,mid);
  35.     else update(rt << 1|1,x,flag,mid+1,r);
  37.     ma[rt] = max(ma[rt << 1],ma[rt << 1|1]);
  38.     mi[rt] = min(mi[rt << 1],mi[rt << 1|1]);
  40.     return;
  41. }
  43. void query1(int rt,int l,int r,int L,int R)
  44. {
  45.     if (l >= L && r <= R)
  46.     {
  47.         g = min(g,mi[rt]);
  48.         return;
  49.     }
  51.     int mid = (l+r) >> 1;
  53.     if (L <= mid)  query1(rt << 1,l,mid,L,R);
  54.     if (R > mid)  query1(rt << 1|1,mid+1,r,L,R);
  56. }
  58. void query2(int rt,int l,int r,int L,int R)
  59. {
  60.     if (l >= L && r <= R)
  61.     {
  62.         v = max(v,ma[rt]);
  63.         return;
  64.     }
  67.     int mid = (l+r) >> 1;
  69.     if (L <= mid)  query2(rt << 1,l,mid,L,R);
  70.     if (R > mid)  query2(rt << 1|1,mid+1,r,L,R);
  72. }
  74. int main()
  75. {
  77.     while (scanf("%d%d",&n,&m) != EOF)
  78.     {
  79.         memset(ma,-1,sizeof(ma));
  80.         memset(mi,inf,sizeof(mi));
  81.         memset(st,0,sizeof(st));
  83.         int top = 0;
  85.         update(1,0,0,0,n+1);
  86.         update(1,n+1,0,0,n+1);
  88.         for (int i = 0;i < m;i++)
  89.         {
  90.             char s[5];
  92.             scanf("%s",s);
  94.             if (s[0] == 'D')
  95.             {
  96.                 int x;
  97.                 scanf("%d",&x);
  98.                 st[top++] = x;
  99.                 update(1,x,0,0,n+1);
  100.             }
  102.             if (s[0] == 'R')
  103.             {
  104.                 int x = st[--top];
  106.                 update(1,x,1,0,n+1);
  107.             }
  109.             if (s[0] == 'Q')
  110.             {
  111.                 int x;
  112.                 scanf("%d",&x);
  114.                 g = inf;
  115.                 v = -1;
  117.                 query1(1,0,n+1,x,n+1);
  118.                 query2(1,0,n+1,0,x);
  120.                 if (g == v)
  121.                     printf("0\n");
  122.                 else
  123.                     printf("%d\n",g - v - 1);
  124.             }
  125.         }
  126.     }
  129.     return 0;
  130. }

poj2528:mayor's posters
题意：
相当于区间染色问题，有一面墙，开始时没有颜色，给出n个操作，每一次染一种颜色，每次染的颜色都不同，问最后墙上有多少颜色。
思路：
一开始想到了是线段树，但是奈何区间太大，1000万的数量级。后来搜题解报告知道了是离散化，所以就浅浅的学习了一下。离散化，对于这题，就是把大的区间映射到小的区间以减小复杂度。但是这题的离散化比较特殊，需要在不连续的坐标之间随意添加一个中间小的数，才能够保证不出错，这一点可以自己举例子理解。最开始写线段树，忘了，就偷懒写了简化版的线段树，果断tle，后来再次按照模板写，wa了，再一看，居然是pushdown在query的时候也需要下方，唉，还是不要懒，more haste,less speed。谨记！！！

代码：

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <map>
  4. #include <vector>
  5. #include <algorithm>
  6. using namespace std;
  8. bool cx[10000005];
  9. vector<int> xl;
  11. int x[10005],y[10005];
  12. int a[10000005];
  13. int ans[10005];
  14. int b[200005],lazy[200005];
  16. void pushdown(int rt)
  17. {
  18.     if (lazy[rt] != -1)
  19.     {
  20.         lazy[rt << 1] = lazy[rt << 1|1] = lazy[rt];
  21.         b[rt << 1] = b[rt << 1|1] = b[rt] = lazy[rt];
  22.         lazy[rt] = -1;
  23.     }
  24. }
  26. void update(int l,int r,int k,int ll,int rr,int rt)
  27. {
  28.     //printf("***\n");
  29.     if (l >= ll && r <= rr)
  30.     {
  31.         b[rt] = k;
  32.         lazy[rt] = k;
  33.         return;
  34.     }
  35.     else
  36.     {
  37.         pushdown(rt);
  39.         int mid = (l + r) >> 1;
  41.         if (ll <= mid) update(l,mid,k,ll,rr,rt << 1);
  42.         if (rr > mid) update(mid+1,r,k,ll,rr,rt << 1|1);
  43.     }
  44. }
  46. void query(int l,int r,int rt)
  47. {
  48.     if (l == r)
  49.     {
  50.         ans[b[rt]]++;
  51.         return;
  52.     }
  54.     pushdown(rt);
  56.     int mid = (l+r) >> 1;
  58.     query(l,mid,rt << 1);
  59.     query(mid+1,r,rt << 1|1);
  60. }
  62. int main()
  63. {
  64.     int t;
  66.     scanf("%d",&t);
  68.     while (t--)
  69.     {
  70.         int n;
  72.         memset(x,0,sizeof(x));
  73.         memset(y,0,sizeof(y));
  74.         memset(a,0,sizeof(a));
  75.         memset(ans,0,sizeof(ans));
  76.         memset(cx,0,sizeof(cx));
  77.         memset(b,0,sizeof(b));
  78.         memset(lazy,-1,sizeof(lazy));
  80.         scanf("%d",&n);
  82.         xl.clear();
  84.         for (int i = 1;i <= n;i++)
  85.         {
  87.             scanf("%d%d",&x[i],&y[i]);
  89.             if (!cx[x[i]])
  90.             {
  91.                 cx[x[i]] = 1;
  92.                 xl.push_back(x[i]);
  93.             }
  95.             if (!cx[y[i]])
  96.             {
  97.                 cx[y[i]] = 1;
  98.                 xl.push_back(y[i]);
  99.             }
  100.         }
  102.         sort(xl.begin(),xl.end());
  104.         int len = xl.size();
  106.         for (int i = 1;i < len;++i)
  107.         {
  108.             if (xl[i] - xl[i-1] > 1)
  109.                 xl.push_back(xl[i] - 1);
  110.         }
  112.         sort(xl.begin(),xl.end());
  114.         len = xl.size();
  116.         for (int i = 0;i < len;i++)
  117.         {
  118.             a[xl[i]] = i+1;
  119.         }
  121.         for (int i = 1;i <= n;i++)
  122.         {
  123.             x[i] = a[x[i]];
  124.             y[i] = a[y[i]];
  125.         }
  128.         for (int i = 1;i <= n;i++)
  129.         {
  130.             update(1,len,i,x[i],y[i],1);
  131.         }
  133.         int sum = 0;
  135.         query(1,len,1);
  137.         for (int i = 1;i <= n;i++)
  138.         {
  139.             if (ans[i]) sum++;
  140.         }
  142.         printf("%d\n",sum);
  143.     }
  145.     return 0;
  146. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注