[关闭]
@TryMyEdge 2017-02-11T14:31:08.000000Z 字数 9440 阅读 816

专题二(线段树)

题解

题目

A 敌兵布阵

题目大意：

    有N(0<N<=50000)个营地，第i个营地中有ai（1<=ai<=50）个士兵。
    有四种命令：
    (1)Add i j，表示第i个营地增加j个人
    (2)Sub i j，表示第i个营地减少j个人
    (3)Query i j，表示询问第i到第j个营地的总人数
    (4)End 表示当前数据结束
    一组数据最多有40000条命令。
    T组数据。

解题思路：

    线段树裸题。
    单点更新，维护区间和。
    时间复杂度o(T*40000*log(N))，空间复杂度o(N)。

AC代码：

  1. **#include<iostream>
  2. #include<bits/stdc++.h>
  3. #define pq priority_queue
  4. #define Pi acos(-1.0)
  5. using namespace std;
  6. struct Node
  7. {
  8.     int l,r,mid,sum;
  9. }tre[200005];
  10. int n,num[50005];
  11. int build(int l,int r,int x)
  12. {
  13.     tre[x].l=l;
  14.     tre[x].r=r;
  15.     tre[x].mid=(l+r)/2;
  16.     if(l==r)
  17.         return tre[x].sum=num[l];
  18.     else
  19.         return tre[x].sum=build(l,tre[x].mid,x*2)+build(tre[x].mid+1,r,x*2+1);
  20. }
  21. int ask(int l,int r,int x)
  22. {
  23.     if(l==tre[x].l && r==tre[x].r)
  24.         return tre[x].sum;
  25.     else
  26.     {
  27.         if(l<=tre[x].mid && r>tre[x].mid)
  28.             return ask(l,tre[x].mid,x*2)+ask(tre[x].mid+1,r,x*2+1);
  29.         else
  30.         {
  31.             if(r<=tre[x].mid)
  32.                 return ask(l,r,x*2);
  33.             else
  34.                 return ask(l,r,x*2+1);
  35.         }
  36.     }
  37. }
  38. void add(int now,int nums,int x)
  39. {
  40.     tre[x].sum+=nums;
  41.     if(tre[x].l!=tre[x].r)
  42.     {
  43.         if(now<=tre[x].mid)
  44.             add(now,nums,x*2);
  45.         else
  46.             add(now,nums,x*2+1);
  47.     }
  48. }
  49. int main()
  50. {
  51.     int T,a,b;
  52.     char s[6];
  53.     cin>>T;
  54.     for(int t=1;t<=T;t++)
  55.     {
  56.         scanf("%d",&n);
  57.         for(int i=1;i<=n;i++)
  58.             scanf("%d",num+i);
  59.         build(1,n,1);
  60.         printf("Case %d:\n",t);
  61.         while(scanf("%s",s),s[0]!='E')
  62.         {
  63.             scanf("%d%d",&a,&b);
  64.             if(s[0]=='Q')
  65.                 printf("%d\n",ask(a,b,1));
  66.             if(s[0]=='A')
  67.                 add(a,b,1);
  68.             if(s[0]=='S')
  69.                 add(a,-b,1);
  70.         }
  71.     }
  72.     return 0;
  73. }**

B Color the ball

题目大意：

    有N(N<=100000)个气球，进行N次涂色，每次涂色可以指定一段任意数目的连续的气球，问最后每个气球被涂过多少次颜色。
    多组数据。

解题思路：

    线段树维护被涂色的次数。
    查询的时候把路径上的染色数都加起来。
    时间复杂度o(N*log(N))，空间复杂度o(N)。

