[关闭]
@iamtts 2017-05-14T15:38:01.000000Z 字数 3488 阅读 990

st表与线段树

A - Hotel

题意：一开始有n个连续空房间编号从1到n，现在有两种操作：

1.入住，给出人数k，要求连续k间空房，若无法满足则输出0，满足则输出满足条件且最左边的房间号
2.清空，从房间a到b全部清空

解题思路：用到线段树的区间合并，线段树节点保存管理的区间（l，r），区间内空房最大连续长度（sum),从最左/右边开始最大连续空房间长度（lsum，rsum），和懒惰标记（flag）

AC代码：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <iostream>
  5. using namespace std;
  6. const int N = 100000 + 5;
  8. struct node
  9. {
  10.     int lsum,rsum,sum,l,r,flag;
  11. } tree[N*4];
  12. inline int MAX(int a,int b,int c)
  13. {
  14.     return max(a,max(b,c));
  15. }
  16. void push_up(int now)
  17. {
  18.     tree[now].lsum=tree[now<<1].lsum;
  19.     tree[now].rsum=tree[now<<1|1].rsum;
  20.     if (tree[now].lsum==tree[now<<1].r-tree[now<<1].l+1) tree[now].lsum+=tree[now<<1|1].lsum;
  21.     if (tree[now].rsum==tree[now<<1|1].r-tree[now<<1|1].l+1) tree[now].rsum+=tree[now<<1].rsum;
  22.     tree[now].sum=MAX(tree[now<<1].sum,tree[now<<1|1].sum,tree[now<<1].rsum+tree[now<<1|1].lsum);
  23. }
  24. void push_down(int now)
  25. {
  26.     if (tree[now].flag!=-1)
  27.     {
  28.         tree[now<<1].flag=tree[now<<1|1].flag=tree[now].flag;
  29.         if (tree[now].flag==1)
  30.         {
  31.             tree[now<<1].sum=tree[now<<1].lsum=tree[now<<1].rsum=0;
  32.             tree[now<<1|1].sum=tree[now<<1|1].lsum=tree[now<<1|1].rsum=0;
  33.         }
  34.         else
  35.         {
  36.             tree[now<<1].sum=tree[now<<1].lsum=tree[now<<1].rsum=tree[now<<1].r-tree[now<<1].l+1;
  37.             tree[now<<1|1].sum=tree[now<<1|1].lsum=tree[now<<1|1].rsum=tree[now<<1|1].r-tree[now<<1|1].l+1;
  38.         }
  39.         tree[now].flag=-1;
  40.     }
  41. }
  42. void build_tree(int l,int r,int now)
  43. {
  44.     tree[now].l=l;
  45.     tree[now].r=r;
  46.     tree[now].flag=-1;
  47.     tree[now].lsum=tree[now].rsum=tree[now].sum=r-l+1;
  48.     if (l==r) return;
  49.     int mid=(r+l)/2;
  50.     build_tree(l,mid,now<<1);
  51.     build_tree(mid+1,r,now<<1|1);
  52. }
  53. int query_tree(int l,int r,int now,int x)
  54. {
  55.     if (r==l) return l;
  56.     int mid=(l+r)/2;
  57.     push_down(now);
  58.     if (tree[now<<1].sum>=x) return query_tree(l,mid,now<<1,x);
  59.     else if (tree[now<<1].rsum+tree[now<<1|1].lsum>=x) return mid-tree[now<<1].rsum+1;
  60.     else return query_tree(mid+1,r,now<<1|1,x);
  61. }
  62. void update(int l,int r,int now,int x)
  63. {
  64.     if (tree[now].l==l &&tree[now].r==r)
  65.     {
  66.         tree[now].flag=x;
  67.         if (x)
  68.         {
  69.             tree[now].sum=tree[now].lsum=tree[now].rsum=0;
  70.         }
  71.         else
  72.         {
  73.             tree[now].sum=tree[now].lsum=tree[now].rsum=r-l+1;
  74.         }
  75.         return;
  76.     }
  77.     push_down(now);
  78.     int mid=(tree[now].r+tree[now].l)/2;
  79.     if (mid>=r) update(l,r,now<<1,x);
  80.     else if (mid+1<=l) update(l,r,now<<1|1,x);
  81.     else
  82.     {
  83.         update(l,mid,now<<1,x);
  84.         update(mid+1,r,now<<1|1,x);
  85.     }
  86.     push_up(now);
  87. }
  88. int main()
  89. {
  90.     int n,m;
  92.     while(~scanf("%d%d",&n,&m))
  93.     {
  94.         build_tree(1,n,1);
  95.         for (int i=1; i<=m; i++)
  96.         {
  97.             int judge;
  98.             scanf("%d",&judge);
  100.             if (judge==1)
  101.             {
  102.                 int num;
  103.                 scanf("%d",&num);
  104.                 if (tree[1].sum<num) cout<<0<<endl;
  105.                 else
  106.                 {
  107.                     int x=query_tree(1,n,1,num);
  108.                     printf("%d\n",x);
  109.                     update(x,x+num-1,1,1);
  110.                 }
  112.             }
  113.             else
  114.             {
  115.                 int x,y;
  116.                 scanf("%d%d",&x,&y);
  117.                 update(x,x+y-1,1,0);
  118.             }
  119.         }
  120.     }
  121.     return 0;
  122. }

C - Assignment

题意：给出n个人的能力值，可以从他们中选人组成小组，要求每组里面任意两者的能力值之差小于k，问能分出多少不同的组

解题思路：用st表储存区间的最大值最小值，然后对每个i（from 1 to n）二分出右端点，判断条件就是区间最大值与最小值之差小于k

AC代码：

  1. #include<algorithm>
  2. #include<iostream>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cstdio>
  6. #include<cmath>
  7. #include<queue>
  8. using namespace std;
  10. #define N 100005
  12. int stmax[N][21],stmin[N][21];
  13. int a[N];
  15. int t,q,n,k;
  16. int x,y;
  18. void init()
  19. {
  20.     for (int i=1;i<=n;i++)
  21.     {
  22.         stmax[i][0]=stmin[i][0]=a[i];
  23.     }
  24.     for (int j=1;(1<<j) <= n;j++)
  25.         for (int i=1;i+(1<<j)-1<=n;i++)
  26.         {
  27.             stmax[i][j]=max(stmax[i][j-1],stmax[i+(1<<(j-1))][j-1]);
  28.             stmin[i][j]=min(stmin[i][j-1],stmin[i+(1<<(j-1))][j-1]);
  29.         }
  30. }
  32. bool ok(int L,int R)
  33. {
  34.     int kk= log2(R - L + 1.0);
  35.     int Max=max(stmax[L][kk],stmax[R-(1<<kk)+1][kk]);
  36.     int Min=min(stmin[L][kk],stmin[R-(1<<kk)+1][kk]);
  37.     //printf("%d~%d:%d\n",L,R,Max-Min);
  38.     if (Max-Min<k) return true;
  39.     return false;
  40. }
  42. int main()
  43. {
  44.     scanf("%d",&t);
  45.     while (t--)
  46.     {
  47.         long long cnt=0;
  48.         scanf("%d%d",&n,&k);
  49.         for (int i=1;i<=n;i++)
  50.             scanf("%d",&a[i]);
  51.         init();
  52.         for (int i=1;i<=n;i++)
  53.         {
  55.             long long ub=n,lb=i,mid;
  56.             while (ub-1>lb)
  57.             {
  59.                 mid=(ub+lb)/2;
  60.                 if (ok(i,mid)) lb=mid;
  61.                 else ub=mid;
  63.             }
  64.             if (ok(i,ub)) cnt+=ub-i+1;
  65.             else cnt+=lb-i+1;
  66.             //printf("%d\n",mid-i+1);
  67.         }
  68.         printf("%lld\n",cnt);
  69.     }
  70.     return 0;
  71. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注