【hdu 1890】Robotic Sort
HDU Sort
2023-09-14 09:03:50 时间
【题目链接】:http://acm.hdu.edu.cn/showproblem.php?pid=1890
【题意】
给你n个数字;
i从1到n;
每次让你把第i小的数和数组的第i个元素之间这段区间内的数翻转
(第i小的数到了第i个位置);
让你输出每次操作前第i小的数的位置;
【题解】
伸展树的区间翻转以及删除操作;
维护区间的最小值;
for (int i = 1;i <=n;i++)
每次找到最小的数,然后看看它的左子树的大小->cnt;
答案就为i+cnt;
->这个数字在数组中左边的数的个数;
然后把这个数删掉;
(这样每次找最小的数,实际上就在找第i小的数字了);
伸展树里面维护这个区间内最小的数字的节点编号;
这个数的下标(因为值相同的话,下标要优先);
懒惰标记来搞区间翻转就好,只有在找最小值以及找下一个数字的时候要push_down;
splay里面不用push_down;
【Number Of WA】
0
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
#define Open() freopen("F:\\rush.txt","r",stdin)
#define Close() ios::sync_with_stdio(0),cin.tie(0)
#define ls s[0]
#define rs s[1]
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 1e5+7;
const int oo = 21e8;
struct node{
int v,idx,flag,sz;
node *s[2],*f,*mi;
};
int n,cnt = 0;
node A[N],*root;
node *newnode(int v,int idx,node *fa){
node *temp = A + cnt++;
temp ->v = v,temp->idx = idx,temp->ls = temp->rs = 0,temp->mi = temp,temp->flag = 0;
temp->f = fa;
temp->sz = 1;
return temp;
}
bool cmp(node *a,node *b){
if (a->v==b->v)
return a->idx < b->idx;
else
return a->v<b->v;
}
void pushup(node *o){
o->sz = 1;
if (o->ls) o->sz+=o->ls->sz;
if (o->rs) o->sz+=o->rs->sz;
o->mi = o;
if (o->ls && cmp(o->ls->mi,o->mi)) o->mi = o->ls->mi;
if (o->rs && cmp(o->rs->mi,o->mi)) o->mi = o->rs->mi;
}
int dir(node *o) {
return o->f->rs == o;
}
void rotate(node *o) {
int diro = dir(o);
node *f = o->f;
if (o->s[diro ^ 1]) o->s[diro ^ 1]->f = f;
f->s[diro] = o->s[diro ^ 1];
if (f->f) {
if (f->f->ls == f) f->f->s[0] = o;
else f->f->s[1] = o;
}
o->f = f->f;
f->f = o;
o->s[diro ^ 1] = f;
pushup(f);
pushup(o);
}
void fz(node *o){
o->flag^=1;
swap(o->ls,o->rs);
}
void pushdown(node *o){
if (o->flag==0) return;
o->flag = 0;
if (o->ls) fz(o->ls);
if (o->rs) fz(o->rs);
}
void splay(node *o) {
while (o->f) {
if (o->f->f && dir(o) == dir(o->f)) rotate(o->f);
rotate(o);
}
root = o;
}
void cr(int v,int idx){
if (!root){
root = newnode(v,idx,NULL);
}else{
splay(root->rs = newnode(v,idx,root));
}
}
void getmin(){
node *o = root;
while (o!=o->mi){
pushdown(o);
if (o->ls && o->ls->mi == o->mi)
o = o->ls;
else
o = o->rs;
}
pushdown(o);
splay(o);
}
void getnext(){
node * o = root->rs;
while (o->ls){
pushdown(o);
o = o->ls;
}
pushdown(o);
splay(o);
}
int query(){
getmin();
node *o = root;
getnext();
if (o->ls) o->ls->f = root;
root->ls = o->ls;
if (o->ls) fz(o->ls);
pushup(root);
if (root->ls)
return root->ls->sz;
else
return 0;
}
int main(){
// Open();
Close();
while (cin >> n){
if(n==0) break;
root = 0;
cnt = 0;
rep1(i,1,n){
int x;
cin >> x;
cr(x,i);
}
cr(oo,n+1);
rep1(i,1,n){
cout << i + query();
if (i==n)
cout << endl;
else
cout <<' ';
}
}
return 0;
}
相关文章
- HDU 1556-差分数组和线段树的对比分析-Color the ball
- hdu 3980 Paint Chain(SG函数)
- HDU 3336 KMP算法中对next数组的理解「建议收藏」
- HDU P3341 Lost’s revenge 题解+数据生成器
- hdu 3336 Count the string(kmp应用)
- hdu 3336 Count the string 用心写的题解
- Natural Sort: How to sort file names naturally
- hdu 1142_hdu1001
- HDU 3336 Count the string 解题报告
- [ACM] HDU 1006 解题报告
- H - Partial Tree HDU - 5534 【 完全背包 】
- HDU-2084 数塔
- 敌兵布阵(HDU 1166)
- I Hate It (HDU 1754)
- 校庆神秘建筑(HDU 1411)
- 还是畅通工程(HDU 1233)
- Friend-Graph (HDU 6152)2017中国大学生程序设计竞赛 - 网络选拔赛
- CaoHaha's staff (HDU 6154)(2017中国大学生程序设计竞赛 - 网络选拔赛)
- Oil Deposits (HDU - 1241 )(DFS思路 或者 BFS思路)
- 畅通工程续(HDU 1874)(简单最短路)
- Drainage Ditches (HDU - 1532)(最大流)
- Ancient Go ( HDU - 5546 ) ( BFS 搜索是否相连)
- 统计难题 【 HDU - 1251 】【 字典树 】
- Phone List 【 HDU - 1671 】 【 字典树判断是否存在前缀 】
- A * B Problem Plus【HDU 1402】 【FFT求高精度乘法】
- Bone Collector HDU - 2602【 01 背包 】
- set数据结构 探索Redis中Sort Set的魅力(redis中sort)
- Linux Sort降序排列技术探究(linux sort降序)
- byOracle排序展示Sort by的威力(oracle中的sort)