Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
类似康托展开的方法。In Reply To:康托展开+树维护,这样都ML爆内存,求大牛解答 Posted by:shuaige123 at 2012-11-07 16:04:13 > #include<cstdio> > #include<cstring> > #include<cstdlib> > #include<cmath> > #include<ctime> > #include<iostream> > #include<algorithm> > #include<vector> > #define max_int 2147483647 > #define oo 1000000000 > #define ll long long > #define db double > #define il inline > #define ms memset > #define mc memcpy > #define sz sizeof > #define gc getchar > #define fo freopen > il int maxx(int a,int b){return a>b?a:b;} > il int minn(int a,int b){return a<b?a:b;} > il void swap(int &a,int &b){int tt=a; a=b; b=tt; return;} > il void swap_ll(ll &a,ll &b){ll tt=a; a=b; b=tt; return;} > il void swap_db(db &a,db &b){db tt=a; a=b; b=tt; return;} > using namespace std; > #define maxn 110 > struct treap_node > { > int lc,rc,d,key,total; > #define lc(x) tr[x].lc > #define rc(x) tr[x].rc > #define d(x) tr[x].d > #define key(x) tr[x].key > #define total(x) tr[x].total > }tr[maxn]; > ll a[maxn],n,m,step[26],sum,root; > il void clear(int x) > { > if (x!=-1) lc(x)=rc(x)=d(x)=key(x)=total(x)=0; > return; > } > il void updata(int x) > { > clear(0); > if (x!=-1) total(x)=total(lc(x))+total(rc(x))+1; > return; > } > il int l_rotate(int x) > { > int y=rc(x),z=lc(rc(x)); > rc(x)=z; lc(y)=x; > updata(x); > return y; > } > il int r_rotate(int x) > { > int y=lc(x),z=rc(lc(x)); > lc(x)=z; rc(y)=x; > updata(x); > return y; > } > il int ins(int w,int val) > { > if (w==-1) w=++sum,lc(w)=rc(w)=-1,d(w)=val,total(w)=1,key(w)=rand(); > else > { > if (val<d(w)) > { > lc(w)=ins(lc(w),val); > if (key(lc(w))>key(w)) w=r_rotate(w); > } > else > { > rc(w)=ins(rc(w),val); > if (key(rc(w))>key(w)) w=l_rotate(w); > } > } > updata(w); > return w; > } > il int del(int w,int val) > { > if (val<d(w)) lc(w)=del(lc(w),val); > else if (val>d(w)) rc(w)=del(rc(w),val); > else > { > if (lc(w)==-1 && rc(w)==-1) w=-1; > else if (lc(w)==-1) w=rc(w),clear(rc(w)); > else if (rc(w)==-1) w=lc(w),clear(lc(w)); > else > { > if (key(rc(w))>key(lc(w))) w=l_rotate(w),lc(w)=del(lc(w),val); > else w=r_rotate(w),rc(w)=del(rc(w),val); > } > } > updata(w); > return w; > } > il int find(int w,int v) > { > if (v<=total(lc(w))) return find(lc(w),v); > else if (v==total(lc(w))+1) return d(w); > else return find(rc(w),v-1-total(lc(w))); > } > int main() > { > int i,j,k,t; > ll now; > //fo("input.txt","r",stdin); fo("output.txt","w",stdout); > srand(time(0)); > for (i=2,step[1]=1; i<=25; i++) step[i]=2*step[i-1]; > for (scanf("%d",&t); t; t--) > { > scanf("%I64d%I64d",&n,&m); m--; > sum=total(0)=0; root=-1; > for (i=1; i<=n; i++) root=ins(root,i); > while (n>1) > { > n--,now=m/step[n],m%=step[n]; > now=find(root,now+1); root=del(root,now); > printf("%d ",now); > } > printf("%d\n",d(root)); > } > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator