2017.5.8训练题

题解

B - A Corrupt Mayor's Performance Art
题意：
有一堵墙，分为n块，开始的时候每块颜色都是2，之后会针对由a到b的色块进行染色，颜色共有30，然后其中会有查询a到b的块由哪些颜色的操作，并且按照升序输出。
思路：
一开始按照区间修改的套路去做，但是很明显的颜色修改不可能覆盖每一块，会有bug，后来看题解知道用状态压缩的方式去表示是否有这种颜色，位运算果然是美妙的。
注意每次build以及update的时候最后要加上pushup。
然后在update中以及query中pushdown永远在递归前面。
代码：

#include <stdio.h>
#include <string.h>
const int mx = 1000005;
int cl[mx << 2];
int add[mx << 2];
bool v[35];
void pushup(int rt)
{
    cl[rt] = cl[rt << 1 | 1] | cl[rt << 1];
}
void pushdown(int rt)
{
    if (add[rt])
    {
        //cl[rt] = add[rt];
        add[rt << 1] = add[rt];
        add[rt << 1|1] = add[rt];
        cl[rt << 1] = add[rt];
        cl[rt << 1|1] = add[rt];
        add[rt] = 0;
    }
}
void build(int rt,int l,int r,int k)
{
    if (l == r)
    {
        cl[rt] = k;
        return;
    }
    int m = (l + r) >> 1;
    build(rt << 1,l,m,k);
    build(rt << 1|1,m+1,r,k);
    pushup(rt);
}
void update(int rt,int ll,int rr,int k,int l,int r)
{
    if (l >= ll && r <= rr)
    {
        cl[rt] = 1 << (k - 1);
        add[rt] = 1 << (k - 1);
        return;
    }
    int m = (l + r) >> 1;
    pushdown(rt);
    if (ll <= m)
    {
        update(rt << 1,ll,rr,k,l,m);
    }
    if (rr > m)
    {
        update(rt << 1|1,ll,rr,k,m+1,r);
    }
    pushup(rt);
}
long long query(int rt,int ll,int rr,int l,int r)
{
    if (l >= ll && r <= rr)
    {
        return cl[rt];
    }
    int m = (l + r) >> 1;
    pushdown(rt);
    long long ret = 0;
    if (ll <= m)
    {
        ret |= query(rt << 1,ll,rr,l,m);
    }
    if (rr > m)
    {
        ret |= query(rt << 1|1,ll,rr,m+1,r);
    }
    return ret;
}
int main()
{
    int m,n;
    while (scanf("%d%d",&n,&m) != EOF)
    {
        if (m == 0 && n == 0) break;
        memset(cl,0,sizeof(cl));
        memset(add,0,sizeof(add));
        memset(v,0,sizeof(v));
        build(1,1,n,2);
        for (int i = 0;i < m;i++)
        {
            char s[5];
            int a,b,c;
            scanf("%s",s);
            if (s[0] == 'P')
            {
                scanf("%d%d%d",&a,&b,&c);
                update(1,a,b,c,1,n);
            }
            if (s[0] == 'Q')
            {
                memset(v,0,sizeof(v));
                scanf("%d%d",&a,&b);
                long long ans = query(1,a,b,1,n);
                for (int j = 0;j < 30;j++)
                {
                    if (ans & (1 << j)) v[j+1] = 1;
                }
                bool flag = 0;
                for (int j = 1;j <= 30;j++)
                {
                    if (v[j])
                    {
                        if (!flag)
                        {
                            printf("%d",j);
                            flag = 1;
                        }
                        else
                            printf(" %d",j);
                    }
                }
                printf("\n");
            }
        }
    }
    return 0;
}

A - Hotel
题意：
一个旅馆有n间房间，最开始这些房间是空的。两种操作，第一种是a人问是否能住进来，这是查询是否有a个连续的房间，若有，则返回起点编号最小的区间的起点，并且把这些房间占用了。第二种操作是将起点为a，区间长度为
b的房间清空。
思路：
线段树的区间合并，非结构体版本，以后就用这个当板子。
主要用了ls,rs,ms三个变量表示当前区间的左连续长度，右连续长度和总连续长度。然后比较重要的函数是pushdown和pushup。特别注意横跨两个区间的长度是要单独讨论的。还得找题来做做。
代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define lson l,mid,rt << 1
#define rson mid + 1,r,rt << 1|1
const int inf = 55555;
int ls[inf << 2],rs[inf << 2],ms[inf << 2];
int add[inf << 2];
void pushdown(int rt,int len)
{
    if (add[rt] != -1)
    {
        add[rt << 1] = add[rt << 1|1] = add[rt];
        ms[rt << 1] = ls[rt << 1] = rs[rt << 1] = add[rt] ? 0 : len - (len >> 1);
        ms[rt << 1|1] = ls[rt << 1|1] = rs[rt << 1|1] = add[rt] ? 0 : (len >> 1);
        add[rt] = -1;
    }
}
void pushup(int rt,int len)
{
    ls[rt] = ls[rt << 1];
    rs[rt] = rs[rt << 1|1];
    if (ls[rt] == len - (len >> 1)) ls[rt] += ls[rt << 1|1];
    if (rs[rt] == (len >> 1))rs[rt] += rs[rt << 1];
    ms[rt] = max(ms[rt << 1],ms[rt << 1|1]);
    ms[rt] = max(ms[rt],rs[rt << 1] + ls[rt << 1|1]);
}
void build(int l,int r,int rt)
{
    add[rt] = -1;
    ls[rt] = rs[rt] = ms[rt] = r - l + 1;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(lson);
    build(rson);
}
void update(int ll,int rr,int k,int l,int r,int rt)
{
    if (l >= ll && r <= rr)
    {
        add[rt] = k;
        ms[rt] = rs[rt] = ls[rt] = k ? 0 : (r - l + 1);
        return;
    }
    pushdown(rt,r - l + 1);
    int mid = (l + r) >> 1;
    if (ll <= mid) update(ll,rr,k,lson);
    if (rr > mid) update(ll,rr,k,rson);
    pushup(rt,r-l+1);
}
int query(int w,int l,int r,int rt)
{
    if (l == r) return l;
    pushdown(rt,r - l + 1);
    int mid = (l + r) >> 1;
    if (ms[rt << 1] >= w)
        return query(w,lson);
    else if (rs[rt << 1] + ls[rt << 1|1] >= w)
        return mid - rs[rt << 1] + 1;
    else
        return query(w,rson);
}
int main()
{
    int m,n;
    scanf("%d%d",&n,&m);
    build(1,n,1);
    while (m--)
    {
        int a,b,c;
        scanf("%d",&a);
        if (a == 1)
        {
            scanf("%d",&b);
            if (ms[1] < b)
                printf("0\n");
            else
            {
                int t = query(b,1,n,1);
                printf("%d\n",t);
                update(t,t+b-1,1,1,n,1);
            }
        }
        else
        {
            scanf("%d%d",&b,&c);
            update(b,b + c - 1,0,1,n,1);
        }
    }
    return 0;
}