Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

类似康托展开的方法。

Posted by yygy at 2014-06-23 15:06:09 on Problem 1037
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator