题目
https://vjudge.net/problem/Gym-247729C
题意
给出 n，m 表示初始序列 1 ~ n 以及 m 个操作，每个操作是将 p 位置开始之后的 s 个数放至最前面。
题解
题意十分简单，可是做不粗来，蒟蒻的我。首先可以想到，将一段区间 [ l, r ] 放至最前方可以通过翻转 [ 1, l - 1 ] , [ l, r ] , [ 1, r ] 三个步骤得到，这样就转化成了 splay 的经典用法。这也是第一次学到splay。
#include <bits/stdc++.h> // #include <iostream> // #include <cstring> // #include <string> // #include <algorithm> // #include <cmath> // #include <cstdio> // #include <queue> // #include <stack> // #include <map> // #include <bitset> // #include <set> // #include <vector> // #include <iomanip> #define ll long long #define ull unsigned long long #define met(a, b) memset(a, b, sizeof(a)) #define rep(i, a, b) for(int i = a; i <= b; ++i) #define bep(i, a, b) for(int i = a; i >= b; --i) #define lowbit(x) (x&(-x)) #define MID (l + r) / 2 #define ls pos*2 #define rs pos*2+1 #define pb push_back #define ios() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; const int maxn = 1e6 + 1010; const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3f; const ll mod = 1e9 + 7; const double eps = 1e-4; const double PI = acos(-1); struct Splay_tree { int val, fa, sub_size, now_size, tag; int son[2]; }tree[maxn]; int root; int arr[maxn]; int cnt; int if_; void push_down(int x) { if(x && tree[x].tag) { tree[tree[x].son[0]].tag ^= 1; tree[tree[x].son[1]].tag ^= 1; tree[x].tag = 0; swap(tree[x].son[0], tree[x].son[1]); } } void update(int x) { if(x) { tree[x].sub_size = tree[x].now_size; tree[x].sub_size += tree[tree[x].son[0]].sub_size; tree[x].sub_size += tree[tree[x].son[1]].sub_size; } } int build_tree(int l, int r, int fa) { if(l > r) return 0; int mid = MID; int now = ++cnt; tree[now].val = arr[mid]; tree[now].fa = fa; tree[now].now_size = 1; tree[now].tag = 0; tree[now].son[0] = build_tree(l, mid - 1, now); tree[now].son[1] = build_tree(mid + 1, r, now); update(now); return now; } void rotate(int x) { int fx = tree[x].fa, ffx = tree[fx].fa; int k = (tree[fx].son[1] == x); push_down(fx); push_down(x); tree[fx].son[k] = tree[x].son[k ^ 1]; tree[tree[fx].son[k]].fa = fx; tree[x].son[k ^ 1] = fx; tree[fx].fa = x; tree[x].fa = ffx; if(ffx) tree[ffx].son[tree[ffx].son[1] == fx] = x; update(fx); update(x); } void splay(int x, int goal) { while(tree[x].fa != goal) { int y = tree[x].fa, z = tree[y].fa; if(z != goal) { ((tree[z].son[1] == y) == (tree[y].son[1] == x)) ? rotate(y) : rotate(x); } rotate(x); } if(!goal) root = x; } int find(int x) { int now = root; while(1) { push_down(now); if(x <= tree[tree[now].son[0]].sub_size) { now = tree[now].son[0]; } else { x -= tree[tree[now].son[0]].sub_size + 1; if(!x) return now; now = tree[now].son[1]; } } } void Reverse(int x, int y) { int l = find(x - 1); int r = find(y + 1); splay(l, 0); splay(r, l); int pos = tree[r].son[0]; tree[pos].tag ^= 1; } void dfs(int x) { push_down(x); if(tree[x].son[0]) dfs(tree[x].son[0]); if(tree[x].val != inf && tree[x].val != -inf) { if(if_) cout << ' '; else if_ = 1; cout << tree[x].val; } if(tree[x].son[1]) dfs(tree[x].son[1]); } int main() { int n, m; cin >> n >> m; rep(i, 2, n + 1) arr[i] = i - 1; arr[1] = -inf; arr[n + 2] = inf; //前后加入数据是为了防止 reverse(1, n) 这种边界时 find 出错。 root = build_tree(1, n + 2, 0); rep(i, 1, m) { int pos, len; cin >> pos >> len; int l = pos + 1, r = l + len - 1; Reverse(l, r); Reverse(2, l - 1); Reverse(2, r); } dfs(root); return 0; }