codeforces 38G - Queue splay伸展树

时间：2023-03-09 14:26:38
codeforces 38G - Queue splay伸展树

题目

https://codeforces.com/problemset/problem/38/G

题意:

一些人按顺序进入队列,每个人有两个属性,地位$A$和能力$C$

每个人进入时都在队尾,并最多可以和前一位互换$C$次,如果前一位的地位高于自己,则无法继续互换.

最终一次性输出整个队列

题解:

splay维护动态的队列

可以用类似权值线段树的思维去考虑

对于每个点,保存其子节点的最大值,自身的值,与子树的大小

对于每次插入时,若能跨过整颗右子树与当前节点,则向左走,否则向右

可以保证整个子树中序遍历的顺序即为当前队列

又因为是平衡树,每次插入一个点,都将该点旋转至根,因此均摊复杂度$O(logn)$

codeforces 38G - Queue splay伸展树

#include <bits/stdc++.h>

#define endl '\n'

#define ll long long

#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)

using namespace std;

const int maxn=1e6+10,maxm=2e6+10;

const int INF=0x3f3f3f3f;

int casn,n,m,k;

class splaytree{

#define nd node[now]

#define ndl	node[node[now].son[0]]

#define ndr node[node[now].son[1]]

	public:

  struct splaynode{

    int son[2],pre;

    int val,mx,size;

    splaynode(){mx=val=size=pre=son[0]=son[1]=0;}

    splaynode(int x,int fa=0){mx=val=x;pre=fa;son[0]=son[1]=0;size=1;}

  };

  int cnt,root;

  vector<splaynode> node;

	void pushup(int now){

		nd.mx=nd.val,nd.size=1;

		rep(i,0,1)if(nd.son[i]) {

			nd.mx=max(node[nd.son[i]].mx,nd.mx);

			nd.size+=node[nd.son[i]].size;

		}

	}

	void pushdown(int now){}

	void rotate(int now,int d){

    int fa=nd.pre;

    pushdown(fa);pushdown(now);

    node[fa].son[!d]=nd.son[d];

    node[nd.son[d]].pre=fa;

    if(node[fa].pre){

			node[node[fa].pre].son[node[node[fa].pre].son[1]==fa]=now;

    }else root=now;

    nd.pre=node[fa].pre;

    nd.son[d]=fa,node[fa].pre=now;

    pushup(fa);pushup(now);

  }

  void splay(int now,int dst){

  	pushdown(now);

    while(nd.pre!=dst){

      if(node[nd.pre].pre==dst)rotate(now,node[nd.pre].son[0]==now);

      else{

	    	int fa=nd.pre,d=(node[node[fa].pre].son[0]==fa);

		    if(node[fa].son[d]==now){rotate(now,!d);rotate(now,d);}

				else {rotate(fa,d);rotate(now,d);}

			}

    }

    if(!dst) root=now;

    pushup(now);

  }

  void insert(int val,int len){

  	if(!root){

			node[++cnt]=splaynode(val);

			root=cnt;

			return;

  	}

  	int now=root;

  	int flag=(val<(max(nd.val,ndr.mx))||len<ndr.size+1);

		while(1){

			if(!nd.son[flag]){

				node[++cnt]=splaynode(val,now);

				nd.son[flag]=cnt;

				break;

			}

			if(!flag)len-=ndr.size+1;

			now=nd.son[flag];

			flag=(val<(max(nd.val,ndr.mx))||len<ndr.size+1);

		}

		pushup(now);

		splay(cnt,0);

  }

  void print(){print(root);}

  void print(int now){

		if(nd.son[0]) print(nd.son[0]);

		cout<<now<<' ';

		if(nd.son[1]) print(nd.son[1]);

  }

  splaytree(int n){

    node.resize(n+7);

    root=0,cnt=0;

  }

};

int main() {

	IO;

	cin>>n;

	splaytree tree(n);

	rep(i,1,n){

		int a,b;cin>>a>>b;

		tree.insert(a,b);

	}

	tree.print();

	return 0;

}

相关文章