3595: [Scoi2014]方伯伯的Oj
Time Limit: 6 Sec Memory Limit: 256 MB
Submit: 102 Solved: 54
[Submit][Status]
Description
方伯伯正在做他的Oj。现在他在处理Oj上的用户排名问题。
Oj上注册了n个用户，编号为1～”，一开始他们按照编号排名。方伯伯会按照心情对这些用户做以下四种操作，修改用户的排名和编号：
1．操作格式为1 x y，意味着将编号为z的用户编号改为V，而排名不变，执行完该操作后需要输出该用户在队列中的位置，数据保证x必然出现在队列中，同时1，是一个当前不在排名中的编号。
2．操作格式为2 x，意味着将编号为x的用户的排名提升到第一位，执行完该操作后需要输出执行该操作前编号为z用户的排名。
3．操作格式为3 x，意味着将编号为z的用户的排名降到最后一位，执行完该操作后需要输出执行该操作前编号为z用户的排名。
4．操作格式为4 k，意味着查询当前排名为足的用户编号，执行完该操作后需要输出当前操作用户的编号。
但同时为了防止别人监听自己的工作，方伯伯对他的操作进行了加密，即将四种操作的格式分别改为了：
1 x+a y+a
2 x+a
3 x+a
4 k+a
其中a为上一次操作得到的输出，一开始a=0。
例如：
上一次操作得到的输出是5
这一次操作的输入为：1 13 15
因为这个输入是经过加密后的，所以你应该处理的操作是1 8 10
现在你截获丁方伯伯的所有操作，希望你能给出结果。
Input
输入的第1行包含2个用空格分隔的整数n和m，表示初始用户数和操作数。
此后有m行，每行是一个询问，询问格式如上所示。
Output
输出包含m行。每行包含一个整数，其中第i行的整数表示第i个操作的输出。
Sample Input
10 10
1 2 11
3 13
25
37
28
2 10
2 11
3 14
2 18
4 9
1 2 11
3 13
25
37
28
2 10
2 11
3 14
2 18
4 9
Sample Output
2
2
2
4
3
5
5
7
8
11
2
2
4
3
5
5
7
8
11
HINT
输入保证对于所有的操作1，2，3，x必然已经出现在队列中，同时对于所有操作1，1≤y≤2×10^8，并且y没有出现在队列中。
对于所有操作4，保证1<k<n。
第一次搞这两个东西的混搭。。。。。。
算法核心为：将标号连续的节点合为一块，并给每一块赋予一个地址pos，并保证长度为len[k]的块k满足pos[k]+len[k]<=pos[k+1]，通过块的分裂，移动实现题中的操作。
借助SBT前趋查找的功能，可找出当前标号所在块的第一个节点标号与所在块的地址。
而可持久化Treap用于给所有块的第一个标号排序。
最后，总结遇到的几个问题：
1、SBT应避免调用到maintain(0)
2、SBT中Delete部分多个if语句间不能并列，要用else连接，否则rotate时改变了now的值后果很严重。
3、可持久化Treap中注意判断now!=0
4、最严重的问题：Treap中要记得赋随机值，否则就T了一个晚上。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXT 310000
#define INF 0x3f3f3f3f
struct group
{
int first,second,third;
};
group make_group(int a,int b,int c)
{
group ret;
ret.first=a;
ret.second=b;
ret.third=c;
return ret;
}
struct SBTree
{
int L[MAXT],R[MAXT],S[MAXT],id[MAXT],pos[MAXT];
int root;
queue<int> Q;
SBTree()
{
int i;
for (i=;i<MAXT;i++)Q.push(i);
root=;
}
void update(int &now)
{
S[now]=S[L[now]]+S[R[now]]+;
}
void l_rot(int &now)
{
int t=R[now];
R[now]=L[t];update(now);
L[t]=now;update(t);
now=t;
}
void r_rot(int &now)
{
int t=L[now];
L[now]=R[t];update(now);
R[t]=now;update(t);
now=t;
}
void maintain(int &now)
{
if (S[L[L[now]]]>S[R[now]])
{
r_rot(now);
maintain(L[now]);
maintain(R[now]);
maintain(now);
}
if (S[R[R[now]]]>S[L[now]])
{
l_rot(now);
maintain(L[now]);
maintain(R[now]);
maintain(now);
}
if (S[L[R[now]]]>S[L[now]])
{
r_rot(R[now]);
l_rot(now);
maintain(L[now]);
maintain(R[now]);
maintain(now);
}
if (S[R[L[now]]]>S[R[now]])
{
l_rot(L[now]);
r_rot(now);
maintain(L[now]);
maintain(R[now]);
maintain(now);
}
} void Insert(int &now,int _id,int _pos)
{
if (!now)
{
now=Q.front();
Q.pop();
id[now]=_id;
pos[now]=_pos;
S[now]=;
L[now]=R[now]=;
return ;
}
if (_id<=id[now])
{
Insert(L[now],_id,_pos);
}else
{
Insert(R[now],_id,_pos);
}
update(now);
maintain(now);
}
pair<int,int> Find(int &now,int _id)
{
if (!now)return make_pair(-INF,-INF);
if (id[now]>_id)
{
return Find(L[now],_id);
}
if (id[now]==_id)
{
return make_pair(id[now],pos[now]);
}
if (id[now]<_id)
{
pair<int,int> ret;
if (R[now])
{
ret=Find(R[now],_id);
if (ret.first<id[now])
{
ret.first=id[now];
ret.second=pos[now];
}
}else
{
ret.first=id[now];
ret.second=pos[now];
}
return ret;
}
}
void Delete(int &now,int _id)
{
if (!now)throw "Cannot delete" ;
if (_id==id[now])
{
if (!R[now]&&!L[now])
{
now=;
return ;
}
if (R[now]&&L[now])
{
r_rot(now);
Delete(R[now],_id);
}else
if (!R[now])
{
now=L[now];
}else if (!L[now])//易忽略
{
now=R[now];
}
update(now);
maintain(now);
return ;
}
if (_id<id[now])
{
Delete(L[now],_id);
}else
{
Delete(R[now],_id);
}
update(now);
maintain(now);
return ;
}
void Scan(int &now)
{
if (!now)return ;
Scan(L[now]);
printf("<%d,%d> ",id[now],pos[now]);
Scan(R[now]);
} }SBT;
struct pTreap
{
int L[MAXT],R[MAXT],K[MAXT],id[MAXT],pos[MAXT],len[MAXT],size[MAXT],S[MAXT];
int root;
queue<int> Q;
pTreap()
{
root=;
for(int i=;i<=MAXT;i++)Q.push(i);
}
void up(int now)
{
if (!now)return;
S[now]=S[L[now]]+S[R[now]]+;
size[now]=size[L[now]]+size[R[now]]+len[now];
}
int Merge(int x,int y)//小根堆
{
if (!y)return x;
if (!x)return y;
if (K[x]<K[y])
{
R[x]=Merge(R[x],y);
up(x);
return x;
}else
{
L[y]=Merge(x,L[y]);
up(y);
return y;
}
}
pair<int,int> Split(int now,int cnt)
{
if (!now)return make_pair(,);
if (S[L[now]]+<=cnt)
{
pair<int,int> p1;
p1=Split(R[now],cnt-S[L[now]]-);
L[now]=Merge(L[now],p1.first);
return make_pair(now,p1.second);
}else
{
pair<int,int> p1;
p1=Split(L[now],cnt);
R[now]=Merge(p1.second,R[now]);
return make_pair(p1.first,now);
}
}
int Insert(int now,int rk,int _id,int _len,int _pos)
{
pair<int,int> p1;
p1=Split(now,rk);
now=Q.front();
Q.pop();
K[now]=rand();
id[now]=_id;
len[now]=_len;
pos[now]=_pos;
S[now]=;
up(now);
return Merge(p1.first,Merge(now,p1.second));
}
group Get(int now,int _pos)
{
group g1;
if (!now)return make_group(,,);
if (_pos==pos[now])
{
int l,r;
l=L[now],r=R[now];
L[now]=R[now]=;
up(now);
return make_group(l,now,r);
}
if (_pos<pos[now])
{
g1=Get(L[now],_pos);
L[now]=g1.third;
g1.third=now;
up(now);
return g1;
}
if (_pos>pos[now])
{
g1=Get(R[now],_pos);
R[now]=g1.first;
g1.first=now;
up(now);
return g1;
}
}
int Get_new_node()
{
int ret=Q.front();
Q.pop();
return ret;
}
int Get_id(int now,int _pos)
{
if (!now)throw "Error:Cannot find id";
if (size[L[now]]+<=_pos&&size[L[now]]+len[now]>=_pos)
{
return id[now]+_pos-size[L[now]]-;
}
if (_pos<=size[L[now]])
{
return Get_id(L[now],_pos);
}else
{
return Get_id(R[now],_pos-size[L[now]]-len[now]);
}
}
void Scan(int now,char ch=' ')
{
if (!now)return ;
if (now==root&&size[now]!=)throw "range error!!";
Scan(L[now],ch);
printf("<%d,%d,%d>%c",id[now],len[now],pos[now],ch);
Scan(R[now],ch);
}
void Scan2(int now,char ch=' ')
{
if (!now)return ;
Scan2(L[now]);
for (int i=;i<len[now];i++)
{
printf("%d%c",id[now]+i,ch);
}
Scan2(R[now]);
}
}T;
int n,m;
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
try{
int i,x,y;
int last_ans=,ans;
int now_rank,first_rank,last_rank;
int opt;
pair<int,int> p1,p2;
int ptr_h,ptr_t;
group g1,g2;
scanf("%d%d",&n,&m);
T.Scan2();
SBT.Insert(SBT.root,,);
T.root=T.Insert(T.root,,,n,);
ptr_h=,ptr_t=n;
for (i=;i<m;i++)
{
scanf("%d",&opt);
switch(opt)
{
case ://change id
scanf("%d%d",&x,&y);
x-=last_ans;y-=last_ans;
p1=SBT.Find(SBT.root,x);//<id,pos>
g1=T.Get(T.root,p1.second);
first_rank=T.size[g1.first]+;
now_rank=first_rank+x-p1.first;
last_rank=T.size[g1.first]+T.size[g1.second];
ans=now_rank;
if (now_rank>first_rank)
{
g2.first=T.Get_new_node();
T.S[g2.first]=;
T.K[g2.first]=rand();
T.len[g2.first]=now_rank-first_rank;
T.id[g2.first]=p1.first;
T.pos[g2.first]=p1.second;
}else g2.first=;
if (now_rank<last_rank)
{
g2.third=T.Get_new_node();
T.S[g2.third]=;
T.K[g2.third]=rand();
T.len[g2.third]=last_rank-now_rank;
T.id[g2.third]=x+;
T.pos[g2.third]=p1.second+now_rank-first_rank+;
}else g2.third=;
g2.second=g1.second;
T.S[g2.second]=;
T.K[g2.second]=rand();
T.len[g2.second]=;
T.id[g2.second]=y;
T.pos[g2.second]=p1.second+now_rank-first_rank;
T.up(g2.first);
T.up(g2.second);
T.up(g2.third);
g1.second=T.Merge(g2.first,T.Merge(g2.second,g2.third));
T.root=T.Merge(g1.first,T.Merge(g1.second,g1.third)); if (now_rank==first_rank)SBT.Delete(SBT.root,p1.first);
SBT.Insert(SBT.root,y,p1.second+now_rank-first_rank);
if (now_rank<last_rank)SBT.Insert(SBT.root,x+,p1.second+now_rank-first_rank+);
break;
case ://To the first
scanf("%d",&x);
x-=last_ans;
p1=SBT.Find(SBT.root,x);//<id,pos>
g1=T.Get(T.root,p1.second);
first_rank=T.size[g1.first]+;
now_rank=first_rank+x-p1.first;
last_rank=T.size[g1.first]+T.size[g1.second];
ans=now_rank;
if (now_rank>first_rank)
{
g2.first=T.Get_new_node();
T.S[g2.first]=;
T.K[g2.first]=rand();
T.len[g2.first]=now_rank-first_rank;
T.id[g2.first]=p1.first;
T.pos[g2.first]=p1.second;
}else g2.first=;
if (now_rank<last_rank)
{
g2.third=T.Get_new_node();
T.S[g2.third]=;
T.K[g2.third]=rand();
T.len[g2.third]=last_rank-now_rank;
T.id[g2.third]=x+;
T.pos[g2.third]=p1.second+now_rank-first_rank+;
}else g2.third=;
g2.second=g1.second;
T.S[g2.second]=;
T.K[g2.second]=rand();
T.len[g2.second]=;
T.id[g2.second]=x;
T.pos[g2.second]=--ptr_h;
T.up(g2.first);
T.up(g2.second);
T.up(g2.third);
g1.second=T.Merge(g2.first,g2.third);
T.root=T.Merge(g2.second,T.Merge(g1.first,T.Merge(g1.second,g1.third)));
if (now_rank==first_rank)SBT.Delete(SBT.root,p1.first);
SBT.Insert(SBT.root,x,ptr_h);
if (now_rank<last_rank)SBT.Insert(SBT.root,x+,p1.second+now_rank-first_rank+);
break;
case ://To thre lase
scanf("%d",&x);
x-=last_ans;
p1=SBT.Find(SBT.root,x);//<id,pos>
g1=T.Get(T.root,p1.second);
first_rank=T.size[g1.first]+;
now_rank=first_rank+x-p1.first;
last_rank=T.size[g1.first]+T.size[g1.second];
ans=now_rank;
if (now_rank>first_rank)
{
g2.first=T.Get_new_node();
T.S[g2.first]=;
T.K[g2.first]=rand();
T.len[g2.first]=now_rank-first_rank;
T.id[g2.first]=p1.first;
T.pos[g2.first]=p1.second;
}else g2.first=;
if (now_rank<last_rank)
{
g2.third=T.Get_new_node();
T.S[g2.third]=;
T.K[g2.third]=rand();
T.len[g2.third]=last_rank-now_rank;
T.id[g2.third]=x+;
T.pos[g2.third]=p1.second+now_rank-first_rank+;
}else g2.third=;
g2.second=g1.second;
T.S[g2.second]=;
T.K[g2.second]=rand();
T.len[g2.second]=;
T.id[g2.second]=x;
T.pos[g2.second]=++ptr_t;
T.up(g2.first);
T.up(g2.second);
T.up(g2.third);
g1.second=T.Merge(g2.first,g2.third);
T.root=T.Merge(T.Merge(g1.first,T.Merge(g1.second,g1.third)),g2.second);
if (now_rank==first_rank)SBT.Delete(SBT.root,p1.first);
SBT.Insert(SBT.root,x,ptr_t);
if (now_rank<last_rank)SBT.Insert(SBT.root,x+,p1.second+now_rank-first_rank+);
break;
case ://Query position
scanf("%d",&x);
x-=last_ans;
ans=T.Get_id(T.root,x);
break;
}
// cout<<"Query:"<<"<"<<i<<">"<<opt<<" "<<x;if (opt==1)cout<<" "<<y;cout<<endl;
// cout<<"Query_ret:"<<ans<<endl;
last_ans=ans;
// cout<<"SBT<id,pos>:";SBT.Scan(SBT.root);cout<<endl;
// cout<<"Treap<id,len,pos>:";T.Scan(T.root);cout<<endl;
// cout<<"Seq:";T.Scan2(T.root);cout<<endl;
printf("%d\n",ans);
} }catch(const char * err)
{
cerr<<err<<endl;
} }