Description
有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c
如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。
Input
第一行N，M
接下来M行，每行形如1 a b c或2 a b c
Output
输出每个询问的结果
Sample Input
2 5
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3
Sample Output
1
2
1
HINT
N,M<=50000,N,M<=50000
a<=b<=N
1操作中abs(c)<=N
2操作中abs(c)<=Maxlongint
Source
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m;
inline int read(){
int tmp=0;char ch;bool kk=0;
while(ch=getchar())if('0'<=ch&&ch<='9')break;
else if(ch=='-')kk=1;
for(;'0'<=ch&&ch<='9';ch=getchar())tmp=tmp*10+ch-'0';
return kk?-tmp:tmp;
}
struct seg{
struct Seg{
#define maxn 1000000
#define maxm 5000000
int ls[maxm],rs[maxm],size[maxm],cnt[maxm],tot,ans;
Seg(){memset(ls,0,sizeof(ls)+sizeof(rs)+sizeof(size)+4+sizeof(cnt));}
int insert(int p,int l,int r,int x,int y){
if(x<=l&&r<=y){
size[p]+=r-l+1;
cnt[p]+=1;
return r-l+1;
}
int mid=(l+r)>>1,tmp=0;
if(x<=mid)tmp+=insert(ls[p]?ls[p]:ls[p]=++tot,l,mid,x,y);
if(y>mid)tmp+=insert(rs[p]?rs[p]:rs[p]=++tot,mid+1,r,x,y);
size[p]+=tmp;
return tmp;
}
void query(int p,int l,int r,int x,int y){
if(x<=l&&r<=y){
ans+=size[p];
return;
}
ans+=(min(y,r)-max(l,x)+1)*cnt[p];
int mid=(l+r)>>1;
if(x<=mid&&ls[p])query(ls[p],l,mid,x,y);
if(y>mid&&rs[p])query(rs[p],mid+1,r,x,y);
}
}Kd;
int tot,root[maxn],ls[maxm],rs[maxm],ans;
seg(){memset(root,0,sizeof(root)+sizeof(ls)+sizeof(rs));tot=1;}
void insert(int p,int l,int r,int val,int ll,int rr){
Kd.insert(root[p]?root[p]:root[p]=++Kd.tot,1,n,ll,rr);
if(l==r)return;
int mid=(l+r)>>1;
if(val<=mid)insert(ls[p]?ls[p]:ls[p]=++tot,l,mid,val,ll,rr);
else insert(rs[p]?rs[p]:rs[p]=++tot,mid+1,r,val,ll,rr);
}
void query(int p,int l,int r,int rk,int x,int y){
if(l==r){ans=l;return;}
int mid=(l+r)>>1;Kd.ans=0;
if(rs[p])Kd.query(root[rs[p]],1,n,x,y);
if(Kd.ans>=rk)query(rs[p],mid+1,r,rk,x,y);
else query(ls[p],l,mid,rk-Kd.ans,x,y);
}
}kd;
int main(){
// freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);
n=read();m=read();
for(int i=1;i<=m;i++){
int a=read(),b=read(),c=read(),d=read();
if(a==1)kd.insert(1,-50000,50000,d,b,c);
else{
kd.query(1,-50000,50000,d,b,c);
printf("%d\n",kd.ans);
}
}//system("pause");
return 0;
}