NC20297. [SCOI2014]方伯伯的OJ
描述
输入描述
输入的第1行包含2个用空格分隔的整数n和m，表示初始用户数和操作数。
此后有m行，每行是一个询问，询问格式如上所示。
输出描述
输出包含m行。每行包含一个整数，其中第i行的整数表示第i个操作的输出。
示例1
输入:
10 10 1 2 11 3 13 2 5 3 7 2 8 2 10 2 11 3 14 2 18 4 9
输出:
2 2 2 4 3 5 5 7 8 11
C++14(g++5.4) 解法, 执行用时: 411ms, 内存消耗: 16760K, 提交时间: 2020-01-30 13:40:44
#include<bits/stdc++.h>
using namespace std;
const int MX=1e5+9;
int n,m,cnt=0,root=0;
map<int,int> mp;
int order,x,y;
struct node{
int siz,l,r,fa;
int son[2];
}t[MX<<1];
int get(int x){
return t[t[x].fa].son[1]==x;
}
void pushup(int x){
int lson=t[x].son[0],rson=t[x].son[1];
// t[x].l=t[lson].l,t[x].r=t[rson].r;
t[x].siz=t[lson].siz+t[rson].siz+t[x].r-t[x].l+1;
}
void rotate(int x){
int f=t[x].fa,ff=t[f].fa,w=get(x);
ff?t[ff].son[get(f)]=x:root=x;t[x].fa=ff;
t[f].son[w]=t[x].son[!w],t[t[x].son[!w]].fa=f;
t[x].son[!w]=f,t[f].fa=x;
pushup(f);
pushup(x);
}
void sply(int x,int rt){
while( t[x].fa!=rt ){
int f=t[x].fa,ff=t[f].fa;
if( ff==rt )
rotate(x);
else{
if( get(f)==get(x) )
rotate(f),rotate(x);
else
rotate(x),rotate(x);
}
}
}
int new_node(int l,int r){
int rt=++cnt;
t[rt].l=l,t[rt].r=r;
t[rt].siz=r-l+1;
return rt;
}
void split(int pos,int x){
int lson=0,rson=0;
mp[x]=pos;
if( t[pos].l==t[pos].r )
return ;
if( t[pos].l!=x ){
lson=mp[x-1]=new_node(t[pos].l,x-1);
t[lson].son[0]=t[pos].son[0];
t[t[pos].son[0]].fa=lson;
t[pos].son[0]=lson;
t[lson].fa=pos;
}
if( t[pos].r!=x ){
rson=mp[t[pos].r]=new_node(x+1,t[pos].r);
t[rson].son[1]=t[pos].son[1];
t[t[pos].son[1]].fa=rson;
t[pos].son[1]=rson;
t[rson].fa=pos;
}
t[pos].l=t[pos].r=x;
if( lson ) pushup(lson);
if( rson ) pushup(rson);
pushup(pos);
}
int trank(int x){
int rt=root;
while( rt ){
if( x<=t[t[rt].son[0]].siz )
rt=t[rt].son[0];
else if( x>t[t[rt].son[0]].siz+t[rt].r-t[rt].l+1 ){
x-=(t[t[rt].son[0]].siz+t[rt].r-t[rt].l+1);
rt=t[rt].son[1];
}
else
return t[rt].l+x-t[t[rt].son[0]].siz-1;
}
}
int ordr(int pos){
sply(pos,0);
return t[t[pos].son[0]].siz+1;
}
void first(int pos){
sply(pos,0);
if( t[pos].son[0]==0 )
return ;
else if( t[pos].son[1]==0 ){
swap(t[pos].son[0],t[pos].son[1]);
return ;
}
else{
int rt=t[pos].son[1],ans;
while( rt ){
ans=rt;
rt=t[rt].son[0];
}
t[ans].son[0]=t[pos].son[0];
t[t[pos].son[0]].fa=ans;
t[pos].son[0]=0;
sply(ans,0);
}
}
void endd(int pos){
sply(pos,0);
if( t[pos].son[1]==0 )
return ;
else if( t[pos].son[0]==0 ){
swap(t[pos].son[1],t[pos].son[0]);
return ;
}
else{
int rt=t[pos].son[0],ans;
while( rt ){
ans=rt;
rt=t[rt].son[1];
}
t[ans].son[1]=t[pos].son[1];
t[t[pos].son[1]].fa=ans;
t[pos].son[1]=0;
sply(ans,0);
}
}
int main()
{
// freopen("input.txt","r",stdin);
scanf("%d %d",&n,&m);
root=mp[n]=new_node(1,n);
int a=0,x,y;
while( m-- ){
scanf("%d %d",&order,&x);
if( order==1 ) scanf("%d",&y);
x-=a,y-=a;
if( order==1 ){
int pos=(*mp.lower_bound(x)).second;
split(pos,x);
mp[y]=pos,t[pos].l=t[pos].r=y;
a=ordr(pos);
//mp[y]=pos,t[pos].l=t[pos].r=y;//换位置
printf("%d\n",a);
}
else if( order==2 ){
int pos=(*mp.lower_bound(x)).second;
split(pos,x);
a=ordr(pos);
printf("%d\n",a);
first(pos);
}
else if( order==3 ){
int pos=(*mp.lower_bound(x)).second;
split(pos,x);
a=ordr(pos);
printf("%d\n",a);
endd(pos);
}
else{
a=trank(x);
printf("%d\n",a);
}
}
return 0;
}
C++(clang++11) 解法, 执行用时: 159ms, 内存消耗: 22360K, 提交时间: 2020-11-10 14:46:37
#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pb push_back
using namespace std;
inline int read(){
int nm=0,fh=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
return nm*fh;
}
#define M 100020
int n,m,nowl,nowr,N;
unordered_map<int,int>id,rev;
struct Seg{
int sz[M<<7],ls[M<<7],rs[M<<7],tot;
inline void mdf(int x,int l,int r,int pos,int vl){
sz[x]+=vl; if(l==r) return; int mid=(l+r)>>1;
(pos<=mid)?mdf((!ls[x])?(ls[x]=++tot):ls[x],l,mid,pos,vl):mdf((!rs[x])?(rs[x]=++tot):rs[x],mid+1,r,pos,vl);
}
inline int Get(int x,int l,int r){
l=max(l,n+1),r=min(r,(n<<1)); return ((l>r)?0:(r-l+1))+sz[x];
}
inline int qry(int x,int l,int r,int pos){
if(l==r) return Get(x,l,r); int mid=(l+r)>>1;
return (pos<=mid)?qry(ls[x],l,mid,pos):Get(ls[x],l,mid)+qry(rs[x],mid+1,r,pos);
}
inline int getpos(int x,int l,int r,int pos){
if(l==r) return l; int mid=(l+r)>>1,td=Get(ls[x],l,mid);
return (pos<=td)?getpos(ls[x],l,mid,pos):getpos(rs[x],mid+1,r,pos-td);
}
}P;
int main(){
//freopen("input4.in","r",stdin);
//freopen("md.out","w",stdout);
n=read(),m=read(),nowl=n+1,nowr=(n<<1),N=n*3,P.tot=1;
int lastans=0;
for(int i=1;i<=m;i++){
int opt=read();
if(opt==1){
int x=read()-lastans,y=read()-lastans;
if(!id[x]) id[x]=x+n; id[y]=id[x],rev[id[y]]=y;
printf("%d\n",lastans=P.qry(1,1,N,id[y]));
}else if(opt==2){
int x=read()-lastans;
if(!id[x]) id[x]=x+n;
printf("%d\n",lastans=P.qry(1,1,N,id[x]));
P.mdf(1,1,N,id[x],-1),id[x]=--nowl,P.mdf(1,1,N,id[x],1);
rev[id[x]]=x;
}else if(opt==3){
int x=read()-lastans;
if(!id[x]) id[x]=x+n;
printf("%d\n",lastans=P.qry(1,1,N,id[x]));
P.mdf(1,1,N,id[x],-1),id[x]=++nowr,P.mdf(1,1,N,id[x],1);
rev[id[x]]=x;
}else{
int x=read()-lastans,pos=P.getpos(1,1,N,x);
if(!rev[pos]) rev[pos]=pos-n;
printf("%d\n",lastans=rev[pos]);
}
}
return 0;
}