首页 > 代码库 > 1552: [Cerc2007]robotic sort

1552: [Cerc2007]robotic sort

2024-11-25 14:10:02   204人阅读

1552: [Cerc2007]robotic sort

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 1205  Solved: 459

Description

技术分享

Input

输入共两行，第一行为一个整数N，N表示物品的个数，1<=N<=100000。
第二行为N个用空格隔开的正整数，表示N个物品最初排列的编号。

Output

输出共一行，N个用空格隔开的正整数P1,P2,P3…Pn，Pi表示第i次操作前第i小的物品所在的位置。 
注意：如果第i次操作前，第i小的物品己经在正确的位置Pi上，我们将区间[Pi,Pi]反转(单个物品)。

Sample Input

6
3 4 5 1 6 2

Sample Output

4 6 4 5 6 6

code

 注意输出格式。
  1 #include<cstdio>  2 #include<algorithm>  3   4 using namespace std;  5 const int MAXN = 100100;  6 const int INF = 0x7fffffff;  7 struct DATA{  8     int x,p;  9     bool operator < (const DATA &a) const  10     { 11         if (x==a.x) return p < a.p; 12         return x < a.x;  13     } 14 }d[MAXN]; 15 int mn[MAXN],mnpos[MAXN],data[MAXN],siz[MAXN],fa[MAXN],ch[MAXN][2],tag[MAXN]; 16 int n,root; 17  18 int read() 19 { 20     int x = 0,f = 1;char ch = getchar(); 21     while (ch<‘0‘||ch>‘9‘) {if(ch==‘-‘)f=-1; ch=getchar(); } 22     while (ch>=‘0‘&&ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();} 23     return x; 24 } 25 void pushup(int x) 26 { 27     int l = ch[x][0],r = ch[x][1]; 28     mn[x] = min(data[x],min(mn[l],mn[r])); 29     if (mn[x]==data[x]) mnpos[x] = x; 30     else if (mn[x]==mn[l]) mnpos[x] = mnpos[l]; 31     else mnpos[x] = mnpos[r]; 32     siz[x] = siz[l]+siz[r]+1; 33 } 34 void pushdown(int x) 35 { 36     if (tag[x]) 37     { 38         tag[x] = 0; 39         int l = ch[x][0],r = ch[x][1]; 40         tag[l] ^= 1; 41         swap(ch[l][0],ch[l][1]); 42         tag[r] ^= 1; 43         swap(ch[r][0],ch[r][1]); 44     } 45 } 46 int son(int x) 47 { 48     return ch[fa[x]][1]==x; 49 } 50 void rotate(int x) 51 { 52     int y = fa[x],z = fa[y],b = son(x),c = son(y),a = ch[x][!b]; 53     if (z) ch[z][c] = x;else root = x;fa[x] = z; 54     if (a) fa[a] = y;ch[y][b] = a; 55     ch[x][!b] = y;fa[y] = x; 56     pushup(y);pushup(x); 57 } 58 void splay(int &x,int rt) 59 { 60     while (fa[x]!=rt) 61     { 62         int y = fa[x],z = fa[y]; 63         if (z==rt) rotate(x); 64         else 65         { 66             pushdown(z); 67             pushdown(y); 68             pushdown(x); 69             if (son(x)==son(y)) rotate(y),rotate(x); 70             else rotate(x), rotate(x); 71         } 72     } 73 } 74 int getkth(int rt,int k) 75 { 76     pushdown(rt); 77     int l = ch[rt][0],r = ch[rt][1]; 78     if (k==siz[l]+1) return rt; 79     else if (k<siz[l]+1) return getkth(l,k); 80     else return getkth(r,k-siz[l]-1); 81 } 82 int getmnpos(int l,int r) 83 { 84     int tl = getkth(root,l-1); 85     int tr = getkth(root,r+1); 86     splay(tl,0); 87     splay(tr,tl); 88     return mnpos[ch[tr][0]]; 89 } 90 void reverse(int l,int r) 91 { 92     int tl = getkth(root,l-1);//根节点是root  93     int tr = getkth(root,r+1); 94     splay(tl,0); 95     splay(tr,tl); 96     int p = ch[tr][0]; 97     tag[p] ^= 1; 98     swap(ch[p][0],ch[p][1]); 99 }100 int main()101 {102     n = read();103     for (int i=2; i<=n+1; ++i)104     {105         data[i] = read();106         d[i].x = data[i];107         d[i].p = i;108     }109     sort(d+2,d+n+2);110     for (int i=2; i<=n+1; ++i)111         data[d[i].p] = i;112     for (int i=0; i<=n+2; ++i)113         mn[i] = INF;114     data[0] = data[1] = data[n+2] = INF;115     siz[0] = 0;root = 1;116     for (int i=1; i<=n+2; ++i)117     {118         fa[i] = i-1;119         ch[i][1] = i+1;120     }121     ch[n+2][1] = 0;122     for (int i=1; i<=n+2; ++i)123         pushup(i);124     for (int i=1; i<=n; ++i)125     {126         int p = getmnpos(i+1,n+1);127         splay(p,0);128         printf("%d",siz[ch[p][0]]);129         reverse(i+1,siz[ch[p][0]]+1);130         if (i!=n) printf(" ");131     }132     return 0;133 }

 

 

1552: [Cerc2007]robotic sort


联系
我们