CQUPT 训练题 2017/5/8

题解

题目

A Hotel

题目大意：

    有N(1<=N<=50000)间初始为空的房间，房号从1到N。M(1<=M<50000)个操作，操作分为两种：(1)申请连续D(1<=D<=N)间房号连续的空房间，如果存在这样的一段空房间，输出其中房号最小的那一间的房号，并且这D间房全部住人，否则输出0(2)将从X开始的D间房置为空(1<=X<=N-D+1)。

解题思路：

    用线段树维护区间最大连续空房间的长度。要用到lazy标记来进行区间修改，否则复杂度会爆炸。
    查询的时候，如果整个区间的最大连续长度小于D，肯定不存在这样的连续区间，直接返回0。接下来依次考虑左区间有长度大于等于D的连续空房，左区间右边界的连续空房延伸到右区间左边界的连续空房长度大于等于D，右区间有长度大于等于D的连续空房这三种情况。
    ps：置空操作可能涉及原本就是空的房间。我的lazy标记有0，1，-1三种状态，0表示没有延迟操作，1表示延迟了整个区间住人的操作，-1表示整个区间置空的操作，实际上这个标记起到了两个标记的作用。
    时间复杂度o(M*log(N))，空间复杂度o(N)。

AC代码：

#include<iostream>
#include<cstdio>
using namespace std;
struct Node
{
    int l,r,mid,flag,slen,llen,rlen;
}tre[200005];
void build(int x,int l,int r)
{
    tre[x].l=l;
    tre[x].r=r;
    tre[x].mid=(l+r)>>1;
    tre[x].flag=0;
    tre[x].llen=tre[x].rlen=tre[x].slen=r-l+1;
    if(l!=r)
    {
        build(x*2,l,tre[x].mid);
        build(x*2+1,tre[x].mid+1,r);
    }
    return;
}
void change(int x,int l,int r,int f)
{
    if(l==tre[x].l && r==tre[x].r)
    {
        tre[x].flag=f;
        if(f>0)
            tre[x].llen=tre[x].rlen=tre[x].slen=0;
        else
            tre[x].llen=tre[x].rlen=tre[x].slen=r-l+1;
        return;
    }
    if(tre[x].flag)
    {
        change(x*2,tre[x].l,tre[x].mid,tre[x].flag);
        change(x*2+1,tre[x].mid+1,tre[x].r,tre[x].flag);
        tre[x].flag=0;
    }
    if(l<=tre[x].mid && r>tre[x].mid)
    {
        change(x*2,l,tre[x].mid,f);
        change(x*2+1,tre[x].mid+1,r,f);
    }
    else
    {
        if(r<=tre[x].mid)
            change(x*2,l,r,f);
        else
            change(x*2+1,l,r,f);
    }
    tre[x].llen=tre[x*2].llen;
    if(tre[x].llen==tre[x].mid-tre[x].l+1)
        tre[x].llen+=tre[x*2+1].llen;
    tre[x].rlen=tre[x*2+1].rlen;
    if(tre[x].rlen==tre[x].r-tre[x].mid)
        tre[x].rlen+=tre[x*2].rlen;
    tre[x].slen=max(max(tre[x*2].slen,tre[x*2+1].slen),tre[x*2].rlen+tre[x*2+1].llen);
    return;
}
int ask(int x,int lens)
{
    if(tre[x].slen<lens)
        return 0;
    if(tre[x].r-tre[x].l+1==lens)
        return tre[x].l;
    if(tre[x].flag)
    {
        change(x*2,tre[x].l,tre[x].mid,tre[x].flag);
        change(x*2+1,tre[x].mid+1,tre[x].r,tre[x].flag);
        tre[x].flag=0;
    }
    if(tre[x*2].slen>=lens)
        return ask(x*2,lens);
    if(tre[x*2].rlen+tre[x*2+1].llen>=lens)
        return tre[x].mid-tre[x*2].rlen+1;
    return ask(x*2+1,lens);
}
int main()
{
    int n,m;
    int t,a,b,c;
    scanf("%d%d",&n,&m);
    build(1,1,n);
    while(m--)
    {
        scanf("%d",&t);
        if(t==1)
        {
            scanf("%d",&a);
            c=ask(1,a);
            if(c)
            change(1,c,c+a-1,1);
            printf("%d\n",c);
        }
        else
        {
            scanf("%d%d",&a,&b);
            change(1,a,a+b-1,-1);
        }
    }
    return 0;
}

B A Corrupt Mayor's Performance Art

