题目链接
直接动态开点线段树，维护所有可能出现的位置\([-m,n+m]\)，并按排名排列元素，记个区间元素个数以及底层节点代表的编号，再搞个map记每个编号对应在线段树中出现的位置即可，跑的飞快，远超平衡树。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<map>
#define P puts("lala")
#define cp cerr<<"lala"<<endl
#define ln putchar('\n')
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
inline int read()
{
char ch=getchar();int g=1,re=0;
while(ch<'0'||ch>'9') {if(ch=='-')g=-1;ch=getchar();}
while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+(ch^48),ch=getchar();
return re*g;
}
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
map<int,int>mp;
int n,m;
const int N=100050;
int key[N*60],ch[N*60][2],sum[N*60],rt,sz=0,L,R;
int updateid(int &o,int l,int r,int x,int k)
{
if(!o)
{
o=++sz;sum[o]=max(min(r,n)-max(l,1)+1,0);
if(l==r) key[o]=l;
}
if(l==r) {key[o]=k; return 0;}
int mid=l+r>>1,lsiz=ch[o][0]?sum[ch[o][0]]:max(min(mid,n)-max(l,1)+1,0);
if(x<=mid) return updateid(ch[o][0],l,mid,x,k);
else return updateid(ch[o][1],mid+1,r,x,k)+lsiz;
}
int update(int &o,int l,int r,int x,int k,int id)
{
if(!o)
{
o=++sz;sum[o]=max(min(r,n)-max(l,1)+1,0);
if(l==r) key[o]=l;
}
sum[o]+=k;
if(l==r) {if(id!=-1) key[o]=id;return 0;}
int mid=l+r>>1,lsiz=ch[o][0]?sum[ch[o][0]]:max(min(mid,n)-max(l,1)+1,0);
if(x<=mid) return update(ch[o][0],l,mid,x,k,id);
else return update(ch[o][1],mid+1,r,x,k,id)+lsiz;
}
int query(int &o,int l,int r,int k)
{
if(!o)
{
o=++sz;sum[o]=max(min(r,n)-max(l,1)+1,0);
if(l==r) key[o]=l;
}
if(l==r) return key[o];
int mid=l+r>>1,lsiz=ch[o][0]?sum[ch[o][0]]:max(min(mid,n)-max(l,1)+1,0);
if(k<=lsiz) return query(ch[o][0],l,mid,k);
else return query(ch[o][1],mid+1,r,k-lsiz);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);freopen("1.out","w",stdout);
#endif
int i,j,opt,T;
n=read(); m=read();
L=1; R=n;
int lastans=0;
for(int cas=1;cas<=m;++cas)
{
opt=read();
if(opt==1) //modify id
{
int x=read(),y=read(); x-=lastans; y-=lastans;
if(!mp.count(x)) mp[x]=x;
mp[y]=mp[x]; mp.erase(x);
printf("%d\n",lastans=updateid(rt,-m,n+m,mp[y],y)+1);
}
else if(opt==2) //make it first
{
int x=read(); x-=lastans;
if(!mp.count(x)) mp[x]=x;
printf("%d\n",lastans=update(rt,-m,m+n,mp[x],-1,-1)+1);
L--; mp[x]=L;
update(rt,-m,n+m,L,1,x);
}
else if(opt==3) //make it last
{
int x=read(); x-=lastans;
if(!mp.count(x)) mp[x]=x;
printf("%d\n",lastans=update(rt,-m,n+m,mp[x],-1,-1)+1);
R++; mp[x]=R;
update(rt,-m,n+m,R,1,x);
}
else if(opt==4) //query kth's id
{
int k=read(); k-=lastans;
printf("%d\n",lastans=query(rt,-m,n+m,k));
}
}
return 0;
}