@[p_b_p_b](/space/show?uid=76481) %%%数据结构之王
~~（别问我为什么哪个讨论都有我）~~
by AThousandSuns @ 2018-05-06 11:37:44
@[AThousandSuns](/space/show?uid=72118) 反膜一发NTT、FFT巨佬%%%
by p_b_p_b @ 2018-05-06 11:41:42
我还是太菜了，您初一巨佬才是神犇
by p_b_p_b @ 2018-05-06 11:42:49
@[p_b_p_b](/space/show?uid=76481) 您还AK了GDOI呢
by AThousandSuns @ 2018-05-06 11:47:16
@[AThousandSuns](/space/show?uid=72118)
伏地魔，我才二等奖，太菜了
by 爱喝敌敌畏 @ 2018-05-06 11:58:16
@[敌敌畏](/space/show?uid=65602) 额……你说的是哪场考试？GDOI3=的蒟蒻%%%dalao
by AThousandSuns @ 2018-05-06 12:01:30
@[敌敌畏](/space/show?uid=65602) GDOI180，太强，我才145
by AThousandSuns @ 2018-05-06 12:02:53
嗯……所以说这还是个问问题的帖吗……该不会成吹水帖了吧……
by AThousandSuns @ 2018-05-06 12:03:38
@[p_b_p_b](/space/show?uid=76481) $q$中的元素可能爆$int$
by Takanashi_Rikka @ 2018-05-06 12:04:25
@[Takanashi_Rikka](/space/show?uid=93507) 谢谢，更新了，但还是WA
而且这么慢是什么鬼。。。
```cpp
#include<bits/stdc++.h>
const int sz=(5e4+5);
const int tree=sz*400;
typedef long long ll;
using namespace std;
int a[sz],tag[tree],rt[sz<<2],ls[tree],rs[tree];
ll q[sz],tr[tree];
int type[sz],ql[sz],qr[sz],totn;
int cnt,n,m;
#define lson ls[p],l,mid
#define rson rs[p],mid+1,r
#define now p,l,r
inline ll read()
{
register ll ret=0,f=1;
register char ch=getchar();
while (ch>'9'||ch<'0')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch<='9'&&ch>='0') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
void pushdown(int p,int l,int r)
{
int t=tag[p],mid=(l+r)>>1;
if (!t) return;
tag[p]=0;
if (!ls[p]) ls[p]=++cnt;
if (!rs[p]) rs[p]=++cnt;
tag[ls[p]]+=t;
tr[ls[p]]+=t*(mid-l+1);
tag[rs[p]]+=t;
tr[rs[p]]+=t*(r-mid);
}
void modify(int &p,int l,int r,int x,int y)
{
if (!p) p=++cnt;
if (x<=l&&r<=y)
{
tag[p]++;tr[p]+=r-l+1;
return;
}
pushdown(now);
int mid=(l+r)>>1;
if (x<=mid) modify(lson,x,y);
if (y>mid) modify(rson,x,y);
tr[p]=tr[ls[p]]+tr[rs[p]];
}
ll sum(int p,int l,int r,int x,int y)
{
if (!p) return 0;
if (x<=l&&r<=y) return tr[p];
pushdown(now);
int mid=(l+r)>>1;
ll ret=0;
if (x<=mid) ret+=sum(lson,x,y);
if (y>mid) ret+=sum(rson,x,y);
return ret;
}
void add(int p,int l,int r,int x,int y,int k)
{
modify(rt[p],1,n,x,y);
if (l==r) return;
int mid=(l+r)>>1;
if (k<=mid) add(p<<1,l,mid,x,y,k);
else add(p<<1|1,mid+1,r,x,y,k);
}
int query(int p,int l,int r,int x,int y,ll k)
{
if (l==r) return a[l];
int mid=(l+r)>>1;
int t=sum(rt[p<<1|1],1,n,x,y);
if (t<k) return query(p<<1,l,mid,x,y,k-t);
else return query(p<<1|1,mid+1,r,x,y,k);
}
int main()
{
n=read();m=read();
register ll x,y,z,opt,i,tot=0;
for (i=1;i<=m;i++)
{
type[i]=read(),ql[i]=read(),qr[i]=read(),q[i]=read();
if (type[i]==1) a[++tot]=q[i];
}
sort(a+1,a+tot+1);
tot=unique(a+1,a+tot+1)-a-1;
for (i=1;i<=n;i++) if (type[i]&1) q[i]=lower_bound(a+1,a+tot+1,q[i])-a;
for (i=1;i<=m;i++)
{
x=ql[i];y=qr[i];z=q[i];opt=type[i];
if (opt&1) add(1,1,tot,x,y,z);
else printf("%d\n",query(1,1,tot,x,y,z));
}
}
```
by p_b_p_b @ 2018-05-06 12:45:28