[关闭]
@Asuna 2017-05-15T12:27:37.000000Z 字数 7937 阅读 1360

CQUPT 训练题题解 2017/5/8

题解

Problem A: Hotel

题意： 有一个旅馆，有N个连续的房间，开始的时候没有人住，下面有M次‘1’或‘2’操作。操作“1 D”表示有D个人进来选房间，他们必须是住在连号的房间，如果不满足这个条件，输出“0”，否则，输出他们这几个人中房间号码最小的一个；操作“2 X D”表示Hotel从房间号X开始D个房间被清空。

题解：线段树的区间更新（操作2）+区间合并（操作1），在线段树上面维护三个值，分别是对于[l,r]这段区间，从l开始的连续区间的长度，以r结尾的连续区间的长度，[l,r]之间最长连续区间的长度。然后是两个操作的方法：
1、合并两个区间[a,b],[c,d] 的时候，得到的新的区间[a,d]的最大连续区间长度为：Length(a,d)=max{Length(a,b),Length(c,d),End(b)+Begin(c)}；
其中End(b)表示的是以b为结尾的连续区间长度，Begin(c)表示的是以c开头的连续区间的长度。
2、更新整个给定区间的时候，由于直接单点逐一更新会导致复杂度爆表，因此需要用到一个lazy-tag（js教本鶸的）。lazy-tag的定义如下：
（1）访问某一节点时，清空该节点标记并把此标记下传给它的左右孩子。
（2）当我们所要修改（or查询）的区间[a,b]与该节点所代表的区间相合时，给这一节点作上标记，退出这层递归。
（3）如果不相合，则继续修改（or查询）左右子节点。具体方法是：当[a,b]在此节点所代表区间的左边时访问左子节点，在右边时访问右子节点，否则按如下方式访问：（lchild,a，p^.m）和（rchild,p^.m+1,b）
（4）清空左右子节点，并把左右子节点的值上传至根节点。

$$说白了就相当于给非叶子结点的更新操作都是一个标记，表示他要修改，但在修改叶子节点前并不更新他的值，直到做到叶子节点的时候更新叶子节点的值一并更新。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<cmath>
  6. using namespace std;
  7. struct node
  8. {
  9.     int ln, rn, mn;
  10. }f[400010];
  11. int tag[400010],handle,ans,X,D,n,m;
  13. void PushUp(int rt,int l,int r)
  14. {
  15.     f[rt].ln=f[rt<<1].ln;
  16.     f[rt].rn=f[rt<<1|1].rn;
  17.     f[rt].mn=max(f[rt<<1].rn+f[rt<<1|1].ln,max(f[rt<<1].mn,f[rt<<1|1].mn));
  18.     int mid=(l+r)/2;
  19.     if(f[rt<<1].mn==mid-l+1)
  20.         f[rt].ln+=f[rt<<1|1].ln;
  21.     if(f[rt<<1|1].mn==r-(mid+1)+1)
  22.         f[rt].rn+=f[rt<<1].rn;
  23. }
  25. void PushDown(int rt,int l,int r)
  26. {
  27.     if(tag[rt]!=-1)
  28.     {
  29.         tag[rt<<1]=tag[rt<<1|1]=tag[rt];
  30.         int mid=(l+r)/2;
  31.         f[rt<<1].ln=f[rt<<1].rn=f[rt<<1].mn=tag[rt]*(mid-l+1);
  32.         f[rt<<1|1].ln=f[rt<<1|1].rn=f[rt<<1|1].mn=tag[rt]*(r-(mid+1)+1);
  33.         tag[rt]=-1;
  34.     }
  36. }
  37. void Build(int l, int r, int rt)
  38. {
  39.     f[rt].ln=f[rt].rn=f[rt].mn=r-l+1;
  40.     tag[rt]=1;
  41.     if(l==r) return ;
  42.     int mid=(l+r)/2;
  43.     Build(l,mid,rt<<1);
  44.     Build(mid+1,r,rt<<1|1);
  45. }
  47. void Update(int L,int R,bool isClear,int l,int r,int rt)
  48. {
  49.     if(L<=l && r<=R)
  50.     {
  51.         if(isClear)
  52.         {
  53.             f[rt].ln=f[rt].rn=f[rt].mn=r-l+1;
  54.             tag[rt]=1;
  55.         }
  56.         else
  57.         {
  58.             f[rt].ln=f[rt].rn=f[rt].mn=0;
  59.             tag[rt]=0;
  60.         }
  61.         return;
  62.     }
  63.     PushDown(rt,l,r);
  64.     int mid=(l+r)/2;
  65.     if (L<=mid)
  66.         Update(L,R,isClear,l,mid,rt<<1 );
  67.     if (mid<R)
  68.         Update(L,R,isClear,mid+1,r,rt<<1|1);
  69.     PushUp(rt,l,r);
  70. }
  72. int Query(int len,int l,int r,int rt)
  73. {
  74.     if (f[rt].ln>=len) return l;
  75.     int mid=(l+r)/2;
  76.     if(f[rt << 1].mn>=len)
  77.         return Query(len,l,mid,rt<<1);
  78.     else
  79.         if (f[rt<<1].rn+f[rt<<1|1].ln>=len)
  80.         return mid-f[rt<<1].rn+1;
  81.     else
  82.         return Query(len,mid+1,r,rt<<1|1);
  83. }
  85. int main()
  86. {
  87.     while (cin>>n>>m)
  88.     {
  89.         Build(1,n,1);
  90.         while (m--)
  91.         {
  92.             scanf("%d",&handle);
  93.             if (handle&1)
  94.             {
  95.                 scanf("%d",&D);
  96.                 if (f[1].mn<D)
  97.                 {
  98.                     printf("0\n");
  99.                     continue;
  100.                 }
  101.                 ans=Query(D,1,n,1);
  102.                 printf("%d\n",ans);
  103.                 Update(ans,ans+D-1,false,1,n,1);
  104.             }
  105.             else
  106.             {
  107.                 scanf("%d%d",&X,&D);
  108.                 Update(X,X+D-1,true,1,n,1);
  109.             }
  110.         }
  111.     }
  112.     return 0;
  113. }

Problem B:A Corrupt Mayor's Performance Art

题意：一长由N小段组成的长条，每小段的初始颜色为2。现执行M个操作，每个操作是以下两种中的一种：
P a b c：将段a到段b涂成颜色c，c是1, 2, ... 30中的一种。
Q a b：问段a到段b之间有哪几种颜色，按颜色大小从小到大输出。

题解：线段树的区间查询和区间修改。
对于P操作，就是区间修改，也需要和Problem A一样用到lazy-tag。
对于Q操作，每查询到一个有颜色的区间就丢进set中，最后把set中的元素一起输出。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<set>
  6. using namespace std;
  7. int n,m,f[4000010];
  8. set<int> st;
  9. set<int>::iterator it;
  10. void pushDown(int rt)
  11. {
  12.     if(f[rt]!=-1)
  13.     {
  14.         f[rt<<1]=f[rt<<1|1]=f[rt];
  15.         f[rt]=-1;
  16.     }
  17. }
  19. void pushUp(int rt)
  20. {
  21.     if (f[rt<<1]==f[rt<<1|1])
  22.     {
  23.         f[rt]=f[rt<<1];
  24.     }
  25.     else f[rt]=-1;
  26. }
  28. void build(int rt, int L, int R)
  29. {
  30.     f[rt]=-1;
  31.     if (L==R)
  32.     {
  33.         f[rt]=2;
  34.         return ;
  35.     }
  36.     int mid=(L+R)/2;
  37.     build(rt<<1,L,mid);
  38.     build(rt<<1|1,mid+1,R);
  39.     pushUp(rt);
  40. }
  42. void update(int rt, int L, int R, int ql, int qr, int val)
  43. {
  44.     if(ql<=L && R<=qr)
  45.     {
  46.         f[rt]=val;
  47.         return ;
  48.     }
  49.     int mid=(L+R)/2;
  50.     pushDown(rt);
  51.     if (ql<=mid) update(rt<<1,L,mid,ql,qr,val);
  52.     if (qr>mid) update(rt<<1|1,mid+1,R,ql,qr,val);
  53.     pushUp(rt);
  54. }
  56. void query(int rt, int L, int R, int ql, int qr)
  57. {
  58.     if (f[rt]!=-1 && ql<=L && R<=qr)
  59.     {
  60.         st.insert(f[rt]);
  61.         return ;
  62.     }
  63.     int mid=(L+R)/2;
  64.     pushDown(rt);
  65.     if (ql<=mid) query(rt<<1,L,mid,ql,qr);
  66.     if (qr>mid) query(rt<<1|1,mid+1,R,ql,qr);
  67.     pushUp(rt);
  68. }
  70. int main()
  71. {
  72.     char op[5];
  73.     int ql,qr,val;
  74.     while(cin>>n>>m)
  75.     {
  76.         if (n==0 && m==0) break;
  77.         build(1,1,n);
  78.         while(m--)
  79.         {
  80.             scanf("%s",op);
  81.             if(op[0]=='P')
  82.             {
  83.                 scanf("%d%d%d",&ql,&qr,&val);
  84.                 update(1,1,n,ql,qr,val);
  85.             }else
  86.             {
  87.                 scanf("%d%d",&ql,&qr);
  88.                 st.clear();
  89.                 query(1,1,n,ql,qr);
  90.                 it=st.begin();
  91.                 printf("%d",*it); it++;
  92.                 for(; it!=st.end(); it++)
  93.                 {
  94.                     printf(" %d",*it);
  95.                 }
  96.                 printf("\n");
  97.             }
  98.         }
  99.     }
  100.     return 0;
  101. }

Problem C:Assignment

题意：输入n,k,问n个数的序列，有多少个区间，最大值减最小值小于k。

题解：发现这是一道区间查询最值的题目，所以用rmq肯定是没错的（事实上好像不用），枚举子串的左端点i，二分右端点R，使得[i,R]长度最大，那么这样一来这个子串是肯定符合的，实际上把右端点往左缩一个得到的小一个单位的子串也肯定是符合的，这样可以一直缩到区间变成[i,i]，因此每一次枚举得到的区间[i,R]可以产生R−i+1个符合题意的子串，然后记得开long long就行了。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<cstring>
  5. using namespace std;
  6. int a[200010],n,m,dp1[200010][30],dp2[100010][30],t;
  8. int rmq(int x,int y)
  9. {
  10.     int k=0;
  11.     while ((1<<(k+1))<=y-x+1) k++;
  12.     return max(dp1[x][k],dp1[y-(1<<k)+1][k])-min(dp2[x][k],dp2[y-(1<<k)+1][k]);
  13. }
  15. int main()
  16. {
  17.     scanf("%d",&t);
  18.     while(t--)
  19.     {
  20.         scanf("%d%d",&n,&m);
  21.         for (int i=1; i<=n; i++)
  22.         {
  23.             scanf("%d",&a[i]);
  24.         }
  25.         for (int i=1; i<=n; i++)
  26.         {
  27.             dp1[i][0]=a[i];
  28.             dp2[i][0]=a[i];
  29.         }
  30.         for (int j=1; (1<<j)<=n; j++)
  31.         {
  32.             for (int i=1; i+(1<<j)-1<=n; i++)
  33.             {
  34.                 dp1[i][j]=max(dp1[i][j-1],dp1[i+(1<<(j-1))][j-1]);
  35.                 dp2[i][j]=min(dp2[i][j-1],dp2[i+(1<<(j-1))][j-1]);
  36.             }
  37.         }
  38.         int k=1;
  39.         long long sum=0;
  40.         for (int i=1; i<=n; i++)
  41.         {
  42.             while (rmq(k,i)>=m&&k<i) k++;
  43.             sum+=(i-k+1);
  44.         }
  45.         printf("%lld\n",sum);
  46.     }
  47.     return 0;
  48. }

