[ZJOI2013][luoguP3332]K大数查询

奇怪的区间第k大~

题目描述

有N个位置，M个操作。操作有两种，每次操作是：
1 l r c：表示在第l个位置到第r个位置，每个位置加上一个数c
2 l r c：表示询问从第l个位置到第r个位置，第C大的数是多少。
注意：这个数组的每个元素都是一个栈，这里的“加上”指的是在某个位置压进去一个新数
其中，\(n,m\le 50000\) ,对于1操作，\(|c|\le n\),对于2操作，c在long long范围内

题解：

大致思路

我不会整体二分，所以我采用了树套树。
这个第k小看起来很不舒服，所以我们统计一下区间中数的总数，转成第k大就好了。

回忆一下\(O(n\lg^3n)\)的区间第k大做法，我们用外层线段树维护位置，内层线段树维护数值。查询的时候二分得到答案。由于外面一层没有给我们什么有用的信息，所以我们只能采用近乎智障的二分...而且还不能区间修改...

真的只能这样吗？

考虑实际上我们维护的还是一种偏序关系，位置和值的限制实际上是等价的。我们完全可以让外层的线段树维护值域，内层的线段树（平衡树）维护位置.而且，这样的话，我们自动拥有了值域线段树具有的二分性质，不用在外面套上一个傻乎乎的二分了。。 具体来说，我们在外层线段树（值域）递归，每一层中，使用内层线段树查询左子树中落在\([l..r]\)之间的数的个数cnt。如果\(k\le cnt\)，进入左子树；反之，进入右子树。到叶子的时候返回值。

考虑区间修改，我们只需要把平衡树换成线段树就好了——这样我们就可以打lazy标记辣！于是就做完了！

撒花！

几个优化的小技巧：

• 内层线段树使用动态开点，将空间降至\(O(n\lg^2 n)\)
• 内层线段树可以标记永久化，减小常数。 > “永久化的标记就是值” --zkw《统计的力量》
• 标记永久化：我们不再下传标记，而是改为查询时经过每个节点都累计其具有的标记，最后递归访问终止节点的时候计算这些标记造成的贡献。

其实树套树也不是多慢嘛，就比整体二分慢了一倍
写个快读是不是就差不多了啊

代码：

#include <cstdio>
#include <cstring>
#include <climits>
#include <cstdint>
#include <algorithm>

const int maxn=5e4+1000;

int bl[maxn],br[maxn],cntl,cntr;

template<class T>inline T max(T a,T b){return a<b?b:a;}
template<class T>inline T min(T a,T b){return a<b?a:b;}

struct Node
{
    int ls,rs;
    int64_t siz,tag;
}T[maxn*300];

int root[maxn<<3],cnt;

inline int _modify(int L,int R,int rt,int l,int r) // 内层线段树的插入操作
{
    if (!rt) rt=++cnt;
    T[rt].siz+=min(R,r)-max(L,l)+1;
    if (L<=l && R>=r)
        return T[rt].tag++,rt;
    int mid=(l+r)>>1;
    if (L<=mid) T[rt].ls=_modify(L,R,T[rt].ls,l,mid);
    if (R> mid) T[rt].rs=_modify(L,R,T[rt].rs,mid+1,r);
    return rt;
}

inline int64_t _query(int L,int R,int rt,int l,int r,int64_t add=0) // 内层线段树查询size
{
    if (!rt) rt=++cnt;
    if (L<=l && R>=r) return T[rt].siz+add*(r-l+1);
    int mid=(l+r)>>1;
    int64_t tot=0;
    if (L<=mid) tot+=_query(L,R,T[rt].ls,l,mid,add+T[rt].tag);
    if (R> mid) tot+=_query(L,R,T[rt].rs,mid+1,r,add+T[rt].tag);
    return tot;
}

inline void modify(int x,int L,int R,int l,int r,int o,int n) // 外层线段树的修改
{
    root[o]=_modify(L,R,root[o],1,n);
    if (l==r) return;
    int mid=(l+r)>>1;
    if (x<=mid) modify(x,L,R,l,mid,o<<1,n);
    else modify(x,L,R,mid+1,r,o<<1|1,n);
}

inline int query(int L,int R,int64_t k,int l,int r,int o,int n) // 外层线段树的查询
{
    if (l==r) return l;
    int mid=(l+r)>>1;
    int64_t rnk=_query(L,R,root[o<<1],1,n,0);
    // printf("%d %d %d %d %d\n",L,R,l,mid,rnk);
    if (k<=rnk) return query(L,R,k,l,mid,o<<1,n);
    else return query(L,R,k-rnk,mid+1,r,o<<1|1,n);
}

int64_t sumv[maxn<<2],tag[maxn<<2];
#define ls l,mid,o<<1
#define rs mid+1,r,o<<1|1

inline void pushdown(int o,int len)
{
    sumv[o<<1]+=tag[o]*(len-(len>>1));
    sumv[o<<1|1]+=tag[o]*(len>>1);
    tag[o<<1]+=tag[o];tag[o<<1|1]+=tag[o];
    tag[o]=0;
}

inline void pushup(int o){sumv[o]=sumv[o<<1]+sumv[o<<1|1];}

inline void add(int L,int R,int c,int l,int r,int o)
{
    if (L<=l && R>=r) return (void)(sumv[o]+=c*(r-l+1),tag[o]+=c);
    pushdown(o,r-l+1);
    int mid=(l+r)>>1;
    if (L<=mid) add(L,R,c,ls);
    if (R> mid) add(L,R,c,rs);
    pushup(o);
}

inline int64_t query(int L,int R,int l,int r,int o)
{
    if (L<=l && R>=r) return sumv[o];
    pushdown(o,r-l+1);
    int mid=(l+r)>>1;
    int64_t tot=0;
    if (L<=mid) tot+=query(L,R,ls);
    if (R> mid) tot+=query(L,R,rs);
    return tot;
}

inline int query(int L,int R,int64_t k,int n)
{
    k=query(L,R,1,n,1)-k+1;
    // printf("%d\n",k);
    return query(L,R,k,1,n*2+2,1,n)-n-1;
}

inline void modify(int l,int r,int c,int n)
{
    add(l,r,1,1,n,1);
    modify(c+n+1,l,r,1,n*2+2,1,n);
}

int main()
{
    // freopen("testdata3332.in","r",stdin);
    int n,m;
    scanf("%d%d",&n,&m);
    int64_t c;
    for (int i=1,a,b,opt;i<=m;++i)
    {
        scanf("%d%d%d%lld",&opt,&a,&b,&c);
        if (opt&1) modify(a,b,c,n);
        else printf("%d\n",query(a,b,c,n));
    }
}