四叉树编码，bzoj4415 [Shoi2013]发牌 线段树

相当于找区间第k个数，同时支持删点

这个题的线段树操作和noiD1T1有点像。所以调了半天。

四叉树编码。注意对size取模，注意查找区间第k的时候的特判

码：

线性四叉树编码 详解、

#include<iostream>
#include<cstdio>
using namespace std;
#define zuo o<<1,l,mid
#define you o<<1|1,mid+1,r
#define N 700005
int sz[N<<4],n,o,a,b,c,zz,op,i;
bool ky;
void up(int o)
{int ll=o<<1,rr=o<<1|1;sz[o]=sz[ll]+sz[rr];
}
void jian(int o,int l,int r)
{if(l==r){sz[o]=1;return ;}int mid=(l+r)>>1;jian(zuo);jian(you);	up(o);	
}
void gai(int o,int l,int r)
{	int mid=(l+r)>>1;if(a<=l&&b>=r){if(op==0)sz[o]=0;		if(op==1) c+=sz[o];return ;}if(a<=mid)gai(zuo);if(b>mid)gai(you);up(o);
}
void cha(int o,int l,int r)
{
int mid=(l+r)>>1;if(a<=l&&r<=b){
if(sz[o]<c){c-=sz[o];return ;}
if(l==r){c=l,ky=1;return;}if(sz[o<<1]<c){  	c-=sz[o<<1];cha(you);	}else{
cha(zuo);	 }	return ;	}	if(a<=mid)cha(zuo);if(b>mid&&ky==0)cha(you);
}
int main()
{scanf("%d",&n);jian(1,1,n);zz=1;for(i=1;i<=n;i++){scanf("%d",&o);o%=sz[1];if(i==n){printf("%d",zz);return 0;}
o++;//找位置op=1;a=zz;b=n;c=0;gai(1,1,n);if(c<o){o-=c;a=1;b=zz;}else{	a=zz;b=n;}ky=0;c=o;cha(1,1,n);//输出printf("%d\n",c);zz=c;op=0;a=b=c;gai(1,1,n);		//换位置 op=1;a=zz;b=n;c=0; gai(1,1,n);if(c==0){a=1;b=n;	}else{a=zz;b=n;}ky=0;			 c=1;cha(1,1,n);zz=c;		}
}