注意操作 $1$ 是在区间的每个位置加入一个数，不是加上一个值
相当于每个位置维护的是一个集合
显然树套树
一开始想的是区间线段树套权值线段树
发现这样询问区间第 $K$ 大时就要先二分答案再用 $O(log^2_n)$ 时间查询
那么单次询问的复杂度就有 $O(log^3_n)$ ，显然不行
考虑权值线段树套区间线段树
单次插入复杂度还是 $O(log^2_n)$，询问时只要在权值线段树上二分就行
那么单次操作复杂度就是 $O(log^2_n)$
据说此题很卡常，为了防止我的大常数导致 $GG$ 所以学了一下线段树的标记用久化
简单说就是标记不下传，只要询问时把经过节点的标记加进来一起计算贡献，代码不难想
因为空间问题所以内层的区间线段树要动态开点
因为插入的数可能为负，所以要离散化，注意 $long long$ !
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline ll readll() { ll x=0; int f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e5+7,M=2e7+7; int n,m,cnt,A[N],T; int rt[N],L[M],R[M],tag[M];//区间线段树的数组，根节点，左儿子，右儿子，永久标记 ll sum[M];//区间线段树数组，区间和 int ql,qr; ll res; void add(int &o,int l,int r)//区间加1 { if(!o) o=++cnt;//动态开点 sum[o]+= max( min(r,qr)-max(l,ql)+1 ,0) ;//因为永久标记所以要这样更新sum if(l>=ql&&r<=qr) { tag[o]++; return; }//注意我的tag是给儿子的，要先更新sum int mid=l+r>>1; if(ql<=mid) add(L[o],l,mid); if(qr>mid) add(R[o],mid+1,r); } void query(int o,int l,int r,int tot)//区间求和,tot维护当前经过节点的tag的和 { if(l>=ql&&r<=qr) { res+=sum[o]+1ll*(r-l+1)*tot; return; }//更新res int mid=l+r>>1; if(ql<=mid) query(L[o],l,mid,tot+tag[o]); if(qr>mid) query(R[o],mid+1,r,tot+tag[o]); } int POS,RES; ll K; void ADD(int o,int l,int r)//权值线段树插入 { add(rt[o],1,n); if(l==r) return; int mid=l+r>>1; if(POS<=mid) ADD(o<<1,l,mid); else ADD(o<<1|1,mid+1,r); } void QUERY(int o,int l,int r)//权值线段树处理询问 { if(l==r) { RES=A[l]; return; } int mid=l+r>>1; res=0; query(rt[o<<1|1],1,n,0);//注意优先走大的！ if(res<K) { K-=res; QUERY(o<<1,l,mid); } else QUERY(o<<1|1,mid+1,r); } int op[N],dl[N],dr[N],dk[N];//读入的数据 int main() { //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); n=read(),m=read(); for(int i=1;i<=m;i++) { op[i]=read(),dl[i]=read(),dr[i]=read(),dk[i]=readll(); if(op[i]==1) A[++T]=dk[i]; } sort(A+1,A+T+1); T=unique(A+1,A+T+1)-A-1;//离散化 for(int i=1;i<=m;i++) if(op[i]==1) dk[i]=lower_bound(A+1,A+T+1,dk[i])-A; for(int i=1;i<=m;i++) { ql=dl[i],qr=dr[i]; if(op[i]==1) { POS=dk[i]; ADD(1,1,T); } else { K=dk[i]; QUERY(1,1,T); printf("%d ",RES); } } return 0; }