题目：http://acm.hdu.edu.cn/showproblem.php?pid=1890
伸展树，按照题意模拟，把所求第i个节点旋转至根节点，reverse一下
View Code
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define keytree root->ch[1]->ch[0] using namespace std; const int M = 100000+10; const int inf = 0x3f3f3f3f; struct node { int size, rev, key; node *ch[2], *pre; void reverse() { if (size == 0)return ; rev ^= 1; swap(ch[0], ch[1]); } void update() { size = ch[0]->size + ch[1]->size + 1; } void pushdown() { if (rev) ch[0]->reverse(), ch[1]->reverse(), rev = 0; } }; int arr[M]; node * hash[M]; class Splay { public: node *root, *null; node *newnode(int var) { node *p; if (top) p = stk[top--]; else p = &data[cnt++]; p->key = var; p->size = 1; p->rev = 0; p->ch[0] = p->ch[1] = p->pre = null; return p; } void init() { top = cnt = 0; null = newnode(inf); null->size = 0; root = newnode(inf); root->ch[1] = newnode(inf); root->ch[1]->pre = root; root->update(); } node *build(int l, int r) { if (l > r) return null; int mid = (l + r) >> 1; node *p = newnode(arr[mid]); hash[arr[mid]] = p; p->ch[0] = build(l, mid-1); p->ch[1] = build(mid+1, r); if (p->ch[0] != null) p->ch[0]->pre = p; if (p->ch[1] != null) p->ch[1]->pre = p; p->update(); return p; } void maketree(int l, int r) { init(); keytree = build(l, r); keytree->pre = root->ch[1]; splay(keytree, null); } void rotate(node *x, int c) { node *y = x->pre; y->pushdown(); x->pushdown(); y->ch[!c] = x->ch[c]; if (x->ch[c] != null) x->ch[c]->pre = y; x->pre = y->pre; if (y->pre != null) y->pre->ch[ y==y->pre->ch[1] ] = x; x->ch[c] = y; y->pre = x; y->update(); if (y == root) root = x; } void splay(node *x, node *f) { x->pushdown(); while (x->pre != f) { if (x->pre->pre == f) { rotate(x, x->pre->ch[0] == x); break; } node *y = x->pre; node *z = y->pre; int c = (y == z->ch[0]); if (x == y->ch[c]) rotate(x, !c), rotate(x, c); else rotate(y, c), rotate(x, c); } x->update(); } void select(int kth, node *x) { node * cur = root; while (true) { cur->pushdown(); int tmp = cur->ch[0]->size; if (tmp == kth) break; else if (tmp < kth) kth -= tmp + 1, cur = cur->ch[1]; else cur = cur->ch[0]; } splay(cur, x); } void reverse(int x, int y) { select(x-1, null); select(y+1, root); keytree->reverse(); } int getans(int x, int y) { splay(hash[y], null); // 第y个转换至根节点 int ans = root->ch[0]->size; // 求出数目 reverse(x, ans); // 反转一下 return ans; } private: int cnt, top; node *stk[M], data[M]; }spt; struct Num { int x, y; bool operator < (const Num& a)const { if (x == a.x) return y < a.y; return x < a.x; } }num[M]; int main() { int n, a; while (~scanf("%d", &n) && n) { for (int i=1; i<=n; i++) scanf("%d", &a), num[i].x = a, num[i].y = i, arr[i] = i; sort(num+1, num+n+1); spt.maketree(1, n); for (int i=1; i<n; i++) { printf("%d ", spt.getans(i, num[i].y)); } printf("%d\n", n); } return 0; }