1. 题目

传送门=￣ω￣=

2. 题解

mmp 好久没碰到这么恶心的题目惹！

因为不会整体二分&CDQ 分治，所以就写惹树套树。

怎么说呢=。=

• 此题树套树卡常
• 还卡空间，线段树需要动态开点
• 理论上要开 long long 但开了就 TLE=。=

所以，，，最好的解决方法是用 zkw 线段树常数小

但我不会啊！

而且也不知道 zkw 会不会被卡

但是我们通过查阅 hzw 的题解&luogu 讨论可知：此题可以直接忽略插入负数的操作！

于是就能开 unsigned int 用普通线段树轻松 AC 了。。。

具体做法的话基本和主席树的思路是一样的：

外层是一颗权值线段树，每个节点维护该节点对应的颜色区间内的所有颜色在题目中的数轴上某个区间内的出现次数总和。

也就是每个外层的线段树节点对应了一颗大小为 $n$的线段树，这颗线段树维护的是每个数轴上的区间内该外层节点对应的颜色的出现次数。

然后我们查询一个区间内排序第 $k$的数值（颜色）的话就在外层线段树上二分。

一开始外层线段树的根节点对应颜色区间 $[-n,n]$，那么根节点的左儿子对应的内层线段树查询区间 $[l,r]$的和就能得到在区间 $[l,r]$内比 $\frac{-n+n}{2}$小的值有多少个，从而得到 $\frac{-n+n}{2}$的排名，最后运用类似二分答案的思想，判断该排名是小了还是大了，小了说明答案在根的右儿子里，否则在左儿子里。

最后输出答案即可。

代码：

#include <bits/stdc++.h>
#define LS(a) (a<<1)
#define RS(a) (a<<1|1)
using namespace std;
typedef unsigned int UL;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
struct N{UL s[2],d,tag;}e[20000005];
UL n,m,cnt,A,B,C;
int D;
void pdown(UL a,UL L,UL R)
{
    if(!e[a].s[0])e[a].s[0]=++cnt;
    if(!e[a].s[1])e[a].s[1]=++cnt;
    if(e[a].tag)
    {
        UL l=e[a].s[0],r=e[a].s[1],mid=(L+R)>>1;
        e[l].d+=(mid-L+1)*e[a].tag,e[l].tag+=e[a].tag;
        e[r].d+=(R-mid)*e[a].tag,e[r].tag+=e[a].tag;
        e[a].tag=0;
    }
}
void pup(UL a){e[a].d=e[e[a].s[0]].d+e[e[a].s[1]].d;}
struct segment_tree
{
    UL root;
    void update(UL l,UL r,UL d,UL&a,UL L,UL R)
    {
        if(!a)a=++cnt;
        if(l<=L&&R<=r){e[a].d+=(R-L+1)*d,e[a].tag+=d;return;}
        pdown(a,L,R);
        UL mid=(L+R)>>1;
        if(l<=mid)update(l,r,d,e[a].s[0],L,mid);
        if(r>mid)update(l,r,d,e[a].s[1],mid+1,R);
        pup(a);
    }
    UL query(UL l,UL r,UL a,UL L,UL R)
    {
        if(!a)return 0;
        if(l<=L&&R<=r)return e[a].d;
        pdown(a,L,R);
        UL tot=0,mid=(L+R)>>1;
        if(l<=mid)tot+=query(l,r,e[a].s[0],L,mid);
        if(r>mid)tot+=query(l,r,e[a].s[1],mid+1,R);
        return tot;
    }
}t[20000005];
void work_update()
{
    if(D<0)return;
    D=n-D;
    UL a=1,L=0,R=n,mid;
    while(a)
    {
        t[a].update(B,C,1,t[a].root,1,n),mid=(L+R)>>1;
        if(L==R)break;
        if(D<=mid)a=LS(a),R=mid;
        else a=RS(a),L=mid+1;
    }
}
void work_query()
{
    UL a=1,tmp,L=0,R=n,mid;
    while(L<R)
    {
        mid=(L+R)>>1,tmp=t[LS(a)].query(B,C,t[LS(a)].root,1,n);
        if(tmp>=D)a=LS(a),R=mid;else a=RS(a),L=mid+1,D-=tmp;
    }
    printf("%d\n",n-L);
}
int main()
{
    IN(n),IN(m);
    while(m--)
    {
        IN(A),IN(B),IN(C),IN(D);
        if(A==1)work_update();
        else work_query();
    }
    return 0;
}