HDU 4614 Vases and Flowers(Segment Tree and Binary Search)

Description

区间[0, n - 1]，初始值全0，有m次操作。
操作分两类：
1 X Y 从位置X开始寻找Y个0，如果不足Y个，则寻找尽量多的0，并将他们的值全部修改为1，输出第一个和最后一个修改的1的位置。
2 X Y 输出区间[ X , Y ]内1的个数，并将区间内的1修改为0。

Analyze

问题：

①关于找位置没有思路，不知道线段树的val记录什么才能方便找位置

②关于更新：区间[X, Y]内的0更新为1，这一点若是单点修改很费时，咋办

对策：

①val记录区间内1的个数，二分找答案

②不需要单点更新，区间更新即可，这种bool状态非此即彼，将区间内非0的单点修改为1等效于将整个区间所有点置1

Something about Segment Tree

①关于懒惰：

像维护区间和这种要求，int型的lazy实现了两个作用：

1.是否需要down

2.down的值是多大。

而本题是维护“状态”(的区间和)，已知知道down多少(即区间长度)，原则上只用bool型变量标记一下就行，但实际上有三个状态(1.不需要down2.down‘1’3.down’0’)，要用int。

②不用结构体的线段树可以省去建树的过程，但是以后写其他函数形参里都要加两个变量L、R。涉及到子区间先写一下mid。

③update和query很简单的时候可以写在一起。

④val down 后是否需要up：视具体情境。

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50005;

int n, m, ans;
bool change;
int num[N << 2 | 1];
int vis[N << 2 | 1];

void down(int o, int L, int R)
{
    if(~vis[o])
    {
        int mid = (L + R) >> 1;
        num[o << 1] = (vis[o] ? mid - L + 1 : 0);
        num[o << 1 | 1] = (vis[o] ? R - mid : 0);
        vis[o << 1] = vis[o << 1 | 1] = vis[o];
        vis[o] = -1;
    }
}

void UpdateOrQuery(int o, int L, int R, int l, int r, bool val)
{
    if(L > r || R < l)
        return ;
    if(l <= L && R <= r)
    {
        if(val == 0)
            vis[o] = change, num[o] = (change ? R - L + 1 : 0);
        else
            ans += num[o];
        return ;
    }
    if(L == R)
        return ;

    down(o, L, R);
    int mid = (L + R) >> 1;
    UpdateOrQuery(o << 1, L, mid, l, r, val);
    UpdateOrQuery(o << 1 | 1, mid + 1, R, l, r, val);
    num[o] = num[o << 1] + num[o << 1 | 1];
}

int BSearch(int o, int L, int R, int idx)
{
    if(L == R)
        return L;

    down(o, L, R);
    int mid = (L + R) >> 1;
    int tot = mid - L + 1 - num[o << 1];
    if(tot >= idx)
        return BSearch(o << 1, L, mid, idx);
    else
        return BSearch(o << 1 | 1, mid + 1, R, idx - tot);///idx - tot
}

int main()
{
    int _;
    scanf("%d", &_);
    while(_--)
    {
        scanf("%d %d", &n, &m);
        memset(num,  0, sizeof(num));
        memset(vis, -1, sizeof(vis));
        int idx, x, y;
        while(m--)
        {
            scanf("%d %d %d", &idx, &x, &y);
            if(idx == 1)
            {
                ++x;

                ans = 0;
                UpdateOrQuery(1, 1, n, x, n, 1);
                int cnt = n - x + 1 - ans;///How many zeros in [x, n].
                int tot = n - num[1] - cnt;///How many zeros in [1, x - 1].

                if(cnt == 0)
                    cout << "Can not put any one.\n";
                else
                {
                    int first, last;
                    first = BSearch(1, 1, n, tot + 1);
                    if(y > cnt)
                        last = BSearch(1, 1, n, tot + cnt);
                    else
                        last = BSearch(1, 1, n, tot + y);
                    cout << first - 1 << ' ' << last - 1 << '\n';

                    change = 1;
                    UpdateOrQuery(1, 1, n, first, last, 0);
                }
            }
            else
            {
                ++x, ++y;

                ans = 0;
                UpdateOrQuery(1, 1, n, x, y, 1);
                cout << ans << '\n';

                change = 0;
                UpdateOrQuery(1, 1, n, x, y, 0);
            }
        }
        cout << '\n';
    }
    return 0;
}

PE

　 Output one blank line after each test case.