Luogu P3165 Splay區間翻轉

腦殘記錄:

• 這周末2天隻做了一道平衡樹題目(2天被一道題限住),發現自己的很多問題,
  1. 學了算法及其性質 但是總是做不出來題目,很難利用學過的性質, 同樣這種情況再次發生在今天
  2. 沒有運用的能力,思維太差???

• 反思:
  1. 自己對算法題目的思維能力 還是不行 ( ？？？一定要想辦法改變？？？ )
  2. 要對自己的學過的算法的流程 好好走一遍,

Splay 練習 Luogu P3165

• 即使 S p l a y Splay Splay後中序周遊還是不變的. 不要和二叉查找樹的左子樹節點權值小于子樹根節點小于右子樹節點權值 這個性質搞混了！！！！
• 前驅和後繼求的都是在樹中節點存的值的意義 (視具體情況
• 如果 S p l a y Splay Splay用來區間翻轉即節點存的是下标, 則 s i z e [ x ] size[x] size[x]數組意義是樹節點 x x x存的值(下标)所代表的數列值在數列中的位置(第幾個or前面有幾個數列值, 用 中序周遊保持不變這一性質來了解

1. 此題 樹節點存下标沒啥作用, 技巧:

   pos[val]

   代表: 數列值 v a l val val所在樹節點的編号, (這樣直接O(1)就找到值對應的樹節點了,)
2. 值都在 ( 1 , n ) (1,n) (1,n)區間中, 把重複值去掉,把重複的第一個放在前面

非常難受,卡我很長時間,

• 如何找到區間下标

  [1,p1],[2,p2],[3,p3]...

  中的

  1,2,3

  在樹中的編号,不然怎麼旋轉???
  1. S p l a y Splay Splay樹的操作 , k t h kth kth,
  2. 注意到每一次都把最小值剛好旋轉到數列開頭,而且我們要找 l − 1 l-1 l−1的下标,恰好直接利用 p o s [ i − 1 ] pos[i-1] pos[i−1]就行
  • 效率差不多

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;

int ch[maxn][2],fa[maxn],size[maxn],val[maxn],tag[maxn],pos[maxn];
int tot,root,n;

struct node { int id,val; } a[maxn];

bool cmp1(node &test1,node &test2) {
    return test1.val < test2.val || (test1.val==test2.val && test1.id<test2.id);
}

bool cmp2(node &test1,node &test2) { return test1.id < test2.id; }

void maintain(int x) {
    if (x) size[x] = size[ch[x][0]] + size[ch[x][1]] + 1;
}

bool get(int x) { return x == ch[fa[x]][1]; }

void pushdown(int x) {
    if (!x || !tag[x]) return ;
    tag[ch[x][0]] ^= 1;
    tag[ch[x][1]] ^= 1;
    swap(ch[x][0],ch[x][1]);
    tag[x] = 0;
}

void rotate(int x) {
    pushdown(fa[x]),pushdown(x);
    int y=fa[x],z=fa[y],chk=get(x);

    ch[y][chk] = ch[x][chk^1];
    fa[ch[x][chk^1]] = y;
    ch[x][chk^1] = y;
    fa[y] = x;
    fa[x] = z;
    if (z) ch[z][y == ch[z][1]] = x;

    maintain(y);
    maintain(x);
}

void splay(int x,int tar) {
    for (int father; (father=fa[x])!=tar; rotate(x))
        if (fa[father] != tar) rotate(get(x) == get(father) ? father : x);
    if (!tar)
        root = x;
}

int nxt() {
    pushdown(root);
    int cur = ch[root][1];
    while (pushdown(cur),ch[cur][0]) cur = ch[cur][0];
    return cur;
}

int build(int l,int r,int father) {
    if (l > r) return 0;
    int mid = (l+r)>>1,now = ++tot;
    pos[a[mid].val]=now,val[now]= a[mid].id,fa[now]=father,tag[now]=0;
    ch[now][0] = build(l,mid-1,now);
    ch[now][1] = build(mid+1,r,now);
    maintain(now);
    return now;
}

int kth(int k) {
    int now = root;
    while (1) {
        pushdown(now);
        if (ch[now][0] && k <= size[ch[now][0]])
            now = ch[now][0];
        else {
            k -= size[ch[now][0]] + 1;
            if (k <= 0) return now;
            now = ch[now][1];
        }
    }
}

void prepare() {
    a[1].id=1,a[1].val=0;
    a[n+2].id=n+2,a[n+2].val=n+1;
    for (int i=1; i<=n; ++i) {
        cin >> a[i+1].val;
        a[i+1].id = i+1;
    }
    sort(a+2,a+2+n,cmp1);
    for (int i=1; i<=n; ++i) a[i+1].val = i;
    sort(a+2,a+2+n,cmp2);
}

int main() {
    cin >> n;
    prepare();
    root = build(1,n+2,0);
    for (int i=1; i<=n; ++i) {
        int x = pos[i];
        splay(x,0);
        cout << size[ch[x][0]] << " ";
        x = nxt();
        //int y = pos[i-1];
        int y = kth(i); // 比上面注釋的稍微慢一點
        splay(y,0);
        splay(x,y);
        tag[ch[x][0]] ^= 1;
    }
    return 0;
}
           

• 先前一直調式的版本,

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;

int ch[maxn][2],fa[maxn],size[maxn],val[maxn],tag[maxn],pos[maxn];
int tot,root,n;
//int a[maxn];
struct node {
    int id,val;
} a[maxn];

bool cmp1(node &test1,node &test2) {
    return test1.val<test2.val || (test1.val==test2.val && test1.id<test2.id);
}
bool cmp2(node &test1,node &test2) { return test1.id < test2.id; }

void maintain(int x) {
    if (x)
        size[x] = size[ch[x][0]] + size[ch[x][1]] + 1;
}

int get(int x) {
    return x == ch[fa[x]][1];
}

void pushdown(int x) {
    if (!x || !tag[x]) return ;
    tag[ch[x][0]] ^= 1;
    tag[ch[x][1]] ^= 1;
    swap(ch[x][0],ch[x][1]);
    tag[x] = 0;
}

void rotate(int x) {
    pushdown(fa[x]);
    pushdown(x);
    int y=fa[x],z=fa[y],chk=get(x);
    ch[y][chk] = ch[x][chk^1];
    fa[ch[x][chk^1]] = y;
    ch[x][chk^1] = y;
    fa[y] = x;
    fa[x] = z;
    if (z) ch[z][y == ch[z][1]] = x;
    maintain(y);
    maintain(x);
}

void splay(int x,int tar) {
    for (int father; (father=fa[x])!=tar; rotate(x))
        if (fa[father]!=tar) rotate(get(x)==get(father)?father:x);
    if (!tar)
        root = x;
}

int kth(int k) {
    int now = root;
    while (1) {
        pushdown(now);
        if (ch[now][0] && k <= size[ch[now][0]])
            now = ch[now][0];
        else {
            k -= size[ch[now][0]] + 1;
            if (k <= 0) return now;
            now = ch[now][1];
        }
    }
}

int build(int l,int r,int father) {
    if (l > r) return 0;
    int mid = (l+r)>>1;
    int now = ++tot;
    pos[a[mid].val] = now,val[now] = a[mid].id,fa[now]=father;tag[now]=0;
    ch[now][0] = build(l,mid-1,now);
    ch[now][1] = build(mid+1,r,now);
    maintain(now);
    return now;
}

void dfs(int now) {
    pushdown(now);
    if (ch[now][0]) dfs(ch[now][0]);
    cout << a[val[now]].val << " ";
    if (ch[now][1]) dfs(ch[now][1]);
}

int nxt() {
    pushdown(root);
    int cur = ch[root][1];
    while (pushdown(cur),ch[cur][0]) cur = ch[cur][0];
    return cur;
}

int m;

int main() {
    //cin >> n;
    scanf("%d",&n);
    a[1].id = 1,a[1].val=0;
    a[n+2].id = n+2,a[n+2].val = n+1;
    for (int i=1; i<=n; ++i) {
        cin >> a[i+1].val;
        a[i+1].id = i+1;
    }
    sort(a+2,a+2+n,cmp1);
    for (int i=1; i<=n; ++i)
        a[i+1].val = i;
    sort(a+2,a+2+n,cmp2);
    root = build(1,n+2,0);
    dfs(root);
    for (int i=1; i<=n; ++i) {
        int x = pos[i];
        splay(x,0);
        //cout << size[ch[x][0]] << " ";
        printf("%d ",size[ch[x][0]]);
        x = nxt();
        int y = pos[i-1];
        splay(y,0);
        splay(x,y);
        tag[ch[x][0]] ^= 1;
    }
    return 0;
}
           

• 自己有時候思維太死了！！！艹