速度居然進前十了...第八...

?

splay, 區間翻轉,用一個類似線段樹的lazy標記表示是否翻轉

----------------------------------------------------------------------------------------

#include<cstdio>#include<algorithm>#include<cstring>#include<iostream>#define rep(i, n) for(int i = 0; i < n; ++i)#define clr(x, c) memset(x, c, sizeof(x))using namespace std;const int maxn = 100000 + 5;int n;struct node *null, *pt;struct node {? ? node* ch[2];? ? int v, s;? ? bool flip;? ? node(int _v = 0) : v(_v), s(1), flip(0) {? ? ? ? ch[0] = ch[1] = null;? ? }? ? inline int cmp(int k) const {? ? ? ? k -= ch[0]->s;? ? ? ? if(k == 1) return -1;? ? ? ? return k <= 0 ? 0 : 1;? ? }? ? inline void maintain() {? ? ? ? s = ch[0]->s + ch[1]->s + 1;? ? }? ? inline void pushdown() {? ? ? ? if(flip) {? ? ? ? ? ? flip = 0;? ? ? ? ? ? swap(ch[0], ch[1]);? ? ? ? ? ? ch[0]->flip ^= 1;? ? ? ? ? ? ch[1]->flip ^= 1;? ? ? ? }? ? }? ? void *operator new (size_t) { return pt++; }};node* root;node N[maxn], Null;void rotate(node* &o, int d) {? ? node* k = o->ch[d^1];? ? o->ch[d^1] = k->ch[d];? ? k->ch[d] = o;? ? o->maintain(); k->maintain();? ? o = k;}void splay(node* &o, int k) {? ? o->pushdown();? ? int d = o->cmp(k);? ? if(d == 1) k -= o->ch[0]->s + 1;? ? if(d != -1) {? ? ? ? node* p = o->ch[d];? ? ? ? p->pushdown();? ? ? ? int d2 = p->cmp(k);? ? ? ? int k2 = d2 ? k - p->ch[0]->s - 1 : k;? ? ? ? if(d2 != -1) {? ? ? ? ? ? splay(p->ch[d2], k2);? ? ? ? ? ? d == d2 ? rotate(o, d^1) : rotate(o->ch[d], d);? ? ? ? }? ? ? ? rotate(o, d^1);? ? }}node* build(int l, int r) {? ? if(l >= r) return null;? ? int m = (l + r) >> 1;? ? node* o = new node(m);? ? if(l < m) o->ch[0] = build(l, m);? ? if(m + 1 < r) o->ch[1] = build(m + 1, r);? ? o->maintain();? ? return o;}void init() { pt = N; null = &Null; null->s = 0; root = build(0, n + 2); }void dfs(node* o) {? ? if(o == null) return;? ? o->pushdown();? ? dfs(o->ch[0]);? ? if(o->v >= 1 && o->v <= n) printf("%d ",o->v);? ? dfs(o->ch[1]);}inline int read() {int ans = 0, f = 1;char c = getchar();while(!isdigit(c)) {if(c == '-') f = -1;c = getchar();}while(isdigit(c)) {ans = ans * 10 + c - '0';c = getchar();}return f * ans;}int main() {? ? n = read();? ? int m = read();? ? init();? ? while(m--) {int l = read(), r = read();? ? ? ? if(l == r) continue;? ? ? ? splay(root, l);? ? ? ? splay(root->ch[1], r + 1 - root->ch[0]->s);? ? ? ? root->ch[1]->ch[0]->flip ^= 1;? ? }? ? dfs(root);? ? return 0;}

??

----------------------------------------------------------------------------------------?

3223: Tyvj 1729 文藝平衡樹

Time Limit:?10 Sec??Memory Limit:?128 MB
Submit:?1675??Solved:?931
[Submit][Status][Discuss]

Description

您需要寫一種數據結構（可參考題目標題），來維護一個有序數列，其中需要提供以下操作：翻轉一個區間，例如原有序序列是5?4?3?2?1，翻轉區間是[2,4]的話，結果是5?2?3?4?1?

Input

第一行為n,m?n表示初始序列有n個數，這個序列依次是(1,2……n-1,n)??m表示翻轉操作次數
接下來m行每行兩個數[l,r]?數據保證?1<=l<=r<=n?

Output

?

輸出一行n個數字，表示原始序列經過m次變換后的結果?

Sample Input

5 3

1 3

1 3

1 4

Sample Output

4 3 2 1 5

HINT

N,M<=100000

Source

平衡樹

?

轉載于:https://www.cnblogs.com/JSZX11556/p/4468791.html

總結

以上是生活随笔為你收集整理的BZOJ 3223: Tyvj 1729 文艺平衡树(splay)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。