AC代码：

  1. #include<iostream>
  2. #include<bits/stdc++.h>
  3. #define pq priority_queue
  4. #define Pi acos(-1.0)
  5. using namespace std;
  6. struct Node
  7. {
  8.     int l,r,mid,num;
  9. }tre[400005];
  10. int n,temp;
  11. void build(int l,int r,int x)
  12. {
  13.     tre[x].l=l;
  14.     tre[x].r=r;
  15.     tre[x].mid=(l+r)/2;
  16.     tre[x].num=0;
  17.     if(l!=r)
  18.     {
  19.         build(l,tre[x].mid,x*2);
  20.         build(tre[x].mid+1,r,x*2+1);
  21.     }
  22. }
  23. void ask(int now,int x)
  24. {
  25.     temp+=tre[x].num;
  26.     if(tre[x].l!=tre[x].r)
  27.     {
  28.         if(now<=tre[x].mid)
  29.             ask(now,x*2);
  30.         else
  31.             ask(now,x*2+1);
  32.     }
  33. }
  34. void add(int l,int r,int x)
  35. {
  36.     if(tre[x].l==l && r==tre[x].r)
  37.         tre[x].num++;
  38.     else
  39.     {
  40.         if(l<=tre[x].mid && r>tre[x].mid)
  41.         {
  42.             add(l,tre[x].mid,x*2);
  43.             add(tre[x].mid+1,r,x*2+1);
  44.         }
  45.         else
  46.         {
  47.             if(r<=tre[x].mid)
  48.                 return add(l,r,x*2);
  49.             else
  50.                 return add(l,r,x*2+1);
  51.         }
  52.     }
  53. }
  54. int main()
  55. {
  56.     int a,b;
  57.     while(scanf("%d",&n),n)
  58.     {
  59.         build(1,n,1);
  60.         for(int i=0;i<n;i++)
  61.         {
  62.             scanf("%d%d",&a,&b);
  63.             add(a,b,1);
  64.         }
  65.         for(int i=1;i<=n;i++)
  66.         {
  67.             if(i-1)
  68.                 printf(" ");
  69.             temp=0;
  70.             ask(i,1);
  71.             printf("%d",temp);
  72.         }
  73.         printf("\n");
  74.     }
  75.     return 0;
  76. }

C Mayor's posters

题目大意：

    有N(1<=N<=10000)张海报，按给出的顺序依次贴在一面墙上，海报的高度相同，第i张海报的左右端点为li和ri(1<=li<=ri<=10^7)，问最终能看到几张不同的海报。
    T组数据。

解题思路：

    10^7*log(10^7)而且是多组(而且是poj23333)，时间复杂度BOOM！
    所以要将点坐标离散化。再用线段树维护当前的海报编号，最后扫一遍整颗线段树看一下哪些编号还在树上。
    小细节：两个点之间的一段没有点的区间，也要离散化成为一个点。
    时间复杂度o(T*N*log(N))，空间复杂度o(N)。

AC代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. #define pq priority_queue
  6. #define Pi acos(-1.0)
  7. using namespace std;
  8. struct Node
  9. {
  10.     int l,r,mid,color;
  11. }tre[200005];
  12. int n;
  13. struct Post
  14. {
  15.     int num,no;
  16. }c[20005];
  17. bool life[10005];
  18. int col[40005];
  19. bool cmp1(Post a,Post b)
  20. {
  21.     if(a.num==b.num)
  22.         return a.no<b.no;
  23.     else
  24.         return a.num<b.num;
  25. }
  26. bool cmp2(Post a,Post b)
  27. {
  28.     return a.no<b.no;
  29. }
  30. void build(int l,int r,int x)
  31. {
  32.     tre[x].l=l;
  33.     tre[x].r=r;
  34.     tre[x].mid=(l+r)/2;
  35.     tre[x].color=0;
  36.     if(l!=r)
  37.     {
  38.         build(l,tre[x].mid,x*2);
  39.         build(tre[x].mid+1,r,x*2+1);
  40.     }
  41. }
  42. void ok(int l,int r,int color,int x)
  43. {
  44.     if(tre[x].l==l && r==tre[x].r)
  45.         tre[x].color=color;
  46.     else
  47.     {
  48.         if(tre[x].color)
  49.         {
  50.             ok(tre[x].l,tre[x].mid,tre[x].color,x*2);
  51.             ok(tre[x].mid+1,tre[x].r,tre[x].color,x*2+1);
  52.             tre[x].color=0;
  53.         }
  54.         if(l<=tre[x].mid && r>tre[x].mid)
  55.         {
  56.             ok(l,tre[x].mid,color,x*2);
  57.             ok(tre[x].mid+1,r,color,x*2+1);
  58.         }
  59.         else
  60.         {
  61.             if(r<=tre[x].mid)
  62.                 return ok(l,r,color,x*2);
  63.             else
  64.                 return ok(l,r,color,x*2+1);
  65.         }
  66.     }
  67. }
  68. void rebuild(int x)
  69. {
  70.     if(tre[x].color)
  71.     {
  72.         for(int i=tre[x].l;i<=tre[x].r;i++)
  73.             col[i]=tre[x].color;
  74.     }
  75.     else
  76.     {
  77.         if(tre[x].l==tre[x].r)
  78.             return;
  79.         rebuild(x*2);
  80.         rebuild(x*2+1);
  81.     }
  82. }
  83. int main()
  84. {
  85.     int T,m,ans;
  86.     int cnt,gg;
  87.     cin>>T;
  88.     while(T--)
  89.     {
  90.         scanf("%d",&m);
  91.         n=0;
  92.         for(int i=0;i<m;i++)
  93.         {
  94.             scanf("%d%d",&(c[i*2].num),&(c[i*2+1].num));
  95.             c[i*2].no=i*2;
  96.             c[i*2+1].no=i*2+1;
  97.         }
  98.         sort(c,c+m*2,cmp1);
  99.         cnt=1;
  100.         gg=c[0].num;
  101.         c[0].num=1;
  102.         for(int i=1;i<2*m;i++)
  103.         {
  104.             cnt+=(c[i].num>gg);
  105.             cnt+=(c[i].num>gg+1);
  106.             gg=c[i].num;
  107.             c[i].num=cnt;
  108.         }
  109.         sort(c,c+m*2,cmp2);
  110.         build(1,cnt,1);
  111.         for(int i=0;i<m;i++)
  112.         {
  113.             ok(c[i*2].num,c[i*2+1].num,i+1,1);
  114.         }
  115.         memset(life,0,sizeof(life));
  116.         ans=0;
  117.         rebuild(1);
  118.         life[0]=1;
  119.         for(int i=1;i<=cnt;i++)
  120.         {
  121.             if(!life[col[i]])
  122.             {
  123.                 ans++;
  124.                 life[col[i]]=1;
  125.             }
  126.         }
  127.         printf("%d\n",ans);
  128.     }
  129.     return 0;
  130. }

D Tunnel Warfare

题目大意：

    有N(N<=50000)个村庄，M(M<=50000)个事件。
    事件分为三种：
    (1)D x，表示摧毁x号村庄
    (2)Q x，表示询问x所在的连续的完好村庄段的长度
    (3)R，表示修复当前最后被摧毁的那个村庄
    多组数据。

解题思路：

    用一个栈维护已经摧毁的村庄，可以知道每次要恢复哪个村庄。
    线段树维护左起连续完好村庄段的长度和右起连续完好村庄段的长度。
    询问的时候如果中间的连续完好村庄段包含询问的点，则返回这一段的长度，否则继续向下询问。
    小细节：多组数据题目没说清楚挺坑的。。。还有似乎会出现重复摧毁已经摧毁过的村庄或者重复恢复当前完好的村庄的情况。
    时间复杂度o(M*log(N))，空间复杂度o(N)。

AC代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #define pq priority_queue
  4. #define Pi acos(-1.0)
  5. using namespace std;
  6. struct Node
  7. {
  8.     int l,r,mid;
  9.     int lans,rans;
  10. }tre[200005];
  11. int n,m;
  12. bool life[50005];
  13. void build(int l,int r,int x)
  14. {
  15.     tre[x].l=l;
  16.     tre[x].r=r;
  17.     tre[x].mid=(l+r)/2;
  18.     tre[x].lans=tre[x].rans=r-l+1;
  19.     if(l!=r)
  20.     {
  21.         build(l,tre[x].mid,x*2);
  22.         build(tre[x].mid+1,r,x*2+1);
  23.     }
  24. }
  25. void change(int now,int flag,int x)
  26. {
  27.     if(tre[x].l==tre[x].r)
  28.         tre[x].lans=tre[x].rans=flag;
  29.     else
  30.     {
  31.         if(now<=tre[x].mid)
  32.             change(now,flag,x*2);
  33.         else
  34.             change(now,flag,x*2+1);
  35.         if(tre[x*2].lans==tre[x*2].r-tre[x*2].l+1)
  36.             tre[x].lans=tre[x*2].lans+tre[x*2+1].lans;
  37.         else
  38.             tre[x].lans=tre[x*2].lans;
  39.         if(tre[x*2+1].rans==tre[x*2+1].r-tre[x*2+1].l+1)
  40.             tre[x].rans=tre[x*2+1].rans+tre[x*2].rans;
  41.         else
  42.             tre[x].rans=tre[x*2+1].rans;
  43.     }
  44. }
  45. int ask(int now,int x)
  46. {
  47.     if(now<=tre[x].mid)
  48.     {
  49.         if(tre[x].mid-tre[x*2].rans<now)
  50.             return tre[x*2].rans+tre[x*2+1].lans;
  51.         else
  52.             return ask(now,x*2);
  53.     }
  54.     else
  55.     {
  56.         if(tre[x].mid+tre[x*2+1].lans>=now)
  57.             return tre[x*2].rans+tre[x*2+1].lans;
  58.         else
  59.             return ask(now,x*2+1);
  60.     }
  61. }
  62. int st[50005],cnt;
  63. int main()
  64. {
  65.     while(cin>>n>>m)
  66.     {
  67.         build(1,n,1);
  68.         char s[6];
  69.         int x;
  70.         cnt=0;
  71.         memset(life,0,sizeof(life));
  72.         while(m--)
  73.         {
  74.             scanf("%s",s);
  75.             if(s[0]=='D')
  76.             {
  77.                 scanf("%d",&x);
  78.                 st[cnt++]=x;
  79.                 change(x,0,1);
  80.                 life[x]=1;
  81.             }
  82.             if(s[0]=='R')
  83.             {
  84.                 cnt--;
  85.                 x=st[cnt];
  86.                 change(x,1,1);
  87.                 life[x]=0;
  88.             }
  89.             if(s[0]=='Q')
  90.             {
  91.                 scanf("%d",&x);
  92.                 if(life[x])
  93.                     printf("0\n");
  94.                 else
  95.                     printf("%d\n",ask(x,1));
  96.             }
  97.         }
  98.     }
  99.     return 0;
  100. }

E A Simple Problem with Integers

题目大意：

    有N(1<=N<=10^5)个数，第i个数为Ai(-10^9<=Ai<=10^9)，Q个(1<=Q<=10^5)操作。
    操作分为两种：
    (1)C a b c，表示第a个到第b个数全部加上c(-10^4<=c<=10^4)
    (2)Q a b，表示询问第a个数到b个数的和

解题思路：

    线段树维护区间和，用lazy标记来优化区间操作。
    小细节：注意爆int的问题。
    时间复杂度o(Q*log(N))，空间复杂度o(N)。

AC代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #define pq priority_queue
  4. #define Pi acos(-1.0)
  5. using namespace std;
  6. struct Node
  7. {
  8.     int l,r,mid;
  9.     long long sum,lazy;
  10. }tre[400005];
  11. int n;
  12. int num[100005];
  13. long long build(int l,int r,int x)
  14. {
  15.     tre[x].l=l;
  16.     tre[x].r=r;
  17.     tre[x].mid=(l+r)/2;
  18.     tre[x].lazy=0;
  19.     if(l!=r)
  20.         return tre[x].sum=build(l,tre[x].mid,x*2)+build(tre[x].mid+1,r,x*2+1);
  21.     else
  22.         return tre[x].sum=num[l];
  23. }
  24. void add(int l,int r,long long nums,int x)
  25. {
  26.     tre[x].sum+=nums*(r-l+1);
  27.     if(tre[x].l==l && r==tre[x].r)
  28.         tre[x].lazy+=nums;
  29.     else
  30.     {
  31.         add(tre[x].l,tre[x].mid,tre[x].lazy,x*2);
  32.         add(tre[x].mid+1,tre[x].r,tre[x].lazy,x*2+1);
  33.         tre[x].lazy=0;
  34.         if(l<=tre[x].mid && r>tre[x].mid)
  35.         {
  36.             add(l,tre[x].mid,nums,x*2);
  37.             add(tre[x].mid+1,r,nums,x*2+1);
  38.         }
  39.         else
  40.         {
  41.             if(r<=tre[x].mid)
  42.                 add(l,r,nums,x*2);
  43.             else
  44.                 add(l,r,nums,x*2+1);
  45.         }
  46.     }
  47. }
  48. long long ask(int l,int r,int x)
  49. {
  50.     if(l==tre[x].l && r==tre[x].r)
  51.         return tre[x].sum;
  52.     else
  53.     {
  54.         add(tre[x].l,tre[x].mid,tre[x].lazy,x*2);
  55.         add(tre[x].mid+1,tre[x].r,tre[x].lazy,x*2+1);
  56.         tre[x].lazy=0;
  57.         if(l<=tre[x].mid && r>tre[x].mid)
  58.             return ask(l,tre[x].mid,x*2)+ask(tre[x].mid+1,r,x*2+1);
  59.         else
  60.         {
  61.             if(r<=tre[x].mid)
  62.                 return ask(l,r,x*2);
  63.             else
  64.                 return ask(l,r,x*2+1);
  65.         }
  66.     }
  67. }
  68. int main()
  69. {
  70.     int q,a,b;
  71.     int c;
  72.     char s[6];
  73.     cin>>n>>q;
  74.     for(int i=1;i<=n;i++)
  75.         scanf("%d",num+i);
  76.     build(1,n,1);
  77.     while(q--)
  78.     {
  79.         scanf("%s",s);
  80.         if(s[0]=='C')
  81.         {
  82.             scanf("%d%d%d",&a,&b,&c);
  83.             add(a,b,c,1);
  84.         }
  85.         else
  86.         {
  87.             scanf("%d%d",&a,&b);
  88.             printf("%lld\n",ask(a,b,1));
  89.         }
  90.     }
  91.     return 0;
  92. }

F Sasha and Array

题目大意：

    有N(1<=N<=10^5)个数，第i个数为ai(1<=ai<=10^9)，Q个(1<=Q<=10^5)操作。
    操作分为两种：
    (1)1 l r x，表示第l个到第r个数全部加上x(1<=x<=10^9)
    (2)2 l r，表示询问第l个数到r个数对应的f(ai)的和，f(ai)表示斐波那契的第ai项，f(1)=f(2)=1
    输出取模10^9+7。