Problem D：GCD

题意：给你n个数，然后给你一对l,r，求这n个数的子区间中gcd值等于gcd(l,l+1,...,r)的个数。

题解：用线段树能求出一个区间的gcd，因此难点就在预处理出所有子区间以供筛选，一开始这个问题十分头疼，于是看了一篇tj，发现可以用map存储gcd的个数和种类（stl还是不熟），以a[i]为右端点进行扫描，右端点不断向后移动，以a[i]为右端点的gcd=gcd(以a[i-1]为右端点的gcd，a[i])，我们通过记录以前一个元素为右端点的gcd，然后扫描就可以了，这样就可以求出所有子区间的gcd种类和个数。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cmath>
  4. #include<cstring>
  5. #include<map>
  6. #include<queue>
  7. using namespace std;
  8. struct node
  9. {
  10.     long long num,l,r;
  11. }tree[4000010];
  13. map<long long,long long>mp1,mp2,cnt;
  14. map<long long,long long>::iterator it;
  15. long long a[1000010];
  17. long long gcd(long long a,long long b)
  18. {
  19.     return b?gcd(b,a%b):a;
  20. }
  22. long long lcm(long long a,long long b)
  23. {
  24.     return a/gcd(a,b)*b;
  25. }
  27. long long powmod(long long a,long long b,long long MOD)
  28. {
  29.     long long ans=1;
  30.     while(b)
  31.     {
  32.         if(b%2)
  33.             ans=ans*a%MOD;
  34.         a=a*a%MOD;
  35.         b/=2;
  36.     }
  37.     return ans;
  38. }
  40. double dpow(double a,long long b)
  41. {
  42.     double ans=1.0;
  43.     while(b)
  44.     {
  45.         if(b%2)
  46.             ans=ans*a;
  47.         a=a*a;
  48.         b/=2;
  49.     }
  50.     return ans;
  51. }
  53. void build(int i,int L,int R)
  54. {
  55.     tree[i].l=L;
  56.     tree[i].r=R;
  57.     if (L==R)
  58.     {
  59.         tree[i].num=a[L];
  60.     }
  61.     else
  62.     {
  63.         int mid=(L+R)/2;
  64.         build(i*2,L,mid);
  65.         build(i*2+1,mid+1,R);
  66.         tree[i].num=gcd(tree[i*2].num,tree[i*2+1].num);
  67.     }
  68. }
  70. long long query(int i,int L,int R)
  71. {
  72.     if(tree[i].l==L&&tree[i].r==R)
  73.     {
  74.         return tree[i].num;
  75.     }
  76.     if (R<=tree[i*2].r) return query(i*2,L,R);
  77.     else
  78.     if (L>=tree[i*2+1].l) return query(i*2+1,L,R);
  79.     else
  80.     {
  81.         int mid=(tree[i].l+tree[i].r)/2;
  82.         return gcd(query(i*2,L,mid),query(i*2+1,mid+1,R));
  83.     }
  84. }
  86. int main()
  87. {
  88.     int n,m,t,icase=0;
  89.     scanf("%d",&t);
  90.     while (t--)
  91.     {
  92.         scanf("%d",&n);
  93.         for (int i=1; i<=n; i++)
  94.             scanf("%lld",&a[i]);
  95.         build(1,1,n);
  96.         mp1.clear();
  97.         mp2.clear();
  98.         cnt.clear();
  99.         for (int i=1; i<=n; i++)
  100.         {
  101.             cnt[a[i]]++;
  102.             mp2[a[i]]++;
  103.             for (it=mp1.begin(); it!=mp1.end(); it++)
  104.             {
  105.                 long long k=gcd(a[i],it->first);
  106.                 cnt[k]+=it->second;
  107.                 mp2[k]+=it->second;
  108.             }
  109.             mp1.clear();
  110.             for (it=mp2.begin(); it!=mp2.end(); it++)
  111.             {
  112.                 mp1[it->first]=it->second;
  113.             }
  114.             mp2.clear();
  115.         }
  116.         scanf("%d",&m);
  117.         printf("Case #%d:\n",++icase);
  118.         for (int i=1; i<=m; i++)
  119.         {
  120.             int L,R;
  121.             scanf("%d%d",&L,&R);
  122.             long long ans=query(1,L,R);
  123.             printf("%lld %lld\n",ans,cnt[ans]);
  124.         }
  125.     }
  126.     return 0;
  127. }

