[TIOJ] 1382. 約瑟問題

題目連結:http://tioj.infor.org/problems/1382

---

原本用黑魔法過了這題，但覺得沒寫過平衡樹覺得還是該練練，所以就寫了個怪怪treap版本的(因為我會按照1,2,3,4...insert，所以不需要split)。這題的做法基本上就是每次查好你要砍那個，先輸出一下再刪掉就好，複雜度$O(n log n)$

#include <bits/stdc++.h>
using namespace std;

class tree{
	private:
		struct node{
			int size,val,pri;
			node* l;
			node* r;
			node* f;
			node(){f=NULL;l=NULL;r=NULL;size=0;pri=rand();}
			node(int x){f=NULL;l=NULL;r=NULL;size=1;val=x;pri=rand();}
		};
		node* root;
		inline int gSize(node* x){return (x==NULL)?0:x->size;}
		node* merge(node* x, node* y){
			if(x==NULL)return y;
			if(y==NULL)return x;
			bool xfa = (x->pri)>(y->pri);
			if(xfa){
				if(y->val < x->val){
					x->l=merge(x->l,y);
					x->l->f=x;
				}else{
					x->r=merge(x->r,y);
					x->r->f=x;
				}
				x->size=gSize(x->l)+gSize(x->r)+1;
				return x;
			}else{
				if(x->val < y->val){
					y->l=merge(y->l,x);
					y->l->f=y;
				}
				else{
					y->r=merge(y->r,x);
					y->r->f=y;
				}
				y->size=gSize(y->l)+gSize(y->r)+1;
				return y;
			}
		}
		node* fbo(int k,int cnt,node* x){
			if(cnt+gSize(x->l)==k)return x;
			else if(cnt+gSize(x->l)<k)return fbo(k,cnt+gSize(x->l)+1,x->r);
			else return fbo(k,cnt,x->l);
		}
		void mf(node *x){
			if(x==NULL)return;
			x->size--;
			if(x->f)mf(x->f);
		}
	public:
		tree(){root = NULL;}
		void insert(int x){
			auto nn=new node(x);
			root = merge(nn,root);
			root->size=gSize(root->l)+gSize(root->r)+1;
		}
		inline int size(){return gSize(root);}
		void erase(int x){
			auto which=fbo(x,0,root);
			if(which->f){
				auto ll=which->l, rr=which->r, ff=which->f;
				if(ff->l==which){
					if(ll)ll->f=NULL;if(rr)rr->f=NULL;
					delete which;which=NULL;
					ff->l=merge(rr,ll);
					if(ff->l)ff->l->f=ff;
					mf(ff);
				}else if(ff->r==which){
					if(ll)ll->f=NULL;if(rr)rr->f=NULL;
					delete which;which=NULL;
					ff->r=merge(rr,ll);
					if(ff->r)ff->r->f=ff;
					mf(ff);
				}
			}else{
				auto ll=which->l, rr=which->r;
				delete which;which=NULL;
				if(ll)ll->f=NULL;if(rr)rr->f=NULL;
				root = merge(ll,rr);
				if(root)root->size=gSize(root->l)+gSize(root->r)+1;
			}
		}
		int find_by_order(int x){return fbo(x,0,root)->val;}
};

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	srand(time(NULL));
	int n;
	while(cin>>n){
		tree tt;
		int start=0;
		for(int i=1;i<=n;i++)tt.insert(i);
		for(int i=0;i<n;i++){
			int k;cin>>k;
			start=(start+k-1)%tt.size();
			cout<<tt.find_by_order(start)<<' ';
			tt.erase(start);
		}
		cout<<'\n';
	}
	return 0;
}