hdu - 4614

Posted by WildCow on April 20, 2018

Vases and Flowers

Time Limit: 4000/2000 MS (Java/Others)
Memory Limit: 65536/32768 K (Java/Others)

Description

Alice is so popular that she can receive many flowers everyday. She has N vases numbered from 0 to N-1. When she receive some flowers, she will try to put them in the vases, one flower in one vase. She randomly choose the vase A and try to put a flower in the vase. If the there is no flower in the vase, she will put a flower in it, otherwise she skip this vase. And then she will try put in the vase A+1, A+2, …, N-1, until there is no flower left or she has tried the vase N-1. The left flowers will be discarded. Of course, sometimes she will clean the vases. Because there are too many vases, she randomly choose to clean the vases numbered from A to B(A <= B). The flowers in the cleaned vases will be discarded.

Input

The first line contains an integer T, indicating the number of test cases. For each test case, the first line contains two integers N(1 < N < 50001) and M(1 < M < 50001). N is the number of vases, and M is the operations of Alice. Each of the next M lines contains three integers. The first integer of one line is K(1 or 2). If K is 1, then two integers A and F follow. It means Alice receive F flowers and try to put a flower in the vase A first. If K is 2, then two integers A and B follow. It means the owner would like to clean the vases numbered from A to B(A <= B).

Output

For each operation of which K is 1, output the position of the vase in which Alice put the first flower and last one, separated by a blank. If she can not put any one, then output ‘Can not put any one.’. For each operation of which K is 2, output the number of discarded flowers.

Output one blank line after each test case.

Sample Input

2
10 5
1 3 5
2 4 5
1 1 8
2 3 6
1 8 8
10 6
1 2 5
2 3 4
1 0 8
2 2 5
1 4 4
1 2 3

Sample Output

3 7
2
1 9
4
Can not put any one.

2 6
2
0 9
4
4 5
2 3


没想到我的博客这么久了居然这个时候才更新第一道分块的题解
这题用分块。。。其实并不好做
还是硬刚过去了

给你一个初始状态全为 0 ,由 0 和 1 组成的序列
两种操作

  • 区间求和然后再赋值为 0
  • 给你一个点 x 和一个长度 len,你需要从 x 开始**小于等于 len 但大于等于 1 **个 0 变成 1,如果一个 0 都不能变成 1,输出蜜汁字符串

分块看起来很好写
实则细节爆炸

我们需要维护每个块的大小 mb(因为最后一个块大小不确定,当然也可以通过特判直接弄掉)
每个块内 1 的个数 cnt
每个块的赋值延迟标记 lazy(-1 — 不操作, 0 — 区间赋值 0 , 1 — 区间赋值 1)

然后对于更新操作
我们先找到从 x 开始第一个 0 的位置作为起点
怎么找呢
先暴力找 x 所在的不完整的块
如果找不到
那么遍历接下来的块
暴力找第一个 cnt != mb 的块
然后再暴力那个块中的第一个 0 的位置作为起点

然后开始找终点
先说一下大致的操作
先暴力更新起点所在的块
对于接下来每个块
如果 cnt < len

那就把 lazy 标记打上 1(实际上这个方法是错的,具体下面讲)
然后 len -= cnt
如果 cnt > len
那就再暴力更新那个块
所以我们显而易见得到第一个结论:

  • 如果最后能正好更新 len 个 0,那么最后一个的位置肯定会在我们暴力更新块的时候找到,所以我们暴力更新块的时候需要维护最后一个更新的点的位置

然后我们来讨论更新的 0 的数目小于 len 的情况,那么最后一个更新的点,肯定在完整更新的块内,所以我们需要维护最后一个更新的块的标号
得到第二个结论:

  • 我们在更新块的时候,需要用 last 记录最后一个更新的块的标号,这样如果最后更新的 0 的个数小于 len,就可以再倒着遍历最后一个更新的块,找到最后一个 0 的位置

然后我们发现了一个新的问题,我们暴力不完整的块的时候,我们需要 down 操作,这样在倒着遍历最后一个更新的块寻找最后一个 0 的时候,我们先 down,直接就把那个块内的元素全变成 1 了,防止这种情况,
有第三个结论:

  • 我们发现一个块该被完整更新的时候,不应该马上把这个块的 lazy 变成 1,而是把上一个完整更新的块的 lazy 变成1

求和操作很好写
直接常规搓就好了

切出来以后心满意足
瞎优化一番后达到了 202ms
HDU 上第二快


#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int ma[N];
int mb[N];
int lazy[N];
int bl[N];
int l[N];
int r[N];
int cnt[N];     /// 1 - cnt
int block;
int num;
int be;
int x, a, b;
int t, q;
int n, m;

