[关闭]
@wwwqeqeqeqe 2019-06-17T16:39:57.000000Z 字数 6379 阅读 678

线段树题目讲解（2019.6.18）

线段树

A Ultra-QuickSort (POJ 2299)

题目大意：

给你n个乱序的数字，求出如果使用冒泡排序所需要交换的次数。（n≤500000）

解题思路：

最初，给每个节点赋值为1建立一棵线段树，对原数组进行排序，得到排序完成后每个数字在原数组的下标。再对这些下标进行操作，查找所有[1,index[i]）之间有多少个1，这些1的个数就是我当前数字进行冒泡排序移动到对应位置所需要的移动的次数，ans加上这个数需要移动的步数后，删除这个数，并对线段树进行操作。最后，将所有的数全部跑完一遍之后，得到答案。

AC代码：

线段树：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<cmath>
  6. using namespace std;
  8. const int maxn=5e5+5;
  10. int Tree[maxn<<2], index[maxn], num[maxn];
  11. int n;
  13. int cmp(const int i, const int j)
  14. {
  15.     return num[i] < num[j];
  16. }
  18. void Edit(int k, int l, int r, int num, int value)
  19. {
  20.     Tree[k] += value;
  21.     if(r==l) return ;
  22.     int mid = (l+r) >> 1;
  23.     if(num <= mid) Edit(k<<1, l, mid, num, value);
  24.     else Edit(k<<1|1, mid+1, r, num, value);
  25. }
  27. int Search(int k, int l, int r, int L, int R)
  28. {
  29.     if(L<=l && r<=R) return Tree[k];
  30.     int mid = (l+r) >> 1;
  31.     int ans = 0;
  32.     if(L <= mid) ans += Search(k<<1, l, mid, L, R);
  33.     if(R > mid) ans += Search(k<<1|1, mid+1, r, L, R);
  34.     return ans;
  35. }
  37. int main()
  38. {
  39.     while(~scanf("%d", &n) && n)
  40.     {
  41.         memset(Tree,0,sizeof(Tree));
  42.         memset(num,0,sizeof(num));
  43.         memset(index,0,sizeof(index));
  44.         for(int i=1; i<=n; i++)
  45.         {
  46.             scanf("%d", &num[i]);
  47.             Edit(1, 1, n, i, 1);
  48.             index[i] = i;
  49.         }
  50.         sort(index+1, index+n+1,cmp);
  51.         long long ans = 0;
  52.         for(int i=1; i<=n; i++)
  53.         {
  54.             ans += (Search(1, 1, n, 1, index[i])-1);
  55.             Edit(1, 1, n, index[i], -1);
  56.         }
  57.         printf("%lld\n", ans);
  58.     }
  59.     return 0;
  60. }

树状数组：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<cmath>
  6. using namespace std;
  8. const int maxn=5e5+5;
  10. int a[maxn],vis[maxn],n;
  12. struct node
  13. {
  14.     int mark,val;
  15. };
  17. node aa[maxn];
  19. bool cmp(node x,node y)
  20. {
  21.     return x.val<y.val;
  22. }
  24. int lowbit(int x)
  25. {
  26.     return x&(-x);
  27. }
  29. void update(int x,int val)
  30. {
  31.     while(x<=n)
  32.     {
  33.         vis[x]+=val;
  34.         x+=lowbit(x);
  35.     }
  36. }
  38. long long sum(int x)
  39. {
  40.     long long an=0;
  41.     while(x>=1)
  42.     {
  43.         an+=vis[x];
  44.         x-=lowbit(x);
  45.     }
  46.     return an;
  47. }
  49. int main()
  50. {
  51.     while(cin >> n && n)
  52.     {
  53.         for(int i=1; i<=n; i++)
  54.         {
  55.             cin >> aa[i].val;
  56.             aa[i].mark=i;
  57.         }
  58.         sort(aa+1,aa+n+1,cmp);
  59.         for(int i=1;i<=n;i++)
  60.         {
  61.             a[aa[i].mark]=i;
  62.         }
  63.         long long ans=0;
  64.         memset(vis,0,sizeof(vis));
  65.         for(int i=1;i<=n;i++)
  66.         {
  67.             update(a[i],1);
  68.             ans+=i-sum(a[i]);
  69.         }
  70.         cout << ans << endl;
  71.     }
  72.     return 0;
  73. }

B Stars (POJ 2352)
题目大意：

给出n个点，表示有n颗星星，以这个点为起点向x，y轴作垂直线，与坐标轴围成一个矩形，矩形内的所有星星的数量（不包含自己）就是这个星星的level。题目按照y轴坐标升序，如果y轴坐标相同，按照x轴坐标升序给出所有的星星，输出所有level从0~n-1各个等级有多少颗星星。

解题思路：

因为输入是按照先y轴再x轴递增的顺序给出的，因此，对于第i颗星星，它的level就是之前出现过的星星中，x小于等于它的所有星星的总数（因为前面出现过的y一定小于后面出现的星星的y值）。
因此，我们需要建立一棵树，用于记录所有星星的x值，方便求出所有x值小于等于当前星星x值。

AC代码：

线段树：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<cmath>
  6. using namespace std;
  8. const int maxn=32000+5;
  10. int sum[maxn<<2],level[maxn<<2];
  12. void update(int k,int l,int r,int data)
  13. {
  14.     sum[k]++;
  15.     if(l==r) return;
  16.     int mid=(l+r)>>1;
  17.     if(data <= mid) update(k<<1, l, mid, data);
  18.     else update(k<<1|1, mid+1, r, data);
  19. }
  21. int query(int k,int l,int r,int ll,int rr)
  22. {
  23.     if(l==ll && r==rr)
  24.     {
  25.         return sum[k];
  26.     }
  27.     int mid = (l+r)>>1;
  28.     if(rr <= mid) return query(k<<1, l, mid,ll,rr);
  29.     else if(ll > mid) return query(k<<1|1, mid+1, r,ll,rr);
  30.     else return query(k<<1, l, mid,ll,mid)+query(k<<1|1, mid+1, r,mid+1,rr);
  31. }
  33. int main()
  34. {
  35.     int n,x,y;
  36.     while(~scanf("%d",&n))
  37.     {
  38.         memset(sum, 0, sizeof(sum));
  39.         memset(level, 0, sizeof(level));
  40.         for(int i=0; i<n; ++i)
  41.         {
  42.             scanf("%d%d",&x,&y);
  43.             x++;
  44.             level[query(1,1,maxn,1,x)]++;
  45.             update(1,1,maxn,x);
  46.         }
  47.         for(int i=0; i<n; ++i)
  48.             printf("%d\n",level[i]);
  49.     }
  50.     return 0;
  51. }

树状数组：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<cmath>
  6. using namespace std;
  8. const int maxn=32005;
  10. int c[maxn];
  11. int mark[maxn];
  12. int n;
  13. int x,y;
  15. int lowbit(int x)
  16. {
  17.     return x&(-x);
  18. }
  20. void update(int x,int val)
  21. {
  22.     while(x<maxn)
  23.     {
  24.         c[x]+=val;
  25.         x+=lowbit(x);
  26.     }
  27. }
  29. int sum(int x)
  30. {
  31.     int ans=0;
  32.     while(x>=1)
  33.     {
  34.         ans+=c[x];
  35.         x-=lowbit(x);
  36.     }
  37.     return ans;
  38. }
  40. int main()
  41. {
  42.     cin >> n;
  43.     memset(mark,0,sizeof(mark));
  44.     memset(c,0,sizeof(c));
  45.     for(int i=0;i<n;i++)
  46.     {
  47.         cin >> x >> y;
  48.         int t=sum(x+1);
  49.         mark[t]++;
  50.         update(x+1,1);
  51.     }
  52.     for(int i=0;i<n;i++)
  53.         cout << mark[i] << endl;
  54.     return 0;
  55. }

C Mayor's posters (POJ 2528)
题目大意：

题目给出一堵墙，有n个人(1≤n≤10000)，每个人依次贴一张海报，每张海报的范围为li到ri（1≤li≤ri≤10000000），求最后能看见多少张海报。

解题思路：

由于题目数据范围很大，但是人的个数很少，因此，我们需要对数据进行离散化，将题目给出的范围按照相互位置进行离散化，将数据范围缩小。数据范围缩小后，将变化后的数据插入线段树中，由于我们需要的是相关的覆盖信息，且是后面的覆盖前面的，因此，只需要将数组从尾到头进行计算即可，每次计算判断是否存在没有被覆盖的范围，如果有，ans++。

AC代码：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<cmath>
  6. using namespace std;
  8. const int maxn = 20000 + 5;
  10. int pl[maxn], pr[maxn], n;
  11. int s[maxn*4], e[maxn*4];
  12. bool covered[maxn*4];
  13. int port[maxn], cnt;
  14. int id[10000000+5];
  16. void build_tree(int l, int r, int rt)
  17. {
  18.     s[rt] = l;
  19.     e[rt] = r;
  20.     covered[rt] = false;
  21.     int mid=(l+r)>>1;
  22.     if(l != r)
  23.     {
  24.         build_tree(l, mid, rt << 1);
  25.         build_tree(mid + 1, r, rt << 1 | 1);
  26.     }
  27. }
  29. bool post(int l, int r, int rt)
  30. {
  31.     if(covered[rt] == true)
  32.         return false;
  33.     if(s[rt] == l && e[rt] == r)
  34.     {
  35.         covered[rt] = true;
  36.         return true;
  37.     }
  38.     bool res;
  39.     int mid=(s[rt]+e[rt])>>1;
  40.     if(r <= mid)
  41.         res = post(l, r, rt << 1);
  42.     else if(l > mid)
  43.         res = post(l, r, rt << 1 | 1);
  44.     else
  45.     {
  46.         bool res1 = post(l, mid, rt << 1);
  47.         bool res2 = post(mid + 1, r, rt << 1 | 1);
  48.         res = res1 || res2;
  49.     }
  50.     if(covered[rt << 1] && covered[rt << 1 | 1])
  51.         covered[rt] = true;
  52.     return res;
  53. }
  55. int main()
  56. {
  57.     int T;
  58.     scanf("%d", &T);
  59.     while(T--)
  60.     {
  61.         scanf("%d", &n);
  62.         cnt = 0;
  63.         for(int i = 0; i < n; i++)
  64.         {
  65.             scanf("%d%d", &pl[i], &pr[i]);
  66.             port[cnt++] = pl[i];
  67.             port[cnt++] = pr[i];
  68.         }
  70.         sort(port, port + cnt);
  71.         cnt = unique(port, port + cnt) - port;
  72.         build_tree(1, cnt, 1);
  74.         for(int i = 0; i < cnt; i++)    id[port[i]] = i + 1;
  76.         int res = 0;
  77.         for(int i = n-1; i >= 0; i--)
  78.         {
  79.             if(post(id[pl[i]], id[pr[i]], 1))
  80.             {
  81.                 res++;
  82.             }
  83.         }
  84.         printf("%d\n", res);
  85.     }
  86.     return 0;
  87. }

D Count Color （POJ 2777）
题目大意：

给出一块长度为L的颜色板，将它均匀地划分为L块长度为1的小方格，从左到右标记为1、2、3、···、L。现在对这个颜色板对这个颜色板进行两种操作，第一种输入C A B C，表示在A到B这些方格中涂上颜色C，第二种输入P A B，表示查询[A,B]上所有的颜色种数。题目一共有T种颜料（1≤T≤30），分别称为颜色1，颜色2···颜色T，开始时，板子上涂有颜色1。

解题思路：

建立一棵带有lazy标记的线段树，因为最初始的状态，所有的板子都是颜色1，所以所有的标记都标记为1，在进行区间修改的过程中，如果查找的整个区间都只有一种颜色，那么，这个区间的标记就为该颜色的种类，否则，将标记传递给子节点，并取消当前节点的lazy标记。查询时，只需要查询到还有lazy标记的位置就可以了。

AC代码：

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. #include<cmath>
  6. using namespace std;
  8. struct node
  9. {
  10.     int l,r;
  11.     int num;
  12. } s[400010];
  14. int vis[35];
  16. void InitTree(int l,int r,int k)
  17. {
  18.     s[k].l=l;
  19.     s[k].r=r;
  20.     s[k].num=1;
  21.     int mid=(l+r)/2;
  22.     if (l==r)
  23.         return ;
  24.     InitTree(l,mid,2*k);
  25.     InitTree(mid+1,r,2*k+1);
  26. }
  28. void UpdataTree(int l,int r,int c,int k)
  29. {
  30.     if(s[k].l==l&&s[k].r==r)
  31.     {
  32.         s[k].num=c;
  33.         return;
  34.     }
  35.     if (s[k].num==c)
  36.         return;
  37.     if (s[k].num!=-1)//如果所查询的区间不是多种颜色
  38.     {
  39.         s[2*k].num=s[k].num;//更新区间的颜色
  40.         s[2*k+1].num=s[k].num;
  41.         s[k].num=-1;//-1表示该区间有多种颜色
  42.     }
  43.     int mid=(s[k].l+s[k].r)/2;
  44.     if (l>mid)
  45.         UpdataTree(l,r,c,2*k+1);
  46.     else if (r<=mid)
  47.         UpdataTree(l,r,c,2*k);
  48.     else
  49.     {
  50.         UpdataTree(l,mid,c,2*k);
  51.         UpdataTree(mid+1,r,c,2*k+1);
  52.     }
  53. }
  55. void SearchTree(int l,int r,int k)
  56. {
  57.     if (s[k].num!=-1)
  58.     {
  59.         vis[s[k].num]=1;
  60.         return;
  61.     }
  62.     int mid=(s[k].l+s[k].r)/2;
  63.     if (r<=mid)
  64.         SearchTree(l,r,2*k);
  65.     else if (l>mid)
  66.         SearchTree(l,r,2*k+1);
  67.     else
  68.     {
  69.         SearchTree(l,mid,2*k);
  70.         SearchTree(mid+1,r,2*k+1);
  71.     }
  72. }
  74. int main()
  75. {
  76.     int l,t,o,ans;
  77.     while (~scanf("%d%d%d",&l,&t,&o))
  78.     {
  79.         InitTree(1,l,1);
  80.         while (o--)
  81.         {
  82.             char ch;
  83.             int a,b,c;
  84.             getchar();
  85.             scanf("%c",&ch);
  86.             if (ch=='C')
  87.             {
  88.                 scanf("%d%d%d",&a,&b,&c);
  89.                 if (a>b)
  90.                     swap(a,b);
  91.                 UpdataTree(a,b,c,1);
  92.             }
  93.             else
  94.             {
  96.                 scanf("%d%d",&a,&b);
  97.                 if (a>b)
  98.                     swap(a,b);
  99.                 memset(vis,0,sizeof(vis));
  100.                 SearchTree(a,b,1);
  101.                 ans=0;
  102.                 for (int i=1; i<=t; i++)
  103.                     if (vis[i]==1)
  104.                         ans++;
  105.                 printf ("%d\n",ans);
  106.             }
  107.         }
  108.     }
  109.     return 0;
  110. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注