题目描述

题面不长自己看啦XD

思路

注意到查询第 $k$ 大这个操作可以转化为 是否有 $k$ 个比 $x$ 大的数 这样一个判定问题。单个这样的判定问题能够二分解决，多个就可以考虑——

整体二分：

简单讲就是把所有插入查询全看成操作放在一起，然后同时二分操作和答案值域，值域直接取 $mid$ ，操作通过下面的方式分成两半。

设当前二分到的值域是 $[l,r]$ ，$mid=(l+r)/2$ ，二分到操作区间是 $[ql,qr]$ 。称将操作分成两边的两个队列为左队列和右队列。

对于加入操作，如果 $val>mid$ 就区间加一，因为这对“是否有【】个比 $mid$ 大的数”产生了贡献，然后放到左队列；否则就放到右边队列。

对于查询操作，区间求和，如果比所要求的值大说明比 $mid$ 大的数太多了，真正的答案一定在 $mid$ 右边（就是比它大），所以放到左队列（这边我是按照实现讲的……稍微有点绕）；否则放到右边队列。

区间求和和区间加都能线段树实现。代码比树套树好写很多。

//Author: AutomaticLove
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define db double
using namespace std;
ll read()
{
    ll x=0,w=1; char ch=getchar();
    while ( ch>'9' || ch<'0' ) { if ( ch=='-' ) w=-1; ch=getchar(); }
    while ( ch<='9' && ch>='0' ) x=x*10+ch-'0',ch=getchar();
    return x*w;
}

#define ls pos<<1
#define rs pos<<1|1
const int N=1e5+10;
const ll INF=2e18;
struct Node{ ll lzy,sum; }tr[N<<2];
void Pushdown( int pos,int l,int r )
{
    if ( !tr[pos].lzy ) return;
    int mid=(l+r)>>1;
    tr[ls].lzy+=tr[pos].lzy; tr[rs].lzy+=tr[pos].lzy;
    tr[ls].sum+=tr[pos].lzy*(mid-l+1);
    tr[rs].sum+=tr[pos].lzy*(r-mid);
    tr[pos].lzy=0;
}
void Build( int pos,int l,int r )
{
    tr[pos].lzy=tr[pos].sum=0;
    if ( l==r ) return;
    int mid=(l+r)>>1;
    Build(ls,l,mid); Build(rs,mid+1,r);
}
void Modify( int pos,int l,int r,int ql,int qr,ll v )
{
    if ( ql<=l && r<=qr ) { tr[pos].lzy+=v; tr[pos].sum+=v*(r-l+1); return; }
    Pushdown(pos,l,r); int mid=(l+r)>>1;
    if ( ql<=mid ) Modify(ls,l,mid,ql,qr,v);
    if ( qr>mid ) Modify(rs,mid+1,r,ql,qr,v);
    tr[pos].sum=tr[ls].sum+tr[rs].sum;
}
ll Query( int pos,int l,int r,int ql,int qr )
{
    if ( ql<=l && r<=qr ) return tr[pos].sum;
    Pushdown(pos,l,r);
    int mid=(l+r)>>1; ll res=0;
    if ( ql<=mid ) res+=Query(ls,l,mid,ql,qr);
    if ( qr>mid ) res+=Query(rs,mid+1,r,ql,qr);
    return res;
}
int n,m,tot=0;
ll ans[N];
struct Operation{ int tim,opt,l,r; ll val; }q[N],le[N],ri[N];

void Solve( int ql,int qr,ll l,ll r )
{
    if ( ql>qr || l>r ) return;
    if ( l==r )
    {
        for ( int i=ql; i<=qr; i++ ) 
            if ( q[i].opt==2 ) ans[q[i].tim]=l;
        return;
    }
    ll mid=(l+r)>>1; int lcnt=0,rcnt=0;
    for ( int i=ql; i<=qr; i++ )
    {
        if ( q[i].opt==1 )   //插入操作
        {
            if ( q[i].val>mid ) Modify(1,1,n,q[i].l,q[i].r,1),le[++lcnt]=q[i];
            else ri[++rcnt]=q[i];
        }
        else    //查询操作
        {
            ll tmp=Query(1,1,n,q[i].l,q[i].r);
            if ( tmp>=q[i].val ) le[++lcnt]=q[i];
            else q[i].val-=tmp,ri[++rcnt]=q[i];
        }
    }
    for ( int i=1; i<=lcnt; i++ )
        if ( le[i].opt==1 && le[i].val>mid ) Modify(1,1,n,le[i].l,le[i].r,-1);
    for ( int i=ql; i<ql+lcnt; i++ ) q[i]=le[i-ql+1];
    for ( int i=ql+lcnt; i<=qr; i++ ) q[i]=ri[i-ql-lcnt+1];
    if ( lcnt ) Solve(ql,ql+lcnt-1,mid+1,r); 
    if ( rcnt ) Solve(ql+lcnt,qr,l,mid);
}

int main()
{
//freopen( "exam.in","r",stdin );

    n=read(); m=read(); Build(1,1,n); 
    for ( int i=1; i<=m; i++ )
    {
        int opt=read(),l=read(),r=read(); ll v=read();
        q[i]=Operation{(opt==2)?++tot:0,opt,l,r,v};
    }

    Solve(1,m,-n,n);

    for ( int i=1; i<=tot; i++ ) printf("%lld\n",ans[i] );

    return 0;
}