Problem E：K-th Number

题意：给出一个序列，有若干个询问，每次询问从l~r的这段区间内第k大的数是哪个。

题解：静态第k大问题。kuangbin的模板里面用主席树处理这个问题，但是kuangbin聚聚的模板本鶸并不能看懂，于是上网找了一个模板来用，这道题是一道裸模板题所以只要搞懂了主席树就套版就行了。

顺便mark一下动态第k大还不会，例题dynamic ranking

参考代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. using namespace std;
  5. struct Node{
  6.     int a,b,rs,ls,sum;
  7. }tr[2000010];
  8. int a[100010],b[100010];
  9. int rt[100010],pos,cnt;
  10. void Build(int &node,int a,int b)
  11. {
  12.     node=++cnt;
  13.     tr[node].a=a;
  14.     tr[node].b=b;
  15.     if(a==b)return;
  16.     int mid=(a+b)>>1;
  17.     Build(tr[node].ls,a,mid);
  18.     Build(tr[node].rs,mid+1,b);
  19. }
  21. void Insert(int pre,int &node)
  22. {
  23.     node=++cnt;
  24.     tr[node].ls=tr[pre].ls;
  25.     tr[node].rs=tr[pre].rs;
  26.     tr[node].a=tr[pre].a;
  27.     tr[node].b=tr[pre].b;
  28.     tr[node].sum=tr[pre].sum+1;
  29.     if(tr[node].a==tr[node].b)return;
  30.     int mid=(tr[node].a+tr[node].b)>>1;
  31.     if(mid>=pos)Insert(tr[pre].ls,tr[node].ls);
  32.     else Insert(tr[pre].rs,tr[node].rs);
  33. }
  34. int Query(int pre,int node,int k)
  35. {
  36.     if(tr[node].ls==tr[node].rs)return b[tr[node].a];
  37.     int cmp=tr[tr[node].ls].sum-tr[tr[pre].ls].sum;
  38.     if(cmp>=k)return Query(tr[pre].ls,tr[node].ls,k);
  39.     else return Query(tr[pre].rs,tr[node].rs,k-cmp);
  40. }
  41. int main()
  42. {
  43.     int n,q;
  44.     scanf("%d%d",&n,&q);
  45.     for(int i=1;i<=n;b[i]=a[i],i++)
  46.         scanf("%d",&a[i]);
  47.     sort(b+1,b+n+1);
  48.     Build(rt[0],1,n);
  49.     for(int i=1;i<=n;i++)
  50.     {
  51.         pos=lower_bound(b+1,b+n+1,a[i])-b;
  52.         Insert(rt[i-1],rt[i]);
  53.     }    
  54.     int l,r,k;
  55.     for(int i=1;i<=q;i++)
  56.     {
  57.         scanf("%d%d%d",&l,&r,&k);
  58.         printf("%d\n",Query(rt[l-1],rt[r],k));
  59.     }
  60.     return 0;
  61. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注