题目大意：

    有30种颜色，编号从1到30。把原色为2的墙分为N(0<N<=1000000)段，编号从1到N，接下来是M(0<M<=100000)个操作，操作分两种：(1)把编号从a到b(0<a<=b<=N)的墙染成颜色c(0<c<=30)(2)询问编号从a到b(0<a<=b<=N)的墙有哪些颜色，按照编号从小到大输出他们。
    多组数据。

解题思路：

    我们可以用一个结构体，装30个bool，来表示某个区间出现了哪些颜色。然后我们会发现2^30-1在int范围之内，于是我们就不需要用装了30个bool的结构体了，直接用一个int在2进制下的对应位表示这种颜色是否出现。区间合并的时候，直接把左右子区间的颜色出现情况进行按位或就得到了合并后的区间的颜色出现情况。一样用lazy标记实现区间修改。
    ps：我传进修改函数的参数和lazy都是颜色对应的2进制表示。一开始墙的颜色都是2这点没读到的话挺坑的。。。
    时间复杂度o(M*(log(N)+30))，空间复杂度o(N)。

AC代码：

#include<iostream>
#include<cstdio>
using namespace std;
struct Node
{
    int l,r,mid,flag,val;
}tre[4000005];
void build(int x,int l,int r)
{
    tre[x].l=l;
    tre[x].r=r;
    tre[x].mid=(l+r)>>1;
    tre[x].flag=0;
    tre[x].val=2;
    if(l!=r)
    {
        build(x*2,l,tre[x].mid);
        build(x*2+1,tre[x].mid+1,r);
    }
    return;
}
void change(int x,int l,int r,int f)
{
    if(l==tre[x].l && r==tre[x].r)
    {
        tre[x].flag=f;
        tre[x].val=f;
        return;
    }
    if(tre[x].flag)
    {
        change(x*2,tre[x].l,tre[x].mid,tre[x].flag);
        change(x*2+1,tre[x].mid+1,tre[x].r,tre[x].flag);
        tre[x].flag=0;
    }
    if(l<=tre[x].mid && r>tre[x].mid)
    {
        change(x*2,l,tre[x].mid,f);
        change(x*2+1,tre[x].mid+1,r,f);
    }
    else
    {
        if(r<=tre[x].mid)
            change(x*2,l,r,f);
        else
            change(x*2+1,l,r,f);
    }
    tre[x].val=tre[x*2].val|tre[x*2+1].val;
    return;
}
int ask(int x,int l,int r)
{
    if(tre[x].l==l && tre[x].r==r)
        return tre[x].val;
    if(tre[x].flag)
    {
        change(x*2,tre[x].l,tre[x].mid,tre[x].flag);
        change(x*2+1,tre[x].mid+1,tre[x].r,tre[x].flag);
        tre[x].flag=0;
    }
    if(l<=tre[x].mid && r>tre[x].mid)
        return ask(x*2,l,tre[x].mid)|ask(x*2+1,tre[x].mid+1,r);
    else
    {
        if(r<=tre[x].mid)
            return ask(x*2,l,r);
        else
            return ask(x*2+1,l,r);
    }
}
int num[35];
void solve(int x)
{
    bool flag=0;
    for(int i=1;i<=30;i++)
    {
        if(x&num[i])
        {
            if(flag)
                printf(" ");
            else
                flag=1;
            printf("%d",i);
        }
    }
    printf("\n");
    return;
}
int main()
{
    int n,m;
    int a,b,c;
    char s[6];
    num[1]=1;
    for(int i=2;i<=30;i++)
        num[i]=num[i-1]*2;
    while(scanf("%d%d",&n,&m),n || m)
    {
        build(1,1,n);
        while(m--)
        {
            scanf("%s",s);
            if(s[0]=='P')
            {
                scanf("%d%d%d",&a,&b,&c);
                change(1,a,b,num[c]);
            }
            else
            {
                scanf("%d%d",&a,&b);
                solve(ask(1,a,b));
            }
        }
    }
    return 0;
}

C Assignment

题目大意：

    有n(1<=n<=100000)个员工，每个员工有一个能力值a(0<a<=10^9)。求有多少个连续区间，满足区间内任何两个员工的能力值差距小于k(0<k<=10^9)。
    T组数据。

解题思路：

    区间内任何两个员工的能力值差距不超过k，实际上就是区间内能力值最大的员工和区间内能力值最小的员工能力值差距小于k。用两个st表，分别求区间最大值和区间最小值。
    但是区间一共有n*(n-1)/2个，枚举区间进行判断显然不合理。
    我们会发现，如果区间的左端点固定，随着右端点往右移动，区间最大值不减，区间最小值不增，于是区间最大值和区间最小值的差距是不减的。所以我们可以枚举左端点，二分右端点，这样就可以求出所有满足要求的区间。
    ps:我预处理了每个查询区间长度对应的两个段现成的st表区间长度，不然时间复杂度要多乘一个log(n)。
    时间复杂度o(T*n*log(n))，空间复杂度o(n*log(n))。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n;
