BZOJ 3110 「ZJOI2013」K 大数查询

无聊来刷水题……
现在这种树套树模板题我 20min 就搞定了，起不到愉悦身心的效果。

显然的权值线段树套线段树模板。
第一层维护权值，第二层维护位置，这样查询就不用另外二分，而是可以直接在权值线段树上二分。

这个题意有点杀，注意是每个位置都维护一个多重集，支持插入。
如果是加上一个数估计得分块？
反正我不会做。

这样就很水了，如果整体二分的话就相当于把 BIT 换成线段树，区间打标记。
树套树维护方式也是类似的。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 5e4;
int n,m;
struct segnode
{
    long long sum,tag;
    int ls,rs;
} seg[(N << 8) + 10];
struct node
{
    int rt;
    int ls,rs;
} tree[(N << 3) + 10];
int rt;
void update(int l,int r,int &p,int tl,int tr)
{
    static int tot = 0;
    if(!p)
        p = ++tot;
    seg[p].sum += min(r,tr) - max(l,tl) + 1;
    if(l <= tl && tr <= r)
    {
        ++seg[p].tag;
        return ;
    }
    int mid = tl + tr >> 1;
    if(l <= mid)
        update(l,r,seg[p].ls,tl,mid);
    if(r > mid)
        update(l,r,seg[p].rs,mid + 1,tr);
}
long long query(int l,int r,int p,int tl,int tr)
{
    if(!p || (l <= tl && tr <= r))
        return seg[p].sum;
    int mid = tl + tr >> 1;
    long long ret = seg[p].tag * (min(r,tr) - max(l,tl) + 1);
    if(l <= mid)
        ret += query(l,r,seg[p].ls,tl,mid);
    if(r > mid)
        ret += query(l,r,seg[p].rs,mid + 1,tr);
    return ret;
}
void update(int l,int r,int x,int &p,int tl,int tr)
{
    static int tot = 0;
    if(!p)
        p = ++tot;
    update(l,r,tree[p].rt,1,n);
    if(tl == tr)
        return ;
    int mid = tl + tr >> 1;
    x <= mid ? update(l,r,x,tree[p].ls,tl,mid) : update(l,r,x,tree[p].rs,mid + 1,tr);
}
int query(int l,int r,long long k,int p,int tl,int tr)
{
    if(tl == tr)
        return tl;
    long long cnt = query(l,r,tree[tree[p].rs].rt,1,n);
    int mid = tl + tr >> 1;
    return k <= cnt ? query(l,r,k,tree[p].rs,mid + 1,tr) : query(l,r,k - cnt,tree[p].ls,tl,mid);
}
int main()
{
    scanf("%d%d",&n,&m);
    int op,l,r;
    long long k;
    while(m--)
    {
        scanf("%d%d%d%lld",&op,&l,&r,&k);
        if(op == 1)
            update(l,r,k,rt,-n,n);
        else
            printf("%d\n",query(l,r,k,rt,-n,n));
    }
}