JZOJ 3191 「中山市选 2013」花瓶

为什么这么多人暴力过了啊！！！！！
比赛时写了正解的我非常不爽！！！
提供一组 Hack 数据。

第一个其实操作就是找到 $A$ 之后的第一个空花瓶和第 $F$ 个空花瓶，并且把他们修改为非空。
第二个就是修改一段花瓶为空。

我们可以把空花瓶视作 $1$，非空视作 $0$。
那么我们需要的操作相当于找某个数之后的第 $k$ 个 $1$，或者是修改一段数。
如果用线段树来维护，修改其实就是区间赋值的操作，第 $k$ 个 $1$ 也可以类比权值线段树上找第 $k$ 小的方式。
所以我们已经得到了一个 $O(n\log n)$ 的算法。

代码：

#include <cstdio>
#include <algorithm>
#define ls (p << 1)
#define rs (ls | 1)
using namespace std;
const int N = 5e4;
int n,m;
struct node
{
    int sum,tag;
} seg[(N << 2) + 10];
inline void push(int p,int tl,int tr)
{
    if(~seg[p].tag)
    {
        int mid = tl + tr >> 1;
        seg[ls].sum = seg[p].tag * (mid - tl + 1),seg[ls].tag = seg[p].tag;
        seg[rs].sum = seg[p].tag * (tr - mid),seg[rs].tag = seg[p].tag;
        seg[p].tag = -1;
    }
}
void update(int l,int r,int k,int p,int tl,int tr)
{
    if(l <= tl && tr <= r)
    {
        seg[p].sum = k * (tr - tl + 1),seg[p].tag = k;
        return ;
    }
    push(p,tl,tr);
    int mid = tl + tr >> 1;
    if(l <= mid)
        update(l,r,k,ls,tl,mid);
    if(r > mid)
        update(l,r,k,rs,mid + 1,tr);
    seg[p].sum = seg[ls].sum + seg[rs].sum;
}
int query(int l,int r,int p,int tl,int tr)
{
    if(l <= tl && tr <= r)
        return seg[p].sum;
    push(p,tl,tr);
    int mid = tl + tr >> 1;
    int ret = 0;
    if(l <= mid)
        ret += query(l,r,ls,tl,mid);
    if(r > mid)
        ret += query(l,r,rs,mid + 1,tr);
    return ret;
}
int query(int k,int p,int tl,int tr)
{
    if(tl == tr)
        return tl;
    push(p,tl,tr);
    int mid = tl + tr >> 1;
    if(k <= seg[ls].sum)
        return query(k,ls,tl,mid);
    else
        return query(k - seg[ls].sum,rs,mid + 1,tr);
}
int main()
{
    scanf("%d%d",&n,&m),update(1,n,1,1,1,n);
    int op,x,y;
    while(m--)
    {
        scanf("%d%d%d",&op,&x,&y);
        if(op == 1)
        {
            ++x;
            if(!query(x,n,1,1,n))
                puts("Can not put any one.");
            else
            {
                int k = x > 1 ? query(1,x - 1,1,1,n) : 0;
                int l = query(min(k + 1,seg[1].sum),1,1,n);
                int r = query(min(k + y,seg[1].sum),1,1,n);
                update(l,r,0,1,1,n);
                printf("%d %d\n",l - 1,r - 1);
            }
        }
        else
            ++x,++y,printf("%d\n",y - x + 1 - query(x,y,1,1,n)),update(x,y,1,1,1,n);
    }
}