inline char _getchar()
{
    static const int BUFSIZE = 100001 ;
    static char  buf[BUFSIZE] ;
    static char  *psta=buf, *pend=buf ;
    if (psta >= pend){
        psta = buf;
        pend = buf + fread(buf,1,BUFSIZE,stdin);
        if (psta >= pend){
            return -1;
        }
    }
    return *psta++;
}
inline int read(int &x)
{
    x=0;
    int f=1;char ch=_getchar();
    while((ch<'0'||ch>'9')&&~ch){if(ch=='-')f=-1;ch=_getchar();}
    if (ch==-1)return -1;
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=_getchar();}
    x*=f;
    return 1;
}

void build()
{
    memset(cnt, 0, sizeof(cnt));
    memset(ma, 0, sizeof(ma));
    memset(lazy, -1, sizeof(lazy));
    block = sqrt(n);
    num = n / block;
    if(n % block){
        num ++;
    }
    for(int i = 1; i <= num; ++ i){
        cnt[i] = 0;
        l[i] = (i - 1) * block + 1;
        r[i] = i * block;
        mb[i] = block;
    }
    r[num] = n;
    mb[num] = r[num] - l[num] + 1;
    for(int i = 1; i <= n; ++ i){
        bl[i] = (i - 1) / block + 1;
    }
}

void down(int x)
{
    if(lazy[x] != -1){
        for(int i = l[x]; i <= r[x]; i ++){
            ma[i] = lazy[x];
        }
        lazy[x] = -1;
    }
}

int update(int x, int li)
{
    int pre;
    int last;
    int mark;

    if(!li){
        return x;
    }
    mark = 0;
    t = bl[x];
    last = t;
    for(int i = x; i <= r[t]; ++ i){
        if(!ma[i]){
            ma[i] = 1;
            pre = i;
            li --;
            cnt[t] ++;
            if(!li){
                return i;
            }
        }
    }
    //printf("li = %d\n", li);
    for(int i = t + 1; i <= num; ++ i){
        //printf("i = %d  cnt = %d\n", i, cnt[i]);
        if(cnt[i] == mb[i]){
            continue;
        }
        if(!li){
            break;
        }
        mark = 1;
        if(mb[i] - cnt[i] <= li){
            if(last != t){
                lazy[last] = 1;
            }
            last = i;
            li -= (mb[i] - cnt[i]);
            cnt[i] = mb[i];
        }
        else{
            down(i);
            if(last != t){
                lazy[last] = 1;
            }
            for(int j = l[i]; j <= r[i]; ++ j){
                if(!ma[j]){
                    mark = 1;
                    ma[j] = 1;
                    pre = j;
                    li --;
                    cnt[i] ++;
                    if(!li){
                        return j;
                    }
                }
            }
        }
    }
    if(!mark){
        return pre;
    }
    else{
        down(last);
        lazy[last] = 1;
        for(int i = r[last]; i >= l[last]; -- i){
            //cout << ma[i] << endl;
            if(!ma[i]){
                return i;
            }
        }
    }
}

int main()
{
    int ncase;

    read(ncase);
    while(ncase --){
        read(n);
        read(m);
        build();
        for(int i = 0; i < m; ++ i){
//            cout << "********" << endl;
//            for(int i = 1; i <= num; i ++){
//                printf("%d - %d - %d\n", i, cnt[i], lazy[i]);
//            }
//            for(int i = 1; i <= n; i ++){
//                printf("%d ", ma[i]);
//            }
//            printf("\n");
//            cout << "********" << endl;
            read(x);
            read(a);
            read(b);
            if(x == 1){
                be = -1;
                a ++;
                t = bl[a];
                down(t);
                for(int i = a; i <= r[t]; ++ i){
                    //cout << i << endl;
                    if(!ma[i]){
                        be = i;
                        break;
                    }
                }
                if(be == -1){
                    for(int i = t + 1; i <= num; ++ i){
                        if(cnt[i] != mb[i]){
                            down(i);
                            for(int j = l[i]; j <= r[i]; ++ j){
                                if(!ma[j]){
                                    be = j;
                                    break;
                                }
                            }
                            break;
                        }
                    }
                }
                if(be == -1){
                    printf("Can not put any one.\n");
                }
                else{
                    printf("%d %d\n", be - 1, update(be, b) - 1);
                }
            }
            else{
                int ans;

                a ++;
                b ++;
                t = bl[a];
                q = bl[b];
                ans = 0;
                down(t);
                down(q);
                if(t == q){
                    for(int i = a; i <= b; ++ i){
                        if(ma[i]){
                            ma[i] = 0;
                            ans ++;
                            cnt[t] --;
                        }
                    }
                }
                else{
                    for(int i = a; i <= r[t]; ++ i){
                        if(ma[i]){
                            ma[i] = 0;
                            ans ++;
                            cnt[t] --;
                        }
                    }
                    for(int i = t + 1; i < q; ++ i){
                        ans += cnt[i];
                        cnt[i] = 0;
                        lazy[i] = 0;
                    }
                    for(int i = l[q]; i <= b; ++ i){
                        if(ma[i]){
                            //cout << "hh" << endl;
                            ma[i] = 0;
                            ans ++;
                            cnt[q] --;
                        }
                    }
                }
                printf("%d\n", ans);
            }
        }
        printf("\n");
    }

    return 0;
}