RT，码的是 $O(n \sqrt {n \log n})$ 的分散层叠，但是现在直接交上去全 T 是个什么鬼啊。

顺便求哪个神仙来实现精细一下这道题的 $O(n \sqrt {n \log n})$ ，我已经卡不动了……

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int Len = 1e5 + 5 , SIZE = 1205 , D = 3 , Inf = 2e9 + 1;
int n,m;
struct node
{
	int lrank,rrank,belong;
	node(){lrank = 0 , rrank = 0 , belong = 0;}
	node(const int LRANK,const int RRANK,const int BELONG){lrank = LRANK , rrank = RRANK , belong = BELONG;}
}num[Len << 1];
int ans,val[Len << 1],L[SIZE],R[SIZE],pos[Len],add[SIZE],Lpos[SIZE << 1],Rpos[SIZE << 1],sz[SIZE << 1],len[SIZE],lst = 1,t,sizt;
struct Node
{
	int val,pos;	
	Node(){val = 0 , pos = 0;}
	Node(const int VAL , const int POS){val = VAL , pos = POS;}
}a[Len],Used[SIZE][2];
int lens[2],lenss,Usedto[SIZE << 1];
bool cmp(Node x,Node y){return x.val < y.val;}
int ls(int x){return x << 1;}
int rs(int x){return x << 1 | 1;}
inline void push_up(int p)
{
	int i = Lpos[ls(p)] , j = Rpos[rs(p)] , idx = Lpos[p];
	while(i - Lpos[ls(p)] + 1 <= sz[ls(p)] && j - Lpos[rs(p)] + 1 <= sz[rs(p)])
	{
		if(val[i] + add[num[i].belong] < val[j] + add[num[j].belong]) 
		{
			val[idx] = val[i];
			num[idx ++] = node(i , j , num[i].belong);
			i += D;
		}
		else
		{
			val[idx] = val[j];
			num[idx ++] = node(i , j , num[j].belong);
			j += D;
		}
	}
	while(i - Lpos[ls(p)] + 1 <= sz[ls(p)])
	{
		val[idx] = val[i];
		num[idx ++] = node(i , Rpos[rs(p)] , num[i].belong);
		i += D;
	}
	while(j - Rpos[rs(p)] + 1 <= sz[rs(p)])
	{
		val[idx] = val[j];
		num[idx ++] = node(Rpos[ls(p)] , j , num[i].belong);
		j += D; 
	}
	val[idx] = Inf;
	num[idx ++] = node(Rpos[ls(p)] , Rpos[rs(p)] , 0);
	return;
}
void build(int p,int l,int r)
{
	if(l == r)
	{
		sz[p] = len[l] , Lpos[p] = lst , Rpos[p] = lst + sz[p] - 1;
		for(int i = L[l] ; i <= R[l] ; i ++) 
		{
			num[lst] = node(lst , 0 , l);
			val[lst ++] = a[i].val;
		}
		return;
	}
	int mid = (l + r) >> 1;
	build(ls(p) , l , mid) , build(rs(p) , mid + 1 , r);
	sz[p] = (sz[ls(p)] - 1) / D + 1 , (sz[rs(p)] - 1) / D + 1;
	Lpos[p] = lst , Rpos[p] = lst + sz[p];
	push_up(p);
	lst = lst + sz[p] + 1;
} 
inline void maintain(int p,int l,int LL)
{
	int idx = Lpos[p] , i = 1 , j = 1 , now = LL;
	while(i <= lens[0] && j <= lens[1])
	{
		if(Used[i][0].val < Used[j][1].val)
		{
			a[now ++] = Used[i][0];
			num[idx] = node(idx , 0 , now - 1);
			val[idx ++] = Used[i][0].val;
			i ++;
		}
		else 
		{
			a[now ++] = Used[j][1];
			num[idx] = node(idx , 0 , now - 1);
			val[idx ++] = Used[j][1].val;
			j ++;
		}
	}
	while(i <= lens[0]) 
	{
		a[now ++] = Used[i][0];
		num[idx] = node(idx , 0 , now - 1);
		val[idx ++] = Used[i][0].val;
		i ++;
	}
	while(j <= lens[1])
	{
		a[now ++] = Used[j][1];
		num[idx] = node(idx , 0 , now - 1);
		val[idx ++] = Used[j][1].val;
		j ++;
	}
}
void update(int p,int l,int r,int idx,int LL,int RR,int Add)
{
	if(l == r) 
	{
		lens[0] = lens[1] = 0;
		for(int i = L[l] ; i <= R[l] ; i ++) 
		{
			if(LL <= a[i].pos && a[i].pos <= RR) Used[++ lens[0]][0] = Node(a[i].val + Add , a[i].pos);
			else Used[++ lens[1]][1] = Node(a[i].val , a[i].pos);
		}
		maintain(p , l , L[l]);
		return;
	}
	int mid = (l + r) >> 1;
	if(idx <= mid) update(ls(p) , l , mid , idx , LL , RR , Add);
	else update(rs(p) , mid + 1 , r , idx , LL , RR , Add);
	push_up(p);
}
void query(int p,int l,int r,int nl,int nr,int idx,int x)
{
	if(idx != Lpos[p] && val[idx - 1] >= x) idx --;
	if(idx != Lpos[p] && val[idx - 1] >= x) idx --;
	if(l == r){ans += idx - Lpos[p] + 1;return;}
	int mid = (l + r) >> 1;
	if(nl <= mid) query(ls(p) , l , mid , nl , nr , idx , x);
	if(nr > mid) query(rs(p) , mid + 1 , r , nl , nr , idx , x); 
}
inline void Upd(int l,int r,int Add)
{
	int LL = pos[l] , RR = pos[r];
	if(LL == RR)
	{
		update(1 , 1 , sizt , LL , l , r , Add);
		return;	
	} 
	update(1 , 1 , sizt , LL , l , r,  Add);
	for(int i = LL + 1 ; i <= RR - 1 ; i ++) add[i] += Add;
	update(1 , 1 , sizt , RR , l , r , Add);
}
inline int check(int L,int R,int rank)
{
	ans = 0;
	if(L <= R) 
	{
		int idx = lower_bound(val + Lpos[1] , val + Rpos[1] , rank) - val;
		query(1 , 1 , sizt , L , R , idx , rank);
	}
	return ans + lower_bound(Usedto + 1 , Usedto + 1 + lenss , rank) - Usedto;
}
inline int Qry(int Ls,int Rs,int k)
{
	if(k > (Rs - Ls + 1)) return -1;
	int l = -2e9 , r = 2e9 , LL = pos[Ls] , RR = pos[Rs];
	if(LL == RR) 
	{
		for(int i = L[LL] ; i <= R[LL] ; i ++) 
		{
			if(Ls <= a[i].pos && a[i].pos <= Rs) 
			{
				k --;
				if(!k) return a[i].val;	
			}
		} 
	}
	int i = L[LL] , j = L[RR];lenss = 0;
	while(i <= R[LL] && j <= R[RR])
	{
		if(a[i].pos < Ls || a[i].pos > Rs) i ++;
		else if(a[j].pos < Ls || a[j].pos > Rs) j ++;
		else 
		{
			if(a[i].val + add[LL] < a[j].val + add[RR])	Usedto[++ lenss] = a[i ++].val + add[LL];
			else Usedto[++ lenss] = a[j ++].val + add[RR];
		} 
	}
	while(i <= R[LL]) 
	{
		if(a[i].pos < Ls || a[i].pos > Rs) i ++;
		else Usedto[++ lenss] = a[i ++].val + add[LL];
	}
	while(j <= R[RR])
	{
		if(a[j].pos < Ls || a[j].pos > Rs) j ++;
		else Usedto[++ lenss] = a[j ++].val + add[RR];
	}
	while(l <= r)
	{
		int mid = (l + r) >> 1 , num = check(LL + 1 , RR - 1 , mid);
		if(num == k) return mid;
		else if(num > k) r = mid - 1;
		else l = mid + 1;
	}
}
signed main()
{
	scanf("%d %d",&n,&m);
	t = max(1 , (int)sqrt(n));
	sizt = n / t;
	for(int i = 1 ; i <= sizt ; i ++) L[i] = (i - 1) * t + 1 , R[i] = i * t , len[i] = R[i] - L[i] + 1;
	if(R[sizt] < n) R[sizt] = n;
	len[sizt] = R[sizt] - L[sizt] + 1; 
	for(int i = 1 ; i <= sizt ; i ++) 
		for(int j = L[i] ; j <= R[i] ; j ++) pos[j] = i;
	for(int i = 1 ; i <= n ; i ++){scanf("%d",&a[i].val);a[i].pos = i;}
	for(int i = 1 ; i <= sizt ; i ++) sort(a + L[i] , a + R[i] + 1 , cmp);
	build(1 , 1 , sizt);
	int opt , l , r , k;
	for(int i = 1 ; i <= m ; i ++)
	{
		scanf("%d %d %d %d",&opt,&l,&r,&k);
		if(opt == 2) Upd(l , r , k);
		else printf("%d\n",Qry(l , r , k));
	}
	return 0; 
}