思路:线段树套可持久化treap，可持久化treap我还是第一次听说。。
改题的时候没看数据范围。。乱开数组T_T
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<time.h>
#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
int n;
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
struct treaps{
int ch[][],rnd[],size[],num[],tt;
int newnode(int s=){
if (tt>) assert();
++tt;
ch[tt][]=ch[s][];
ch[tt][]=ch[s][];
if (s) rnd[tt]=rnd[s];else rnd[tt]=rand();
size[tt]=size[s];
num[tt]=num[s];
return tt;
}
void updata(int k){
size[k]=+size[ch[k][]]+size[ch[k][]];
}
int getsize(int k){
return size[k];
}
int merge(int s,int t){
if (!s||!t) return s+t;
if (rnd[s]>rnd[t]){
int d=newnode(s);
ch[d][]=merge(ch[d][],t);
updata(d);
return d;
}else{
int d=newnode(t);
ch[d][]=merge(s,ch[d][]);
updata(d);
return d;
}
}
pair<int,int> split(int s,int k){
if (!s) return make_pair(,);
if (size[ch[s][]]>=k){
pair<int,int> ls=split(ch[s][],k);
int d=newnode(s);
ch[d][]=ls.second;updata(d);
return pair<int,int>(ls.first,d);
}
pair<int,int> ls=split(ch[s][],k-size[ch[s][]]-);
int d=newnode(s);
ch[d][]=ls.first;updata(d);
return pair<int,int>(d,ls.second);
}
void clear(int &s){
s=;
}
void push_back(int &s,int w){
int d=newnode();size[d]=;num[d]=w;
s=merge(s,d);
}
void pop_back(int &s){
s=split(s,size[s]-).first;
}
int findkth(int s,int k){
if (size[ch[s][]]>=k) return findkth(ch[s][],k);
if (size[ch[s][]]+==k) return num[s];
return findkth(ch[s][],k-size[ch[s][]]-);
}
}treap;
struct segment{
int tt,l[],r[];
int ins[];
int erz[];
int build(int ql=,int qr=n){
int t=++tt;
int mid=(ql+qr)>>;
if (ql==qr) return t;
l[t]=build(ql,mid);
r[t]=build(mid+,qr);
return t;
}
void pushdown(int root){
if (erz[root]){
if (treap.getsize(ins[l[root]])<=erz[root]){
erz[l[root]]+=erz[root]-treap.getsize(ins[l[root]]);
treap.clear(ins[l[root]]);
}else ins[l[root]]=treap.split(ins[l[root]],treap.getsize(ins[l[root]])-erz[root]).first; if (treap.getsize(ins[r[root]])<=erz[root]){
erz[r[root]]+=erz[root]-treap.getsize(ins[r[root]]);
treap.clear(ins[r[root]]);
}else ins[r[root]]=treap.split(ins[r[root]],treap.getsize(ins[r[root]])-erz[root]).first;
erz[root]=;
}
if (treap.getsize(ins[root])){
ins[l[root]]=treap.merge(ins[l[root]],ins[root]);
ins[r[root]]=treap.merge(ins[r[root]],ins[root]);
treap.clear(ins[root]);
}
}
void push(int root,int ql,int qr,int w,int pl=,int pr=n){
if ((ql==pl)&&(pr==qr)){
treap.push_back(ins[root],w);
return;
}
pushdown(root);
int mid=(pl+pr)>>;
if (ql<=mid) push(l[root],ql,min(qr,mid),w,pl,mid);
if (qr>mid) push(r[root],max(mid+,ql),qr,w,mid+,pr);
}
void pop(int root,int ql,int qr,int pl=,int pr=n){
if ((ql==pl)&&(qr==pr)){
if (treap.getsize(ins[root])) treap.pop_back(ins[root]);
else erz[root]++;
return;
}
pushdown(root);
int mid=(pl+pr)>>;
if (ql<=mid) pop(l[root],ql,min(mid,qr),pl,mid);
if (qr>mid) pop(r[root],max(ql,mid+),qr,mid+,pr);
}
void work(int root,int s,int k,int pl=,int pr=n){
if (pl==pr){
if (treap.getsize(ins[root])<k) printf("Error\n");
else
printf("%d\n",treap.findkth(ins[root],treap.getsize(ins[root])-k+));
return;
}
pushdown(root);
int mid=(pl+pr)>>;
if (s<=mid) work(l[root],s,k,pl,mid);
else work(r[root],s,k,mid+,pr);
}
}seg;
int main(){
n=read();int q=read();
seg.build();
while (q--){
int opt=read();
if (opt==){
int l=read(),r=read(),x=read();
seg.push(,l,r,x);
}else
if (opt==){
int l=read(),r=read();
seg.pop(,l,r);
}else
if (opt==)
{
int s=read(),k=read();
seg.work(,s,k);
}
}
}