BZOJ1552: [Cerc2007]robotic sort-白红宇

强烈建议你试试无所不能的chatGPT，快点击我

BZOJ1552: [Cerc2007]robotic sort

阅读量：4497 次

发布时间：2019-06-08

本文共 4421 字，大约阅读时间需要 14 分钟。

1552: [Cerc2007]robotic sort

Time Limit: 5 Sec Memory Limit: 64 MB

Submit: 1428 Solved: 563

[][][]

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

HINT

Source

【题解】

顺便维护一下子树最小值所在splay的节点即可，想知道节点在序列中的位置，把它splay到根看左子树即可

需要离散化让相等的数按出现顺序从小到大排

1 /**************************************************************  2     Problem: 1552  3     User: 33511595  4     Language: C++  5     Result: Accepted  6     Time:3360 ms  7     Memory:21528 kb  8 ****************************************************************/  9   10 #include 
      
        11 #include 
       
         12 #include 
        
          13 #include 
         
           14 #include 
          
            15 #include 
           
             16 #include 
            
              17 #include 
              18 #include 
              
                19 #include 
               
                 20 #define min(a, b) ((a) < (b) ? (a) : (b)) 21 #define max(a, b) ((a) > (b) ? (a) : (b)) 22 #define abs(a) ((a) < 0 ? (-1 * (a)) : (a)) 23 template 
                
                  24 inline void swap(T& a, T& b) 25 { 26 T tmp = a;a = b;b = tmp; 27 } 28 inline void read(int &x) 29 { 30 x = 0;char ch = getchar(), c = ch; 31 while(ch < '0' || ch > '9') c = ch, ch = getchar(); 32 while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar(); 33 if(c == '-') x = -x; 34 } 35 36 const int INF = 0x3f3f3f3f; 37 const int MAXN = 500000 + 10; 38 39 int ch[MAXN][2], fa[MAXN], n, root, size[MAXN], data[MAXN], mi[MAXN], tag[MAXN]; 40 void ddfs(int x) 41 { 42 if(!x) return; 43 ddfs(ch[x][0]); 44 if(x != 1 && x != n + 2) printf("%d ", data[x]); 45 ddfs(ch[x][1]); 46 } 47 int son(int x){ return x == ch[fa[x]][1];} 48 void pushup(int rt) 49 { 50 int l = ch[rt][0], r = ch[rt][1]; 51 size[rt] = size[l] + size[r] + 1; 52 if(mi[l] == 0) mi[rt] = mi[r]; 53 else if(mi[r] == 0) mi[rt] = mi[l]; 54 else mi[rt] = data[mi[l]] < data[mi[r]] ? mi[l] : mi[r]; 55 mi[rt] = data[mi[rt]] < data[rt] ? mi[rt] : rt; 56 } 57 void pushdown(int rt) 58 { 59 if(!tag[rt]) return; 60 int l = ch[rt][0], r = ch[rt][1]; 61 tag[l] ^= 1, tag[r] ^= 1; 62 swap(ch[l][0], ch[l][1]), swap(ch[r][0], ch[r][1]); 63 tag[rt] = 0; 64 } 65 void rotate(int x) 66 { 67 int y = fa[x], z = fa[y], b = son(x), c = son(y), a = ch[x][!b]; 68 if(z) ch[z][c] = x; else root = x; fa[x] = z; 69 if(a) fa[a] = y; ch[y][b] = a; 70 ch[x][!b] = y, fa[y] = x; 71 pushup(y), pushup(x); 72 } 73 void dfs(int x) 74 { 75 if(!x) return; 76 dfs(fa[x]); 77 pushdown(x); 78 } 79 void splay(int x, int i) 80 { 81 dfs(x); 82 while(fa[x] != i) 83 { 84 int y = fa[x], z = fa[y]; 85 if(z == i) rotate(x); 86 else 87 if(son(x) == son(y)) rotate(y), rotate(x); 88 else rotate(x), rotate(x); 89 } 90 } 91 int getkth(int rt, int x) 92 { 93 pushdown(rt);int l = ch[rt][0]; 94 if(size[l] + 1 == x) return rt; 95 if(x < size[l] + 1) return getkth(ch[rt][0], x); 96 return getkth(ch[rt][1], x - size[l] - 1); 97 } 98 void turn(int l, int r) 99 {100 l = getkth(root, l - 1), r = getkth(root, r + 1);101 // ddfs(root), putchar('\n'); 102 splay(l, 0), splay(r, l);103 // ddfs(root), putchar('\n'); 104 int now = ch[r][0];105 tag[now] ^= 1;swap(ch[now][0], ch[now][1]);pushdown(now);106 }107 //查询节点k的排名 108 int getk(int k)109 {110 splay(k, 0);111 return size[ch[k][0]] + 1;112 }113 int ask_mi(int l, int r)114 {115 l = getkth(root, l - 1), r = getkth(root, r + 1);116 // ddfs(root), putchar('\n'); 117 splay(l, 0), splay(r, l);118 // ddfs(root), putchar('\n'); 119 return getk(mi[ch[r][0]]);120 }121 122 int cnt[MAXN];123 bool cmp(int a, int b)124 {125 return data[a] < data[b];126 }127 128 129 int main()130 {131 memset(data, 0x3f, sizeof(data));132 read(n);133 for(int i = 2;i <= n + 1;++ i) cnt[i] = i, read(data[i]);134 std::stable_sort(cnt + 2, cnt + 2 + n, cmp);135 for(int i = 2;i <= n + 1;++ i) data[cnt[i]] = i; 136 fa[2] = 1, ch[1][1] = 2;size[1] = n + 2;mi[1] = 2;137 for(int i = 2;i <= n + 1;++ i) 138 { 139 ch[i][1] = i + 1, fa[i + 1] = i;size[i] = n + 3 - i;140 mi[i] = i;141 } 142 size[n + 2] = 1;mi[n + 2] = n + 2;root = 1;143 for(int i = n + 2;i >= 1;-- i) pushup(i);144 for(int i = 1;i < n;++ i) 145 {146 int tmp = ask_mi(i + 1, n + 1);147 printf("%d ", tmp - 1);148 turn(i + 1, tmp);149 }150 int tmp = ask_mi(n + 1, n + 1);151 printf("%d\n", tmp - 1);152 return 0;153 }

BZOJ1552

转载于:https://www.cnblogs.com/huibixiaoxing/p/8375749.html

你可能感兴趣的文章

PAT 1014. 福尔摩斯的约会

[Leetcode] Candy

优秀博客地址

《连载 | 物联网框架ServerSuperIO教程》- 8.单例通讯模式开发及注意事项

使用MicroService4Net 快速创建一个简单的微服务

单链表（C++）

配置handler vs2013 iis8.0

LINQ 常用from

mysql优化的一些基本语法

配置带用户权限的docker registry v2

springboot入门

MATLAB的符号运算基础

继续截取长文本显示省略号（多行）

python字符串连接的N种方式

android脚步---简单图片浏览器改变图像透明度

mysql中insert into select from的使用

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！

当前时间: 2024-10-14 23:12:19 当前IP: 3.149.238.40 联系邮箱:javaeecc@qq.com Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2

强烈建议你试试无所不能的CHAT-GPT，快点击我

强烈建议你试试无所不能的CHAT-GPT，快点击我