[关闭]
@morehigh 2017-05-20T13:31:52.000000Z 字数 4145 阅读 1040

CQUPT 线段树+st专题 2017/5/8

线段数

A - Hotel POJ - 3667 

  1. 旅馆里面有N(1 ≤ N ≤ 50,000)个房间，有M(1 ≤ M < 50,000)个操作，包含两类
  2. 1操作 需要占用连续的D个房间
  3. 2操作 从第X个房间到第X+D-1个房间被清空
  4. 进行1操作的时候，需要占用D个房间，需要查询输出r，表示从r到r+D的房间是空出来的
  1. 线段数连续区间合并问题，lsum表示从左边端点开始连续的空房间的个数，rsum表示从最右边端点开始向左连续的空房间的个数，msum表示此区间最大连续区间，如果最大的连续区间小于要占用的区间D，则表示不满足条件输出‘0’。col表示lazy数组，如果col为-1表示不存在向下传递数据。pushdown表示向下传递标记，pushup表示向上传递最大父亲区间的最大连续区间。
  1. #include <iostream>
  2. #include <cstring>
  3. #include <cstdio>
  4. #include <algorithm>
  6. using namespace std;
  7. const int maxn=50005;
  8. int lsum[maxn*4], rsum[maxn*4], msum[maxn*4];
  9. int col[maxn*4];
  10. void push_down(int rt,int m)
  11. {
  12.     if(col[rt]!=-1)
  13.     {
  14.         col[rt<<1]=col[rt<<1|1]=col[rt];
  15.         msum[rt<<1]=lsum[rt<<1]=rsum[rt<<1]=col[rt]?0:m-(m>>1);
  16.         msum[rt<<1|1]=lsum[rt<<1|1]=rsum[rt<<1|1]=col[rt]?0:(m>>1);
  17.         col[rt]=-1;
  18.     }
  19. }
  21. void push_up(int rt, int m) {
  22.     lsum[rt]=lsum[rt<<1];
  23.     rsum[rt]=rsum[rt<<1|1];
  24.     if(lsum[rt]==m-(m>>1)) lsum[rt]+=lsum[rt<<1|1];
  25.     if(rsum[rt] == (m>>1)) rsum[rt]+=rsum[rt<<1];
  26.     msum[rt]=max(lsum[rt<<1|1]+rsum[rt<<1], max(msum[rt<<1], msum[rt<<1|1]));
  27. }
  29. void build(int l,int r,int rt)
  30. {
  31.     msum[rt]=lsum[rt]=rsum[rt]=r-l+1;
  32.     col[rt]=-1;
  33.     if(l==r) return ;
  34.     int mid=(l+r)>>1;
  35.     build(l,mid,rt<<1);
  36.     build(mid+1,r,rt<<1|1);
  37. }
  38. void update(int L,int R,int c,int rt,int l,int r)
  39. {
  40.     if(L<=l&&R>=r){
  41.         msum[rt]=lsum[rt]=rsum[rt]=c?0:r-l+1;
  42.         col[rt]=c;
  43.         return ;
  44.     }
  45.     push_down(rt,r-l+1);
  46.     int mid=(l+r)>>1;
  47.     if(L<=mid) update(L,R,c,rt<<1,l,mid);
  48.     if(R>mid) update(L,R,c,rt<<1|1,mid+1,r);
  49.     push_up(rt,r-l+1);
  50. }
  51. int query(int wid, int rt, int l, int r) {
  52.     if(l == r) return l;
  53.     push_down(rt, r - l + 1);
  54.     int mid = (l + r) >> 1;
  55.     if(msum[rt << 1] >= wid) return query(wid, rt<<1,l,mid);
  56.     else if(rsum[rt << 1] + lsum[rt << 1|1] >= wid) return mid - rsum[rt << 1] + 1;
  57.     return query(wid,rt<<1|1,mid+1,r);
  58. }
  59. int main()
  60. {
  61.     int n,m;
  62.     scanf("%d%d",&n,&m);
  63.     build(1,n,1);
  64.     while(m--)
  65.     {
  66.         int x,a,b;
  67.         scanf("%d",&x);
  68.         if(x==1)
  69.         {
  70.             scanf("%d",&a);
  71.             if(msum[1]<a) printf("0\n");
  72.             else{
  73.                 int l=query(a,1,1,n);
  74.                 printf("%d\n",l);
  75.                 update(l,l+a-1,1,1,1,n);
  76.             }
  77.         }else{
  78.             scanf("%d%d",&a,&b);
  79.             update(a,a+b-1,0,1,1,n);
  80.         }
  81.     }
  82.     return 0;
  83. }

B - A Corrupt Mayor's Performance Art HDU - 5023 

  1. 输入两个数据 N 和 M (0 < N <= 1,000,000; 0<M<=100,000)，表示在长度为N的墙壁上进行M个操作，涂颜色，一共有30种颜色，
  2. 1) P a b c  在a到b区间涂上颜色c
  3. 2) Q a b  查询a，b区间一共有几种颜色( 0 < a<=b <= N).
  1. 用到二进制存储压缩记录每个线段数区间所包含的颜色，初始颜色为2，pushdown表示将更新得到的颜色向下传递，更新时将需要更新的颜色存储到add数组中，减少时间复杂度，pushup将子区间更改的颜色传递给父亲节点，其中用到了位运算。
  1. #include <bits/stdc++.h>
  3. using namespace std;
  4. const int N=1100056;
  5. char s[10];
  6. long long sum[N*4],add[N*4];
  8. void pushdown(int rt)
  9. {
  10.     if(add[rt])
  11.     {
  12.         add[rt<<1]=add[rt<<1|1]=add[rt];
  13.         sum[rt<<1]=add[rt];
  14.         sum[rt<<1|1]=add[rt];
  15.         add[rt]=0;
  16.     }
  17. }
  18. void pushup(int rt)
  19. {
  20.     sum[rt]=sum[rt<<1]|sum[rt<<1|1];
  21. }
  22. void build(int rt,int l,int r)
  23. {
  24.     add[rt]=0;
  25.     if(l==r)
  26.     {
  27.        sum[rt]=2;
  28.        return ;
  29.     }
  30.     int mid=(l+r)>>1;
  31.     build(rt<<1,l,mid);
  32.     build(rt<<1|1,mid+1,r);
  33.     pushup(rt);
  34. }
  35. void update(int L,int R,int c,int rt,int l,int r)
  36. {
  37.     if(L<=l&&R>=r)
  38.     {
  39.         add[rt]=1<<(c-1);
  40.         sum[rt]=1<<(c-1);
  41.         return ;
  42.     }
  43.     pushdown(rt);
  44.     int mid=(l+r)>>1;
  45.     if(L<=mid)
  46.         update(L,R,c,rt<<1,l,mid);
  47.     if(R>mid)
  48.         update(L,R,c,rt<<1|1,mid+1,r);
  49.     pushup(rt);
  50. }
  51. long long query(int a,int b,int rt,int l,int r)
  52. {
  53.     if(a<=l&&b>=r)
  54.     {
  55.         return sum[rt];
  56.     }
  57.     pushdown(rt);
  58.     long long ret=0;
  59.     int mid=(l+r)>>1;
  60.     if(a<=mid) ret|=query(a,b,rt<<1,l,mid);
  61.     if(b>mid)  ret|=query(a,b,rt<<1|1,mid+1,r);
  62.     return ret;
  63. }
  64. int main()
  65. {
  66.     int n,m;
  67.     int a,b,c;
  68.     while(~scanf("%d%d",&n,&m))
  69.     {
  70.         if(n==0&&m==0)
  71.         break;
  72.         build(1,1,n);
  73.         while(m--)
  74.         {
  75.             scanf("%s",s);
  76.             if(s[0]=='P')
  77.             {
  78.                 scanf("%d%d%d",&a,&b,&c);
  79.                 update(a,b,c,1,1,n);
  80.             }else{
  81.                 scanf("%d%d",&a,&b);
  82.                 long long t=query(a,b,1,1,n);
  83.                 int flag=0;
  84.                 for(int i=1;i<=30;i++)
  85.                 {
  86.                     if(t>>(i-1)&1 && flag==0)
  87.                     {
  88.                         printf("%d",i);
  89.                         flag = 1;
  90.                     }
  91.                     else if(t>>(i-1)&1)
  92.                         printf(" %d",i);
  93.                 }
  94.                 printf("\n");
  95.             }
  96.         }
  97.     }
  98.     return 0;
  99. }

C - Assignment HDU - 5289 

  1. 一个公司有n个员工，每个员工有一个大小为x能力，老板想把能力差大小不超过k的员工分到一组，求出老板能把员工分成多少组。(1<=n<=100000, 0<k<=10^9)
  1. 用ST做一个预处理，处理得到的数组mx[i][j]表示区间i到i^j中最大的数字。mn[i][j]表示区间i到i^j中最小的数字。然后要用到二分查找，判断i到j区间最大值与最小值差小于k。计算满足条件的区间数。
  1. #include <bits/stdc++.h>
  2. #define N 100005
  3. using namespace std;
  4. int a[N];
  5. int mx[N][21], mn[N][21];
  6. int n, k;
  7. void ST()
  8. {
  9.     for(int j=1;(1<<j)<=n;j++)
  10.     {
  11.         for(int i=1;i+(1<<j)-1<=n;i++)
  12.         {
  13.             int p = 1<<(j - 1);
  14.             mx[i][j]=max(mx[i][j-1],mx[i+p][j-1]);
  15.             mn[i][j]=min(mn[i][j-1],mn[i+p][j-1]);
  16.         }
  17.     }
  18. }
  19. int sol(int x,int y)
  20. {
  21.     int p=log2(y-x+1.0);
  22.     int mxx=max(mx[x][p],mx[y-(1<<p)+1][p]);
  23.     int mnn=min(mn[x][p],mn[y-(1<<p)+1][p]);
  24.     return mxx-mnn;
  25. }
  26. int main()
  27. {
  28.     int t;
  29.     scanf("%d",&t);
  30.     while(t--)
  31.     {
  32.         scanf("%d%d",&n,&k);
  33.         for(int i=1;i<=n;i++)
  34.         {
  35.             scanf("%d",&a[i]);
  36.             mx[i][0]=mn[i][0]=a[i];
  37.         }
  38.         ST();
  39.         long long ans=0;
  40.         for(int i=1;i<=n;i++)
  41.         {
  42.             int l=i,r=n;
  43.             while(l<=r)
  44.             {
  45.                 int mid=(l+r)>>1;
  46.                 if(sol(i,mid)<k) l=mid+1;
  47.                 else
  48.                     r=mid-1;
  49.             }
  50.                 ans += (r * 1LL - i + 1);
  52.         }
  53.         cout<<ans<<endl;
  54.     }
  55.     return 0;
  56. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注