[SCOI2014]方伯伯的OJ（线段树）

[SCOI2014]方伯伯的OJ（线段树）

题目：Luogu3285

题解：

大佬们都是用Splay做的，其实在数据结构运用上面，此题只是NOIP2017D2T3列队的拓展版，动态开点的线段树就可以搞定。

我的做法的关键在：

1. 在线段树中，利用初始状态易于计算的特点，不用实际值作为初始化内容，而直接在节点区间未被修改时计算状态。

2. 不改变编号在线段树中实际位置，而通过给节点一个cal表示区间有效点个数来确定此编号的排名

操作可以看做是这几个操作的组合：

1. 查询排名为k的编号
2. 删除编号k，并返回删除前k的排名
3. 将编号k的编号改为p
4. 向队尾或队首添加一个编号

我们开一个map记录编号在线段树的实际位置，给将1_n放在m+1n+m位置，也就是给排列前后各预留m个位置，设置两个指针在排列前后指向以前没有插入过编号的位置，插入编号后将指针前移或后移就可以了，这样就可以实现4操作。2，3操作里用map里的数据获得编号的位置可以实现。1操作里，用cal直接在线段树上二分就行了。

总时间复杂度： O ( m l o g m ) O(mlogm) O(mlogm),空间 O ( m l o g m ) O(mlogm) O(mlogm)

代码：

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <map>
using namespace std;
struct Node{Node* l;Node* r;int cal,val;Node(){cal=val=0;l=r=NULL;}
};
int n,q,Bi,Ai,Jia,Len,pai;
Node* Root;
map<int,int> wei;Node* NewNode(){return new Node();
}inline int Cal(Node* o,int l,int r)
{if(o!=NULL)return o->cal;r=min(Jia+n,r);l=max(Jia+1,l);return (l>r?0:r-l+1);
}void update(Node* o,int l,int r,int k,int val0,int cao)
{
//	printf("%d %d %d %d %d %dn",l,r,k,val0,cao,pai);o->cal+=cao;if(l==r){if(cao!=-1)o->val=val0;return;}int mid=(l+r)>>1,l_cal=Cal(o->l,l,mid);
//	cout<<"cal: "<<l_cal<<endl;if(k<=mid){if(o->l==NULL){o->l=NewNode();o->l->cal=l_cal;}update(o->l,l,mid,k,val0,cao);}else{if(o->r==NULL){o->r=NewNode();o->r->cal=o->cal-1-l_cal;}pai+=l_cal;update(o->r,mid+1,r,k,val0,cao);}
}int query(Node* o,int l,int r,int k)
{if(l==r){if(!o->val)o->val=l-Jia;return o->val;}int mid=(l+r)>>1,l_cal=Cal(o->l,l,mid);	if(k<=l_cal){if(o->l==NULL){o->l=NewNode();o->l->cal=l_cal;}return query(o->l,l,mid,k);}else{if(o->r==NULL){o->r=NewNode();o->r->cal=o->cal+1-l_cal;}return query(o->r,mid+1,r,k-l_cal);}
}void out(int f,int x){printf("After %d %d the rank is :n",f,x);for(int i=1;i<=n;i++)printf("%d ",query(Root,1,Len,i));printf("nEndn");}int main()
{
//	freopen("scoi.in","r",stdin);
//	freopen("scois.out","w",stdout);Root=NewNode();scanf("%d%d",&n,&q);Jia=q;Root->cal=n;Bi=Jia;Ai=Jia+n+1;Len=n+2*Jia;int a=0;while(q--){pai=0;int f,x,y;scanf("%d%d",&f,&x);x-=a;int w=wei[x];
//		cout<<"sd:"<<w<<endl;if(!w) w=x+Jia;if(f==1){scanf("%d",&y);y-=a;	wei[x]=-1;wei[y]=w;update(Root,1,Len,w,y,0);pai++;a=pai;printf("%dn",a);}else if(f==2){wei[x]=Bi;update(Root,1,Len,w,2853,-1);pai++;a=pai;printf("%dn",a);update(Root,1,Len,Bi,x,1);Bi--;}else if(f==3){wei[x]=Ai;update(Root,1,Len,w,2853,-1);pai++;a=pai;printf("%dn",a);update(Root,1,Len,Ai,x,1);Ai++;}else{a=query(Root,1,Len,x);printf("%dn",a);}
//		out(f,x);}return 0;
}