解题思路：

    乍看之下题意的描述和E几乎一模一样，事实上最终的代码也很相似(强行
    斐波那契函数可以由原始向量通过不断左乘转移矩阵x-1次来得到表示第x项的向量，由于原始向量是固定的，于是斐波那契函数的第x项可以用转移矩阵的x-1次方来表示。因为x可能非常大所以要到用矩阵快速幂。几个项斐波那契数的相加则可以用矩阵的相加来实现。于是定义完关于矩阵的一系列操作，我们就可以很容易的把E题的代码转化为F题的代码，其中sum和lazy都是矩阵类型的。
    小细节：注意f(x)是用矩阵的x-1次方来表示的。注意处理好取模，爆int。
    时间复杂度o(Q*log(N)*log(x))，空间复杂度o(N)。

AC代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #define pq priority_queue
  4. #define Pi acos(-1.0)
  5. using namespace std;
  6. #define MOD 1000000007
  7. struct JZ
  8. {
  9.     long long a,b,c,d;
  10.     friend JZ operator *(JZ x1,JZ x2)
  11.     {
  12.         JZ x3;
  13.         x3.a=(x1.a*x2.a+x1.b*x2.c)%MOD;
  14.         x3.b=(x1.a*x2.b+x1.b*x2.d)%MOD;
  15.         x3.c=(x1.c*x2.a+x1.d*x2.c)%MOD;
  16.         x3.d=(x1.c*x2.b+x1.d*x2.d)%MOD;
  17.         return x3;
  18.     }
  19.     friend JZ operator +(JZ x1,JZ x2)
  20.     {
  21.         JZ x3;
  22.         x3.a=(x1.a+x2.a)%MOD;
  23.         x3.b=(x1.b+x2.b)%MOD;
  24.         x3.c=(x1.c+x2.c)%MOD;
  25.         x3.d=(x1.d+x2.d)%MOD;
  26.         return x3;
  27.     }
  28. }A,E;
  29. JZ Pows(int x)
  30. {
  31.     JZ X=E,Y=A;
  32.     while(x)
  33.     {
  34.         if(x%2)
  35.             X=Y*X;
  36.         Y=Y*Y;
  37.         x/=2;
  38.     }
  39.     return X;
  40. }
  41. struct Node
  42. {
  43.     int l,r,mid;
  44.     JZ sum,lazy;
  45. }tre[400005];
  46. int n;
  47. int num[100005];
  48. JZ build(int l,int r,int x)
  49. {
  50.     tre[x].l=l;
  51.     tre[x].r=r;
  52.     tre[x].mid=(l+r)/2;
  53.     tre[x].lazy=E;
  54.     if(l!=r)
  55.         return tre[x].sum=build(l,tre[x].mid,x*2)+build(tre[x].mid+1,r,x*2+1);
  56.     else
  57.         return tre[x].sum=Pows(num[l]-1);
  58. }
  59. void add(int l,int r,JZ nums,int x)
  60. {
  61.     if(tre[x].l==l && r==tre[x].r)
  62.     {
  63.         tre[x].sum=nums*tre[x].sum;
  64.         tre[x].lazy=nums*tre[x].lazy;
  65.     }
  66.     else
  67.     {
  68.         add(tre[x].l,tre[x].mid,tre[x].lazy,x*2);
  69.         add(tre[x].mid+1,tre[x].r,tre[x].lazy,x*2+1);
  70.         tre[x].lazy=E;
  71.         if(l<=tre[x].mid && r>tre[x].mid)
  72.         {
  73.             add(l,tre[x].mid,nums,x*2);
  74.             add(tre[x].mid+1,r,nums,x*2+1);
  75.         }
  76.         else
  77.         {
  78.             if(r<=tre[x].mid)
  79.                 add(l,r,nums,x*2);
  80.             else
  81.                 add(l,r,nums,x*2+1);
  82.         }
  83.         tre[x].sum=tre[x*2].sum+tre[x*2+1].sum;
  84.     }
  85. }
  86. JZ ask(int l,int r,int x)
  87. {
  88.     if(l==tre[x].l && r==tre[x].r)
  89.         return tre[x].sum;
  90.     else
  91.     {
  92.         add(tre[x].l,tre[x].mid,tre[x].lazy,x*2);
  93.         add(tre[x].mid+1,tre[x].r,tre[x].lazy,x*2+1);
  94.         tre[x].lazy=E;
  95.         if(l<=tre[x].mid && r>tre[x].mid)
  96.             return ask(l,tre[x].mid,x*2)+ask(tre[x].mid+1,r,x*2+1);
  97.         else
  98.         {
  99.             if(r<=tre[x].mid)
  100.                 return ask(l,r,x*2);
  101.             else
  102.                 return ask(l,r,x*2+1);
  103.         }
  104.     }
  105. }
  106. int main()
  107. {
  108.     E.b=E.c=A.d=0;
  109.     E.a=E.d=A.a=A.b=A.c=1;
  110.     int q,a,b,c,s;
  111.     cin>>n>>q;
  112.     for(int i=1;i<=n;i++)
  113.         scanf("%d",num+i);
  114.     build(1,n,1);
  115.     while(q--)
  116.     {
  117.         scanf("%d",&s);
  118.         if(s==1)
  119.         {
  120.             scanf("%d%d%d",&a,&b,&c);
  121.             add(a,b,Pows(c),1);
  122.         }
  123.         else
  124.         {
  125.             scanf("%d%d",&a,&b);
  126.             printf("%lld\n",(ask(a,b,1)).a);
  127.         }
  128.     }
  129.     return 0;
  130. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注