int num[100005],minn[20][100005],maxx[20][100005],lens[20];
int ok[100005];
void init()
{
    for(int i=1;lens[i]<=n;i++)
    {
        for(int j=1;j+lens[i]-1<=n;j++)
        {
            minn[i][j]=min(minn[i-1][j],minn[i-1][j+lens[i-1]]);
            maxx[i][j]=max(maxx[i-1][j],maxx[i-1][j+lens[i-1]]);
        }
    }
    return;
}
int ask(int l,int r)
{
    int len=ok[r-l+1];
    return max(maxx[len][l],maxx[len][r-lens[len]+1])-min(minn[len][l],minn[len][r-lens[len]+1]);
}
int main()
{
    int t,k,l,r,mid;
    long long ans;
    scanf("%d",&t);
    lens[0]=1;
    for(int i=1;i<20;i++)
    {
        lens[i]=lens[i-1]<<1;
        for(int j=lens[i-1];j<=100000 && j<lens[i];j++)
            ok[j]=i-1;
    }
    while(t--)
    {
        scanf("%d%d",&n,&k);
        for(int i=1,j=0;i<=n;i++)
        {
            scanf("%d",&minn[0][i]);
            maxx[0][i]=minn[0][i];
        }
        ans=0;
        init();
        for(int i=1;i<=n;i++)
        {
            l=i;
            r=n;
            while(l!=r)
            {
                mid=(l+r+1)>>1;
                if(ask(i,mid)<k)
                    l=mid;
                else
                    r=mid-1;
            }
            ans+=l-i+1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

D GCD

题目大意：

    有一个由N(N<=100000)个数组成的数列a(0<a≤10^9)，Q(Q<=100000)个询问，对于每个询问输出区间a到b(1<=a<=b<=N)的gcd和一共有多少个区间的gcd和所查询的区间gcd一样(包括所查询的区间)。
    T组数据。

解题思路：

    一个区间的gcd的等于区间内所有数的gcd。先讲一个常识gcd(a，b，c)=gcd(gcd(a，b)，c)=gcd(a，gcd(b，c))。
    用st表维护区间gcd。查询区间的gcd没有难度，难度在于怎么查询一共有多少个区间的gcd和所查询的区间的gcd一样的。区间一共有n*(n-1)/2个，a的范围是10^9，所以枚举gcd和枚举区间都不可行。
    我们发现，如果固定区间的左端点l，移动右端点r，假设l<=r1<r2那么区间l到r1的gcd>=区间l到r2的gcd，并且区间l到r2的gcd是区间l到r1的gcd的因数。原因和我之前说的那个常识有关，你们自己思考一下。所以当区间的左端点l固定，那么区间的gcd值最多有log(a[l])个。
    枚举区间左端点，对于每一个gcd值，二分查找他的右端点的最大值，然后用一个map记录每一个gcd值对应的区间个数。
    ps:可能说的有点晕，看代码会好理解一点。一样预处理了每个区间长度对应的要用到的st表的长度。多组数据所以每次要记得清空map。。。
    时间复杂度o(n*log(n)*log(n))，空间复杂度o(n*log(n))。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<map>
using namespace std;
int n;
int num[20][100005],lens[20];
int ok[100005];
map <int,long long>mp;
int gcd(int x,int y)
{
    if(x%y)
        return gcd(y,x%y);
    else
        return y;
}
int ask(int l,int r)
{
    int len=ok[r-l+1];
    return gcd(num[len][l],num[len][r-lens[len]+1]);
}
void init()
{
    int temp,l,r,mid,now;
    for(int i=1;lens[i]<=n;i++)
        for(int j=1;j+lens[i]-1<=n;j++)
            num[i][j]=gcd(num[i-1][j],num[i-1][j+lens[i-1]]);
    for(int i=1;i<=n;i++)
    {
        now=i;
        while(now<=n)
        {
            temp=ask(i,now);
            l=now;
            r=n;
            while(l!=r)
            {
                mid=(l+r+1)>>1;
                if(ask(i,mid)<temp)
                    r=mid-1;
                else
                    l=mid;
            }
            mp[temp]+=l-now+1;
            now=l+1;
        }
    }
    return;
}
int main()
{
    int t,m,l,r,ans;
    scanf("%d",&t);
    lens[0]=1;
    for(int i=1;i<20;i++)
    {
        lens[i]=lens[i-1]<<1;
        for(int j=lens[i-1];j<=100000 && j<lens[i];j++)
            ok[j]=i-1;
    }
    for(int cases=1;cases<=t;cases++)
    {
        printf("Case #%d:\n",cases);
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&num[0][i]);
        mp.clear();
        init();
        scanf("%d",&m);
        while(m--)
        {
            scanf("%d%d",&l,&r);
            ans=ask(l,r);
            printf("%d",ans);
            printf(" %lld\n",mp[ans]);
        }
    }
    return 0;
}

E K-th Number

题目大意：

    由n(1<=n<=100000)个数组成的数列a(|a|<=10^9)，m(1<=m<=5000)个询问，对于每个询问输出区间a到b(1<=a<=b<=n)内第k(1<=k<=b-a+1)小的数。

解题思路：

    裸的主席树求区间第k小。
    a的范围比较大，必须先离散化，这个也是很常见的做法了。可以参考一下我的离散化方式。
    ps：这题保证了数列里每个数是不一样的，但是我离散化是允许出现重复的数的。
    时间复杂度o((n+m)*log(n))，空间复杂度o(n*log(n))。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<map>
using namespace std;
struct Node
{
    int num,lson,rson;
}tre[2500005];
struct Num
{
    int val,no;
}nums[100005];
int cntn,cntt,root[100005];
int ans[100005];
int prenum;
bool cmp1(Num x1,Num x2)
{
    return x1.val<x2.val;
}
bool cmp2(Num x1,Num x2)
{
    return x1.no<x2.no;
}
int build(int l,int r)
{
    int x=++cntt,mid=(l+r)>>1;
    tre[x].num=0;
    if(l==r)
        tre[x].lson=tre[x].rson=-1;
    else
    {
        tre[x].lson=build(l,mid);
        tre[x].rson=build(mid+1,r);
    }
    return x;
}
int change(int pre,int l,int r,int y)
{
    int now=++cntt;
    tre[now].num=tre[pre].num+1;
    if(l==r)
        tre[now].lson=tre[now].rson=-1;
    else
    {
        int mid=(l+r)>>1;
        if(y<=mid)
        {
            tre[now].rson=tre[pre].rson;
            tre[now].lson=change(tre[pre].lson,l,mid,y);
        }
        else
        {
            tre[now].lson=tre[pre].lson;
            tre[now].rson=change(tre[pre].rson,mid+1,r,y);
        }
    }
    return now;
}
int ask(int lnode,int rnode,int l,int r,int k)
{
    if(l==r)
        return l;
    else
    {
        int temp=tre[tre[rnode].lson].num-tre[tre[lnode].lson].num,mid=(l+r)>>1;
        if(temp>=k)
            return ask(tre[lnode].lson,tre[rnode].lson,l,mid,k);
        else
            return ask(tre[lnode].rson,tre[rnode].rson,mid+1,r,k-temp);
    }
}
int main()
{
    int n,m,a,b,k;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        nums[i].no=i;
        scanf("%d",&nums[i].val);
    }
    sort(nums+1,nums+1+n,cmp1);
    cntn=1;
    prenum=nums[1].val;
    ans[1]=nums[1].val;
    nums[1].val=1;
    for(int i=2;i<=n;i++)
    {
        if(nums[i].val!=prenum)
        {
            cntn++;
            ans[cntn]=nums[i].val;
            prenum=nums[i].val;
        }
        nums[i].val=cntn;
    }
    cntt=0;
    root[0]=build(1,cntn);
    sort(nums+1,nums+1+n,cmp2);
    for(int i=1;i<=n;i++)
        root[i]=change(root[i-1],1,cntn,nums[i].val);
    while(m--)
    {
        scanf("%d%d%d",&a,&b,&k);
        printf("%d\n",ans[ask(root[a-1],root[b],1,cntn,k)]);
    }
    return 0;
}

F Shooting

题目大意：

    在横坐标1到X(1<=X<=100000)的区间内，有N个线段(1<=N<=100000)，每个线段有起点L、终点R、高度D三个属性(1<=L<=R<=N，1<=D<=10000000)。有M(1<=M<=100000)次射击，每次射击将从横坐标x(1<=x<=X）纵坐标为0的位置往上击穿高度最低的K个线段，击穿某条线段会得到等于高度的得分，K=(a*pre+b)%c(0<=a，b<=N，1<=c<=10000000)，其中pre为上一次射击的分数(初始默认为1)。并且如果上一次射击的分数超过P(P<=1000000000)，那么这次射击的总分翻倍。
    多组数据。

解题思路：

    首先K和上一次射击有关以及上次分数超过P这次分数要翻倍这两条规则，限制了这题的询问是强制在线的。
    如果我们在每个点把出现的高度建一棵权值线段树，一次射击实际上就是求这个权值线段树对应的前K小的数的和。
    因为射击不改变线段的情况，所以我们可以直接用主席树维护每个点的权值线段树。主席树实际上维护的是前缀区间的点的出现情况，所以我们把从a到b的线段，变为在a点插入，b+1点删除即可。这个实际上和差分数组的思路是一样的。
    ps：注意一定要按坐标顺序建，因为坐标小的点会影响到后续的所有点。如果某个区间的右端点为X，那么删除的坐标就会是X+1，因为是多组数据，所以要清空X+1对应的删除，我这里采用的是对X+1也建树的方法。注意初始化。每次射击的总分数会爆int。每个线段对应一个插入一个删除，所以其实总共会修改2*N条链，如果是用静态内存池，开空间的时候要注意。可能会有某些点不存在插入和删除操作。
    时间复杂度o((X+M)*log(N))，空间复杂度o(X*log(N))。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
struct Node
{
    int num,lson,rson;
    long long val;
}tre[5000005];
struct Num
{
    int val,l,r;
}nums[100005];
queue <int> ql[100005],qr[100005];
int cntn,cntt,root[100005];
int ans[100005];
int prenum,flag;
bool cmp(Num x1,Num x2)
{
    return x1.val<x2.val;
}
int build(int l,int r)
{
    int x=++cntt,mid=(l+r)>>1;
    tre[x].num=0;
    tre[x].val=0;
    if(l==r)
        tre[x].lson=tre[x].rson=-1;
    else
    {
        tre[x].lson=build(l,mid);
        tre[x].rson=build(mid+1,r);
    }
    return x;
}
int change(int pre,int l,int r,int y)
{
    int now=++cntt;
    tre[now].num=tre[pre].num+flag;
    tre[now].val=tre[pre].val+flag*ans[y];
    if(l==r)
        tre[now].lson=tre[now].rson=-1;
    else
    {
        int mid=(l+r)>>1;
        if(y<=mid)
        {
            tre[now].rson=tre[pre].rson;
            tre[now].lson=change(tre[pre].lson,l,mid,y);
        }
        else
        {
            tre[now].lson=tre[pre].lson;
            tre[now].rson=change(tre[pre].rson,mid+1,r,y);
        }
    }
    return now;
}
long long ask(int now,int l,int r,int k)
{
    if(tre[now].num<=k)
        return tre[now].val;
    if(l==r)
        return 1LL*k*ans[l];
    else
    {
        int mid=(l+r)>>1;
        if(tre[tre[now].lson].num>=k)
            return ask(tre[now].lson,l,mid,k);
        else
            return tre[tre[now].lson].val+ask(tre[now].rson,mid+1,r,k-tre[tre[now].lson].num);
    }
}
int main()
{
    int n,m,x,now;
    int a,b,c,k,gg;
    long long p,pre;
    while(~scanf("%d%d%d%lld",&n,&m,&x,&p))
    {
        for(int i=1;i<=n;i++)
            scanf("%d%d%d",&nums[i].l,&nums[i].r,&nums[i].val);
        sort(nums+1,nums+1+n,cmp);
        cntn=1;
        prenum=nums[1].val;
        ans[1]=nums[1].val;
        nums[1].val=1;
        ql[nums[1].l].push(1);
        qr[nums[1].r+1].push(1);
        for(int i=2;i<=n;i++)
        {
            if(nums[i].val!=prenum)
            {
                cntn++;
                ans[cntn]=nums[i].val;
                prenum=nums[i].val;
            }
            nums[i].val=cntn;
            ql[nums[i].l].push(nums[i].val);
            qr[nums[i].r+1].push(nums[i].val);
        }
        cntt=0;
        root[0]=build(1,cntn);
        for(int i=1;i<=x+1;i++)
        {
            root[i]=root[i-1];
            flag=1;
            while(!ql[i].empty())
            {
                now=ql[i].front();
                ql[i].pop();
                root[i]=change(root[i],1,cntn,now);
            }
            flag=-1;
            while(!qr[i].empty())
            {
                now=qr[i].front();
                qr[i].pop();
                root[i]=change(root[i],1,cntn,now);
            }
        }
        pre=1;
        while(m--)
        {
            if(pre>p)
                gg=2;
            else
                gg=1;
            scanf("%d%d%d%d",&x,&a,&b,&c);
            k=(a*pre+b)%c;
            pre=ask(root[x],1,cntn,k)*gg;
            printf("%lld\n",pre);
        }
    }
    return 0;
}