[ZJOI 2013]K大数查询

注意是K大不是K小！！

样例死活调不出来？？

话说第K大怎么反着求啊？？

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 100010
using namespace std;



namespace BIT{
	int a[maxn],visa[maxn],tim,n;
	int t1[maxn],vis1[maxn];
	#define lowbit(i) i & (~ i) + 1
	void update(int *t,int *vis,int pos,int val){
		pos ++;
		for(int i = pos; i <= n; i += lowbit(i)){
			if(vis[i] != tim){
				vis[i] = tim;
				t[i] = 0;
			}
			t[i] += val;
		}
	}

	int ask(int *t,int pos){
		pos ++;
		int ans = 0;
		for(int i = pos; i; i -= lowbit(i))
			if(vis[i] == tim)
			    ans += t[i];
		return ans;
	}

	void update(int l,int r,int val){
		update(a,visa,l,val);
		update(a,r + 1,-val);
		update(t1,vis1,val * l);
		update(t1,-val * (r + 1));
	}

	int ask(int x){return (x + 1) * ask(a,x) - ask(t1,x);}
}

int mn = 0x7fffffff,mx = -0x7fffffff;
int ID;
int ans[maxn];
struct opt{
	int tp,a,b,c,id;
	void read(){
		scanf("%d%d%d%d",&tp,&a,&b,&c);
		if(tp == 1){
			mn = min(mn,c);
			mx = max(mx,c);
		}
		else id = ++ ID;
	}
}q[maxn],q1[maxn],q2[maxn];

int n,m,tmp[maxn];



void solve(int head,int tail,int l,int r){
	if(tail < head)return;
	if(l == r){
		for(int i = head; i <= tail; i ++)
		    if(q[i].tp == 2)
				ans[q[i].id] = l;
		return;
	}
	int mid = (long long)l + r >> 1;
	BIT::tim ++;
	for(int i = head; i <= tail; i ++){
		if(q[i].tp == 2)
			tmp[i] = BIT::ask(q[i].b) - BIT::ask(q[i].a - 1);
		else{
			if(q[i].c <= mid)continue;
			BIT::update(q[i].a,q[i].b,1);
		}
	}

	int l1 = 0,l2 = 0;
	for(int i = head; i <= tail; i ++){
		if(q[i].tp == 2){
			if(q[i].c <= tmp[i])q2[++ l2] = q[i];
			else{
                q[i].c -= tmp[i];
				q1[++ l1] = q[i];
			}
		}
		else{
			if(q[i].c <= mid)q1[++ l1] = q[i];
			else q2[++ l2] = q[i];
		}
	}
	int cnt = head;
	for(int i = 1; i <= l1; i ++)
	    q[cnt ++] = q1[i];
    for(int i = 1; i <= l2; i ++)
	    q[cnt ++] = q2[i];
	solve(head,head + l1 - 1,mid);
	solve(head + l1,tail,mid + 1,r);
}


int main(){
    freopen("zjoi13_sequence.in","r",stdin);
	freopen("zjoi13_sequence.out","w",stdout);
	scanf("%d%d",&n,&m);
	BIT::n = n;
	for(int i = 1; i <= m; i ++)
		q[i].read();

	solve(1,mn,mx);
	for(int i = 1; i <= ID; i ++)
	    printf("%dn",ans[i]);

    return 0;
}