最终得对抗自己

平衡树专题练习

开始进入平衡树时代!

BZOJ 2258

题目大意: 给你一个串, 支持插入和从某个位置查询匹配两种操作。
插入最多200次。

解题报告

很显然的平衡树嘛!
咦为什么插入只有200个QAQ
果断哈希暴力

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <iostream>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int MAXL = 52050;
const ULL SEED = 31;
char str[MAXL];
ULL hashc[MAXL], powr[MAXL];
int len;
inline void rebuild () {
    for(int i = 1; i<=len; i++)
        hashc[i] = hashc[i-1]*SEED+str[i];
}
int query (int a, int b) {
    int l = 0, r = min(len-a, len-b), ans = -1;
    while(l <= r) {
        int mid = (l+r)>>1;
        if(hashc[a+mid]-hashc[a-1]*powr[mid+1]
        == hashc[b+mid]-hashc[b-1]*powr[mid+1])
            l = mid+1, ans = mid;
        else r = mid-1;
    }
    return ans+1;
}
int sum[MAXL], pos[MAXL];
int main () {
    scanf("%s", str+1);
    len = strlen(str+1);
    int tlen = len;
    powr[0] = 1;
    for(int i = 1; i<=len+220; i++) powr[i] = powr[i-1]*SEED;
    rebuild();
    char buf[5]; int Q;
    scanf("%d", &Q);
    for(int i = 1; i<=tlen; i++) pos[i] = i;
    while(Q --) {
        scanf("%s", buf);
        if(buf[0] == 'Q') {
            int a, b;
            scanf("%d%d", &a, &b);
            printf("%d\n", query(pos[a], pos[b]));
        } else {
            int p;
            scanf("%s%d", buf, &p);
            if(p > len) p = len;
            for(int i = len; i>=p; i--) str[i+1] = str[i];
            ++ len;
            for(int i = 1; i<=tlen; i++) if(pos[i] >= p) pos[i]++;
            str[p] = buf[0];
            rebuild();
        }
    }
}

BZOJ 3786

题目大意: 给你一颗树, 支持三种操作:
1.子树加
2.树链和
3.单点修改父亲

解题报告

动态树LCT上维护奇怪的标记貌似可以搞。
但是用Splay维护dfn序上差分貌似更好写而且更快。
据说这就是ETT?算了不管那么多了写!

代码

#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <climits>
#include <cstdio>
#include <set>
#include <iostream>
using namespace std;
typedef long long LL;
const int MAXN = 100010;
namespace Splay {
    const int MAXD = MAXN*2;
    struct Node {
        int ch[2], fa;
        int delta;
        LL sum, val, lz;
        int flg;
    } d[MAXD];
    int dtot, root;
    inline void updata (int u) {
        d[u].sum = d[d[u].ch[0]].sum+d[u].val+d[d[u].ch[1]].sum;
        d[u].delta = d[d[u].ch[0]].delta+d[u].flg+d[d[u].ch[1]].delta;
    }
    inline int newNode (int val) {
        ++ dtot;
        if(val >= 0) d[dtot].val = val, d[dtot].flg = 1;
        else d[dtot].val = val+1, d[dtot].flg = -1;
        updata(dtot);
        return dtot;
    }
    int * src, * uid;
    int build (int l, int r) {
        if(l > r) return 0;
        if(l == r) return uid[l] = newNode(src[l]);
        int mid = (l+r)>>1;
        int u = uid[mid] = newNode(src[mid]);
        d[d[u].ch[0] = build(l, mid-1)].fa = u;
        d[d[u].ch[1] = build(mid+1, r)].fa = u;
        updata(u);
        return u;
    }
    inline void add (int u, LL v) {
        if(!u) return ;
        d[u].val += v*d[u].flg;
        d[u].lz += v;
        d[u].sum += (LL)v*d[u].delta;
    }
    inline void pushdown (int u) {
        if(d[u].lz) {
            add(d[u].ch[0], d[u].lz);
            add(d[u].ch[1], d[u].lz);
            d[u].lz = 0;
        }
    }
    inline void downlazy (int u) {
        if(d[u].fa) downlazy(d[u].fa);
        pushdown(u);
    }
    inline void rotate (int x) {
        int y = d[x].fa;
        bool f = d[y].ch[1] == x;
        d[y].ch[f] = d[x].ch[!f];
        d[d[y].ch[f]].fa = y;
        d[x].ch[!f] = y;
        d[x].fa = d[y].fa;
        d[y].fa = x;
        d[d[x].fa].ch[d[d[x].fa].ch[1] == y] = x;
        updata(y), updata(x);
    }
    void splay (int x, int g) {
        downlazy(x);
        while(d[x].fa != g) {
            int y = d[x].fa, z = d[y].fa;
            if(z != g) {
                if((d[z].ch[1] == y) == (d[y].ch[1] == x)) rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
        updata(x);
        if(g == 0) root = x;
    }
    inline int getNext (int u, bool f) {
        splay(u, 0), u = d[u].ch[f], pushdown(u);
        while(d[u].ch[!f]) u = d[u].ch[!f], pushdown(u);
        return u;
    }
    inline int getInterval (int a, int b) {
        int pre = getNext(a, false), suc = getNext(b, true);
        splay(pre, 0), splay(suc, pre);
        return d[suc].ch[0];
    }
    inline void insertAfter (int u, int ins) {
        d[d[ins].fa].ch[d[d[ins].fa].ch[1] == ins] = 0;
        if(d[ins].fa) splay(d[ins].fa, 0);
        int nxt = getNext(u, true);
        d[nxt].ch[0] = ins, d[ins].fa = nxt;
        splay(ins, 0);
    }
    inline LL value (int u) {
        return d[u].sum;
    }
}
struct Node {
    int v, nxt;
} adj[MAXN];
int head[MAXN], etot;
inline void addEdge (int a, int b) {
    etot ++;
    adj[etot].v = b;
    adj[etot].nxt = head[a];
    head[a] = etot;
}
int src[MAXN*2], uid[MAXN*2];
int dfn[MAXN], lst[MAXN], dfntot;
int W[MAXN];
void dfs (int u) {
    src[dfn[u] = ++dfntot] = W[u];
    for(int e = head[u]; e; e = adj[e].nxt)
        dfs(adj[e].v);
    src[lst[u] = ++dfntot] = -W[u]-1;
}
inline int getInt () {
    int ret = 0; char ch; bool flg = false;
    while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-');
    ret = ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+ch-'0';
    return flg ? -ret : ret;
}
char buf[12];
int main () {
    int N = getInt();
    for(int i = 2; i<=N; i++) addEdge(getInt(), i);
    for(int i = 1; i<=N; i++) W[i] = getInt();
    dfs(1);
    Splay::src = src, Splay::uid = uid;
    Splay::root = Splay::build(0, dfntot+1);
    int M = getInt();
    while(M --) {
        scanf("%s", buf);
        if(buf[0] == 'Q')
            printf("%lld\n", Splay::value(Splay::getInterval(uid[dfn[1]], uid[dfn[getInt()]])));
        else if(buf[0] == 'C') {
            int a = getInt(), b = getInt();
            int inv = Splay::getInterval(uid[dfn[a]], uid[lst[a]]);
            Splay::insertAfter(uid[dfn[b]], inv);
        } else {
            int x = getInt();
            Splay::add(Splay::getInterval(uid[dfn[x]], uid[lst[x]]), getInt());
        }
    }
}

BZOJ 1251

题目大意: 给个序列, 要求支持区间翻转, 区间加减, 区间最大值。

解题报告

题目名称看起来好可怕的样子..然而这就是个水题。
注意把0号节点设成-INF。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
using namespace std;
typedef long long LL;
const int MAXN = 50050;
namespace Splay {
    const int MAXD = MAXN;
    struct Node {
        int ch[2], fa;
        int val, mxv, lz;
        bool rev;
        int sz;
    } d[MAXD];
    int root;
    inline void initialize () {d[0].mxv = INT_MIN;}
    inline void updata (int u) {
        d[u].sz = d[d[u].ch[0]].sz+1+d[d[u].ch[1]].sz;
        d[u].mxv = max(d[u].val, max(d[d[u].ch[0]].mxv, d[d[u].ch[1]].mxv));
    }
    inline void add (int u, int val) {
        if(!u) return ;
        d[u].val += val;
        d[u].lz += val;
        d[u].mxv += val;
    }
    inline void filp (int u) {
        d[u].rev ^= 1;
        swap(d[u].ch[0], d[u].ch[1]);
    }
    inline void pushdown (int u) {
        if(d[u].rev) {
            filp(d[u].ch[0]);
            filp(d[u].ch[1]);
            d[u].rev = false;
        }
        if(d[u].lz) {
            add(d[u].ch[0], d[u].lz);
            add(d[u].ch[1], d[u].lz);
            d[u].lz = 0;
        }
    }
    inline void downlazy (int u) {
        if(d[u].fa) downlazy(d[u].fa);
        pushdown(u);
    }
    inline void rotate (int x) {
        int y = d[x].fa;
        bool f = d[y].ch[1] == x;
        d[y].ch[f] = d[x].ch[!f];
        d[d[y].ch[f]].fa = y;
        d[x].ch[!f] = y;
        d[x].fa = d[y].fa;
        d[y].fa = x;
        if(d[x].fa) d[d[x].fa].ch[d[d[x].fa].ch[1] == y] = x;
        updata(y), updata(x);
    }
    int splay (int x, int g) {
        downlazy(x);
        while(d[x].fa != g) {
            int y = d[x].fa;
            int z = d[y].fa;
            if(z != g) {
                if((d[z].ch[1] == y) == (d[y].ch[1] == x))
                    rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
        updata(x);
        if(g == 0) root = x;
        return x;
    }
    int dtot;
    inline int newNode (int val) {
        dtot ++;
        d[dtot].val = val;
        updata(dtot);
        return dtot;
    }
    int * src;
    int build (int l, int r) {
        if(l > r) return 0;
        if(l == r) return newNode(src[l]);
        int mid = (l+r)>>1;
        int u = newNode(src[mid]);
        d[d[u].ch[0] = build(l, mid-1)].fa = u;
        d[d[u].ch[1] = build(mid+1, r)].fa = u;
        updata(u);
        return u;
    }
    int getByRank (int rk) {
        rk++;
        int u = root;
        while(u) {
            pushdown(u);
            if(d[d[u].ch[0]].sz >= rk) u = d[u].ch[0];
            else if(d[d[u].ch[0]].sz+1 == rk) return u;
            else rk -= d[d[u].ch[0]].sz+1, u = d[u].ch[1];
        }
        return -1;
    }
    int getIntervalN (int a, int b) {
        splay(a, 0), splay(b, a);
        return d[b].ch[0];
    }
    int getMaxv (int u) {return d[u].mxv;}
}
int src[MAXN];
inline int getInt () {
    int ret = 0; char ch; bool flg = false;
    while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-');
    ret = ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+ch-'0';
    return flg ? -ret : ret;
}
int main () {
    Splay::initialize();
    int N = getInt(), M = getInt();
    Splay::src = src, Splay::root = Splay::build(0, N+1);
    for(int i = 1; i<=M; i++) {
        int oper = getInt();
        int l = getInt(), r = getInt();
        int inv = Splay::getIntervalN(Splay::getByRank(l-1), Splay::getByRank(r+1));
        if(oper == 1) Splay::add(inv, getInt());
        else if(oper == 2) Splay::filp(inv);
        else printf("%d\n", Splay::getMaxv(inv));
    }
}

BZOJ 1861

题目大意: 我这么懒, 不存在的…

解题报告

Splay, 注意自己插到自己后面这种情况特判。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
using namespace std;
typedef long long LL;
const int MAXN = 160080;
namespace Splay {
    const int MAXD = MAXN;
    struct Node {
        int ch[2], fa;
        int sz, val;
    } d[MAXD];
    int root, dtot;
    inline void updata (int u) {
        d[u].sz = d[d[u].ch[0]].sz+d[d[u].ch[1]].sz+1;
    }
    inline int newNode (int val) {
        ++ dtot;
        d[dtot].val = val;
        updata(dtot);
        return dtot;
    }
    int * src, * uid;
    int build (int l, int r) {
        if(l > r) return 0;
        if(l == r) return uid[l] = newNode(src[l]);
        int mid = (l+r)>>1;
        int u = uid[mid] = newNode(src[mid]);
        d[d[u].ch[0] = build(l, mid-1)].fa = u;
        d[d[u].ch[1] = build(mid+1, r)].fa = u;
        updata(u);
        return u;
    }
    inline void rotate (int x) {
        int y = d[x].fa;
        bool f = d[y].ch[1] == x;
        d[y].ch[f] = d[x].ch[!f];
        d[d[y].ch[f]].fa = y;
        d[x].ch[!f] = y;
        d[x].fa = d[y].fa;
        d[y].fa = x;
        d[d[x].fa].ch[d[d[x].fa].ch[1] == y] = x;
        updata(y), updata(x);
    }
    inline int splay (int x, int g) {
        while(d[x].fa != g) {
            int y = d[x].fa;
            int z = d[y].fa;
            if(z != g) {
                if((d[z].ch[1] == y) == (d[y].ch[1] == x)) rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
        updata(x);
        if(g == 0) root = x;
        return x;
    }
    inline int getByRank (int rk) {
        rk++;
        int u = root;
        while(u) {
            if(d[d[u].ch[0]].sz >= rk) u = d[u].ch[0];
            else if(d[d[u].ch[0]].sz+1 == rk) return u;
            else rk -= d[d[u].ch[0]].sz+1, u = d[u].ch[1];
        }
        return -1;
    }
    inline int getNext (int u, bool f) {
        splay(u, 0);
        u = d[u].ch[f];
        while(d[u].ch[!f]) u = d[u].ch[!f];
        return u;
    }
    inline int erase (int u) {
        int pre = getNext(u, false), suc = getNext(u, true);
        splay(pre, 0), splay(suc, pre);
        d[suc].ch[0] = 0; splay(suc, 0);
        return u;
    }
    inline void insertAfter (int u, int ins) {
        if(u == ins) return ;
        int nxt = getNext(u, true);
        splay(u, 0), splay(nxt, u);
        d[ins].fa = nxt, d[nxt].ch[0] = ins;
        splay(ins, 0);
    }
    inline int getFront (int u) {
        splay(u, 0);
        return d[d[u].ch[0]].sz-1;
    }
    inline int getValue (int u) {return d[u].val;}
}
inline int getInt () {
    int ret = 0; char ch; bool flg = false;
    while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-');
    ret = ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+ch-'0';
    return flg ? -ret : ret;
}
int src[MAXN], uid[MAXN], rev[MAXN];
char buf[18];
int main () {
    int N = getInt(), M = getInt();
    for(int i = 1; i<=N; i++) src[i] = getInt();
    for(int i = 1; i<=N; i++) rev[src[i]] = i;
    Splay::src = src, Splay::uid = uid;
    Splay::root = Splay::build(0, N+1);
    for(int i = 1; i<=M; i++) {
        scanf("%s", buf);
        if(buf[0] == 'Q') printf("%d\n", Splay::getValue(Splay::getByRank(getInt())));
        else if(buf[0] == 'T') {
            int x = Splay::erase(uid[rev[getInt()]]);
            Splay::insertAfter(Splay::getByRank(0), x);
        } else if(buf[0] == 'B') {
            int x = Splay::erase(uid[rev[getInt()]]);
            Splay::insertAfter(Splay::getByRank(N-1), x);
        } else if(buf[0] == 'A') printf("%d\n", Splay::getFront(uid[rev[getInt()]]));
        else if(buf[0] == 'I') {
            int x = uid[rev[getInt()]];
            int rk = Splay::getFront(x)+getInt();
            Splay::erase(x);
            int y = Splay::getByRank(rk);
            Splay::insertAfter(y, x);
        }
    }
}
/*
10 100
1 3 2 7 5 8 10 4 9 6
*/

BZOJ 1014

题目大意: 写一个支持动态插入和修改以及询问A和B开始的LCP的数据结构。

解题报告

BZOJ2258正常版, 这次不能偷懒了… Nlog^2N可以过。
用splay维护区间哈希值然后外面再套个二分lcp长度。
据说卡取模的常数, 习惯自然溢出不存在的…

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int MAXN = 100010;
const int MAXM = 150020;
const ULL SEED = 31;
ULL powr[MAXN*2];
namespace Splay {
    struct Node {
        int ch[2], fa, sz;
        char val;
        ULL hashc;
    } d[MAXN*2];
    int root, dtot;
    inline void updata (int u) {
        d[u].sz = d[d[u].ch[0]].sz+1+d[d[u].ch[1]].sz;
        d[u].hashc = d[d[u].ch[0]].hashc*powr[d[d[u].ch[1]].sz+1]
        +powr[d[d[u].ch[1]].sz]*d[u].val+d[d[u].ch[1]].hashc;
    }
    inline int newNode (char ch) {
        ++ dtot;
        d[dtot].val = ch;
        updata(dtot);
        return dtot;
    }
    char * src;
    int build (int l, int r) {
        if(l > r) return 0;
        if(l == r) return newNode(src[l]);
        int mid = (l+r)>>1;
        int u = newNode(src[mid]);
        d[d[u].ch[0] = build(l, mid-1)].fa = u;
        d[d[u].ch[1] = build(mid+1, r)].fa = u;
        updata(u);
        return u;
    }
    inline void rotate (int x) {
        int y = d[x].fa;
        bool f = (d[y].ch[1] == x);
        d[y].ch[f] = d[x].ch[!f];
        d[d[y].ch[f]].fa = y;
        d[x].ch[!f] = y;
        d[x].fa = d[y].fa;
        d[y].fa = x;
        d[d[x].fa].ch[d[d[x].fa].ch[1] == y] = x;
        updata(y), updata(x);
    }
    void splay (int x, int g) {
        while(d[x].fa != g) {
            int y = d[x].fa;
            int z = d[y].fa;
            if(z != g) {
                if((d[z].ch[1] == y) == (d[y].ch[1] == x))
                    rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
        updata(x);
        if(g == 0) root = x;
    }
    inline int getByRank (int rk) {
        rk++;
        int u = root;
        while(u) {
            if(d[d[u].ch[0]].sz >= rk) u = d[u].ch[0];
            else if(d[d[u].ch[0]].sz+1 == rk) return u;
            else rk -= d[d[u].ch[0]].sz+1, u = d[u].ch[1];
        }
        return -1;
    }
    inline int getNext (int u, bool f) {
        splay(u, 0), u = d[u].ch[f];
        while(d[u].ch[!f]) u = d[u].ch[!f];
        return u;
    }
    inline int getIntervalN (int l, int r) {
        splay(l, 0), splay(r, l);
        return d[r].ch[0];
    }
    inline void insertAfter (int u, int ins) {
        int nxt = getNext(u, true);
        d[nxt].ch[0] = ins, d[ins].fa = nxt;
        splay(ins, 0);
    }
    inline void modify (int u, char ch) {
        d[u].val = ch; splay(u, 0);
    }
    inline ULL hashCode (int u) {return d[u].hashc;}
}
inline int getInt () {
    int ret = 0; char ch; bool flg = false;
    while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-');
    ret = ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+ch-'0';
    return ret;
}
int curlen;
int query (int a, int b) {
    int l = 0, r = curlen-max(a, b), ans = -1;
    while(l <= r) {
        int mid = (l+r)>>1;
        ULL cd1 = Splay::hashCode(
            Splay::getIntervalN(
            Splay::getByRank(a-1), Splay::getByRank(a+mid+1)));
        ULL cd2 = Splay::hashCode(
            Splay::getIntervalN(
            Splay::getByRank(b-1), Splay::getByRank(b+mid+1)));
        if(cd1 == cd2) l = mid+1, ans = mid;
        else r = mid-1;
    }
    return ans+1;
}
char buf[MAXN];
int main () {
    powr[0] = 1;
    for(int i = 1; i<MAXN; i++) powr[i] = powr[i-1]*SEED;
    scanf("%s", buf+1);
    int len = curlen = strlen(buf+1);
    Splay::src = buf;
    Splay::root = Splay::build(0, len+1);
    int M = getInt();
    while(M --) {
        scanf("%s", buf);
        if(buf[0] == 'Q') printf("%d\n", query(getInt(), getInt()));
        else if(buf[0] == 'I') {
            curlen ++;
            int pos = getInt();
            scanf("%s", buf);
            Splay::insertAfter(Splay::getByRank(pos), Splay::newNode(buf[0]));
        } else {
            int pos = getInt();
            scanf("%s", buf);
            Splay::modify(Splay::getByRank(pos), buf[0]);
        }
    }
}

BZOJ 1269

题目大意: 自己看。

解题报告

各种操作splay。
splay真好玩怎么乱搞都可以…

代码

 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int MAXN = 2*1024*1024+10;
namespace Splay {
    const int MAXD = MAXN;
    struct Node {
        int ch[2], fa;
        char val;
        int sz;
        bool rev;
    } d[MAXD];
    int dtot, root;
    inline void updata (int u) {d[u].sz = d[d[u].ch[0]].sz+1+d[d[u].ch[1]].sz;}
    inline int newNode (char ch) {
        dtot ++;
        d[dtot].val = ch;
        updata(dtot);
        return dtot;
    }
    char * src;
    int build (int l, int r) {
        if(l > r) return 0;
        if(l == r) return newNode(src[l]);
        int mid = (l+r)>>1;
        int u = newNode(src[mid]);
        d[d[u].ch[0] = build(l, mid-1)].fa = u;
        d[d[u].ch[1] = build(mid+1, r)].fa = u;
        updata(u);
        return u;
    }
    inline void filp (int u) {
        d[u].rev ^= 1;
        swap(d[u].ch[0], d[u].ch[1]);
    }
    inline void pushdown (int u) {
        if(d[u].rev) {
            filp(d[u].ch[0]);
            filp(d[u].ch[1]);
            d[u].rev = false;
        }
    }
    void downlazy (int u) {
        if(d[u].fa) downlazy(d[u].fa);
        pushdown(u);
    }
    inline void rotate (int x) {
        int y = d[x].fa;
        bool f = d[y].ch[1] == x;
        d[y].ch[f] = d[x].ch[!f];
        d[d[y].ch[f]].fa = y;
        d[x].ch[!f] = y;
        d[x].fa = d[y].fa;
        d[y].fa = x;
        d[d[x].fa].ch[d[d[x].fa].ch[1] == y] = x;
        updata(y), updata(x);
    }
    inline void splay (int x, int g) {
        downlazy(x);
        while(d[x].fa != g) {
            int y = d[x].fa;
            int z = d[y].fa;
            if(z != g) {
                if((d[z].ch[1] == y) == (d[y].ch[1] == x)) rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
        updata(x);
        if(g == 0) root = x;
    }
    inline int getByRank (int rk, int u = root) {
        rk ++;
        while(u) {
            pushdown(u);
            if(d[d[u].ch[0]].sz >= rk) u = d[u].ch[0];
            else if(d[d[u].ch[0]].sz+1 == rk) return u;
            else rk -= d[d[u].ch[0]].sz+1, u = d[u].ch[1];
        }
        return -1;
    }
    inline int advance (int u, int len) {
        splay(u, 0);
        if(len == 0) return u;
        return getByRank(len-1, d[u].ch[1]);
    }
    inline int getNext (int u, bool f) {
        splay(u, 0), u = d[u].ch[f];
        pushdown(u);
        while(d[u].ch[!f]) u = d[u].ch[!f], pushdown(u);
        return u;
    }
    inline int getIntervalN (int pre, int suc) {
        splay(pre, 0), splay(suc, pre);
        return d[suc].ch[0];
    }
    inline void eraseNode (int u) {
        d[d[u].fa].ch[d[d[u].fa].ch[1] == u] = 0;
        if(d[u].fa) splay(d[u].fa, 0);
    }
    inline void insertAfter (int u, int ins) {
        int nxt = getNext(u, true);
        d[nxt].ch[0] = ins, d[ins].fa = nxt;
        splay(ins, 0);
    }
    inline char value (int u) {return d[u].val;}
}
inline int getInt () {
    int ret = 0; char ch; bool flg = false;
    while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-');
    ret = ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+ch-'0';
    return flg ? -ret : ret;
}
char buf[MAXN];
int main () {
    int M = getInt();
    Splay::src = buf, Splay::root = Splay::build(0, 1);
    int cursor = Splay::getByRank(0);
    while(M --) {
        scanf("%s", buf);
        if(buf[0] == 'I') {
            int len = getInt();
            char * cur = buf;
            while(cur != buf+len) *cur = getchar(), ++ cur;
            Splay::insertAfter(cursor, Splay::build(0, len-1));
        } else if(buf[0] == 'M') {
            cursor = Splay::getByRank(getInt());
        } else if(buf[0] == 'D') {
            int endpos = Splay::advance(cursor, getInt()+1);
            Splay::eraseNode(Splay::getIntervalN(cursor, endpos));
        } else if(buf[0] == 'R') {
            int endpos = Splay::advance(cursor, getInt()+1);
            Splay::filp(Splay::getIntervalN(cursor, endpos));
        } else if(buf[0] == 'G') {
            printf("%c\n", Splay::value(Splay::getNext(cursor, true)));
        } else if(buf[0] == 'P') {
            cursor = Splay::getNext(cursor, false);
        } else if(buf[0] == 'N') {
            cursor = Splay::getNext(cursor, true);
        }
    }
}

BZOJ 1493

题目大意: 自己看去..

解题报告

维护环上的序列! 恶心题!
把环复制一份用序列维护, 用splay维护标记乱搞。
注意查询的时候要特殊判断几种情况! 包括整个环都是同一种颜色。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int MAXN = 500050;
namespace Splay {
    const int MAXD = MAXN*2;
    struct Node {
        int ch[2], fa;
        int sz, lc, rc, seg, val, lz;
        bool rev;
    } d[MAXD];
    int root, dtot;
    inline void updata (int u) {
        d[u].sz = d[d[u].ch[0]].sz + 1 + d[d[u].ch[1]].sz;
        d[u].seg = d[d[u].ch[0]].seg+d[d[u].ch[1]].seg+1
        -(d[d[u].ch[0]].rc == d[u].val)-(d[u].val == d[d[u].ch[1]].lc);
        if(d[u].ch[0]) d[u].lc = d[d[u].ch[0]].lc;
        else d[u].lc = d[u].val;
        if(d[u].ch[1]) d[u].rc = d[d[u].ch[1]].rc;
        else d[u].rc = d[u].val;
    }
    inline int newNode (int colr) {
        ++ dtot;
        d[dtot].val = colr;
        updata(dtot);
        return dtot;
    }
    inline void filp (int u) {
        d[u].rev ^= 1;
        swap(d[u].ch[0], d[u].ch[1]);
        swap(d[u].lc, d[u].rc);
    }
    inline void paint (int u, int colr) {
        if(!u) return ;
        d[u].lc = d[u].rc = d[u].val = d[u].lz = colr;
        d[u].seg = 1;
    }
    inline void pushdown (int u) {
        if(d[u].lz) {
            paint(d[u].ch[0], d[u].lz);
            paint(d[u].ch[1], d[u].lz);
            d[u].lz = 0;
        }
        if(d[u].rev) {
            filp(d[u].ch[0]);
            filp(d[u].ch[1]);
            d[u].rev = false;
        }
    }
    inline void downlazy (int u) {
        if(d[u].fa) downlazy(d[u].fa);
        pushdown(u);
    }
    int * src;
    inline int build (int l, int r) {
        if(l > r) return 0;
        if(l == r) return newNode(src[l]);
        int mid = (l+r)>>1;
        int u = newNode(src[mid]);
        d[d[u].ch[0] = build(l, mid-1)].fa = u;
        d[d[u].ch[1] = build(mid+1, r)].fa = u;
        updata(u);
        return u;
    }
    inline void rotate (int x) {
        int y = d[x].fa;
        bool f = d[y].ch[1] == x;
        d[y].ch[f] = d[x].ch[!f];
        d[d[y].ch[f]].fa = y;
        d[x].ch[!f] = y;
        d[x].fa = d[y].fa;
        d[y].fa = x;
        d[d[x].fa].ch[d[d[x].fa].ch[1] == y] = x;
        updata(y), updata(x);
    }
    inline void splay (int x, int g) {
        downlazy(x);
        while(d[x].fa != g) {
            int y = d[x].fa;
            int z = d[y].fa;
            if(z != g) {
                if((d[z].ch[1] == y) == (d[y].ch[1] == x)) rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
        updata(x);
        if(g == 0) root = x;
    }
    inline int getByRank (int rk, int u = root) {
        rk ++;
        while(u) {
            pushdown(u);
            if(d[d[u].ch[0]].sz >= rk) u = d[u].ch[0];
            else if(d[d[u].ch[0]].sz+1 == rk) return u;
            else rk -= d[d[u].ch[0]].sz+1, u = d[u].ch[1];
        }
        return -1;
    }
    inline int getNext (int u, bool f) {
        splay(u, 0), u = d[u].ch[f], pushdown(u);
        while(d[u].ch[!f]) u = d[u].ch[!f], pushdown(u);
        return u;
    }
    inline int getIntervalN (int a, int b) {
        splay(a, 0), splay(b, a);
        pushdown(d[b].ch[0]);
        return d[b].ch[0];
    }
    inline void insertAfter (int u, int ins) {
        d[d[ins].fa].ch[d[d[ins].fa].ch[1] == ins] = 0;
        if(d[ins].fa) splay(d[ins].fa, 0);
        int nxt = getNext(u, true);
        d[nxt].ch[0] = ins, d[ins].fa = nxt;
        splay(ins, 0);
    }
    inline void swapValue (int a, int b) {
        swap(d[a].val, d[b].val);
        splay(a, 0), splay(b, 0);
    }
    inline int segment (int u) {
        return d[u].seg;
    }
    inline int color (int u) {
        return d[u].val;
    }
    void output (int u) {
        if(!u) return ;
        pushdown(u);
        output(d[u].ch[0]);
        printf(" %d", d[u].val);
        output(d[u].ch[1]);
    }
}
inline int getInt () {
    int ret = 0; char ch; bool flg = false;
    while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-');
    ret = ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+ch-'0';
    return flg ? -ret : ret;
}
int src[MAXN*2];
char buf[15];
inline int interval (int a, int b)
{return Splay::getIntervalN(Splay::getByRank(a-1), Splay::getByRank(b+1));}
int main () {
    int N, C;
    scanf("%d%d", &N, &C);
    for(int i = 1; i<=N; i++) src[i] = src[i+N] = getInt();
    Splay::src = src, Splay::root = Splay::build(0, N*2+1);
    int M = getInt();
    while(M --) {
        scanf("%s", buf);
        if(buf[0] == 'C') {
            if(buf[1] == 'S') {
                int l = getInt(), r = getInt();
                if(r < l) r += N;
                printf("%d\n", Splay::segment(interval(l, r)));
            } else {
                int a = Splay::getByRank(0), b = Splay::getByRank(N+1);
                int ans = Splay::segment(Splay::getIntervalN(a, b));
                int lb = Splay::getNext(a, true), rb = Splay::getNext(b, false);
                if(lb != rb && Splay::color(lb) == Splay::color(rb)) ans --;
                printf("%d\n", max(ans, 1));
            }
        } else if(buf[0] == 'F') {
            Splay::filp(interval(2, N));
            Splay::filp(interval(N+2, N*2));
        } else if(buf[0] == 'S') {
            int a = getInt(), b = getInt();
            Splay::swapValue(Splay::getByRank(a), Splay::getByRank(b));
            Splay::swapValue(Splay::getByRank(a+N), Splay::getByRank(b+N));
        } else if(buf[0] == 'R') {
            int adv = getInt();
            if(adv == 0) continue ;
            Splay::insertAfter(Splay::getByRank(0),
            Splay::getIntervalN(Splay::getByRank(2*N-adv), Splay::getByRank(2*N+1)));
            //Splay::output(Splay::root);
            //puts("\n");
        } else if(buf[0] == 'P') {
            int l = getInt(), r = getInt(), c = getInt();
            if(l <= r) {
                Splay::paint(interval(l, r), c);
                Splay::paint(interval(l+N, r+N), c);
            } else {
                Splay::paint(interval(1, r), c);
                Splay::paint(interval(l, N+r), c);
                Splay::paint(interval(N+l, N*2), c);
            }
        }
    }
}

BZOJ 2329

题目大意: 给个括号序列, 支持区间取反, 区间翻转, 区间查询进行多少次单括号取反能让这个区间合法。

解题报告

好题啊! 刷了那么多代码题之后(看完题解)眼前一亮啊!
但是可惜题解太长, Hineven又要去赶作业…就不写了。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int MAXN = 100010;
namespace Splay {
    const int MAXD = MAXN;
    struct Node {
        int ch[2], fa;
        int val;
        int minp, maxp, mins, maxs, sum, sz;
        bool rev, flp;
        int covr;
    } d[MAXD];
    int dtot, root;
    void updata (int u) {
        d[u].minp = min(d[d[u].ch[0]].minp,
        d[d[u].ch[0]].sum+d[u].val+d[d[u].ch[1]].minp);
        d[u].maxp = max(d[d[u].ch[0]].maxp,
        d[d[u].ch[0]].sum+d[u].val+d[d[u].ch[1]].maxp);
        d[u].mins = min(d[d[u].ch[1]].mins,
        d[d[u].ch[1]].sum+d[u].val+d[d[u].ch[0]].mins);
        d[u].maxs = max(d[d[u].ch[1]].maxs,
        d[d[u].ch[1]].sum+d[u].val+d[d[u].ch[0]].maxs);
        d[u].sum = d[d[u].ch[0]].sum+d[u].val+d[d[u].ch[1]].sum;
        d[u].sz = d[d[u].ch[0]].sz+1+d[d[u].ch[1]].sz;
    }
    inline int newNode (int val) {
        d[++dtot].val = val;
        updata(dtot);
        return dtot;
    }
    inline void cover (int u, int c) {
        if(!u) return ;
        d[u].rev = d[u].flp = false;
        d[u].covr = d[u].val = c;
        d[u].sum = c*d[u].sz;
        d[u].val = c;
        d[u].minp = min(0, d[u].sum);
        d[u].maxp = max(0, d[u].sum);
        d[u].mins = min(0, d[u].sum);
        d[u].maxs = max(0, d[u].sum);
    }
    inline void filp (int u) {
        if(d[u].covr) return ;
        d[u].rev ^= 1;
        swap(d[u].ch[0], d[u].ch[1]);
        swap(d[u].minp, d[u].mins);
        swap(d[u].maxp, d[u].maxs);
    }
    inline void vfilp (int u) {
        if(d[u].covr) d[u].covr = -d[u].covr;
        else d[u].flp ^= 1;
        swap(d[u].minp, d[u].maxp);
        swap(d[u].mins, d[u].maxs);
        d[u].maxp = -d[u].maxp;
        d[u].maxs = -d[u].maxs;
        d[u].minp = -d[u].minp;
        d[u].mins = -d[u].mins;
        d[u].sum = -d[u].sum;
        d[u].val = -d[u].val;
    }
    inline void pushdown (int u) {
        if(d[u].covr) {
            cover(d[u].ch[0], d[u].covr);
            cover(d[u].ch[1], d[u].covr);
            d[u].covr = 0;
            d[u].rev = d[u].flp = false;
        }
        if(d[u].rev) {
            filp(d[u].ch[0]);
            filp(d[u].ch[1]);
            d[u].rev = false;
        }
        if(d[u].flp) {
            vfilp(d[u].ch[0]);
            vfilp(d[u].ch[1]);
            d[u].flp = false;
        }
    }
    void downlazy (int u) {
        if(d[u].fa) downlazy(d[u].fa);
        pushdown(u);
    }
    int * src;
    int build (int l, int r) {
        if(l > r) return 0;
        if(l == r) return newNode(src[l]);
        int mid = (l+r)>>1;
        int u = newNode(src[mid]);
        d[d[u].ch[0] = build(l, mid-1)].fa = u;
        d[d[u].ch[1] = build(mid+1, r)].fa = u;
        updata(u);
        return u;
    }
    inline void rotate (int x) {
        int y = d[x].fa;
        bool f = d[y].ch[1] == x;
        d[y].ch[f] = d[x].ch[!f];
        d[d[y].ch[f]].fa = y;
        d[x].ch[!f] = y;
        d[x].fa = d[y].fa;
        d[y].fa = x;
        d[d[x].fa].ch[d[d[x].fa].ch[1] == y] = x;
        updata(y), updata(x);
    }
    inline void splay (int x, int g) {
        downlazy(x);
        while(d[x].fa != g) {
            int y = d[x].fa, z = d[y].fa;
            if(z != g) {
                if((d[z].ch[1] == y) == (d[y].ch[1] == x)) rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
        updata(x);
        if(g == 0) root = x;
    }
    inline int getByRank (int rk) {
        rk ++;
        int u = root;
        while(u) {
            pushdown(u);
            if(d[d[u].ch[0]].sz >= rk) u = d[u].ch[0];
            else if(d[d[u].ch[0]].sz+1 == rk) return u;
            else rk -= d[d[u].ch[0]].sz+1, u = d[u].ch[1];
        }
        return -1;
    }
    inline int getIntervalN (int a, int b) {
        splay(a, 0), splay(b, a);
        return d[b].ch[0];
    }
    inline int value (int u) {
        return ((-d[u].minp+1)>>1) + ((d[u].maxs+1)>>1);
    }
}
inline int getInt () {
    int ret = 0; char ch; bool flg = false;
    while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-');
    ret = ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+ch-'0';
    return flg ? -ret : ret;
}
int src[MAXN];
char str[MAXN];
int main () {
    int N = getInt(), M = getInt();
    scanf("%s", str+1);
    for(int i = 1; i<=N; i++) src[i] = (str[i] == '(') ? 1 : -1;
    Splay::src = src;
    Splay::root = Splay::build(0, N+1);
    while(M --) {
        scanf("%s", str);
        int a = getInt(), b = getInt();
        int inv = Splay::getIntervalN(Splay::getByRank(a-1), Splay::getByRank(b+1));
        if(*str == 'R') {
            scanf("%s", str);
            if(*str == '(') Splay::cover(inv, 1);
            else Splay::cover(inv, -1);
        } else if(*str == 'I') Splay::vfilp(inv);
        else if(*str == 'S') Splay::filp(inv);
        else printf("%d\n", Splay::value(inv));
    }
}

BZOJ 1500

题目大意: 自己看..

解题报告

按照题目要求把所有操作都写一遍即可…
一坨细节..注意处理0好节点和maxans等标记的updata写法..

代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <climits>
using namespace std;
typedef long long LL;
const int MAXN = 500050;
const int EMPTY = -87197623;
namespace Splay {
    const int MAXD = MAXN;
    struct Node {
        int ch[2], fa;
        int val, sz, lz;
        LL mxp, mxs, sum, mxsum;
        bool rev;
    } d[MAXD];
    inline void initialize () {
        d[0].mxp = d[0].mxs = d[0].mxsum = -(0x3f3f3f3f3f3f3f3fLL);
    }
    int dtot, root;
    inline void updata (int u) {
        d[u].sz = d[d[u].ch[0]].sz+1+d[d[u].ch[1]].sz;
        d[u].sum = d[d[u].ch[0]].sum+d[u].val+d[d[u].ch[1]].sum;
        if(d[u].ch[0])
            d[u].mxp = max(
            max(d[d[u].ch[0]].mxp, d[d[u].ch[0]].sum+d[u].val),
            d[d[u].ch[0]].sum+d[u].val+d[d[u].ch[1]].mxp);
        else d[u].mxp = max((LL)d[u].val, d[u].val+d[d[u].ch[1]].mxp);
        if(d[u].ch[1])
            d[u].mxs = max(
            max(d[d[u].ch[1]].mxs, d[d[u].ch[1]].sum+d[u].val),
            d[d[u].ch[1]].sum+d[u].val+d[d[u].ch[0]].mxs);
        else d[u].mxs = max((LL)d[u].val, d[u].val+d[d[u].ch[0]].mxs);
        d[u].mxsum = max((LL)d[u].val, max(
            max(d[d[u].ch[0]].mxsum, d[d[u].ch[1]].mxsum),
            max(d[d[u].ch[0]].mxs+d[u].val+d[d[u].ch[1]].mxp,
            max(d[d[u].ch[0]].mxs+d[u].val, d[d[u].ch[1]].mxp+d[u].val))));
    }
    int stk[MAXD], stktop;
    inline int newNode (int val) {
        int u;
        if(stktop) u = stk[stktop--];
        else u = ++dtot;
        memset(d+u, 0, sizeof d[0]);
        d[u].val = val;
        d[u].lz = EMPTY;
        updata(u);
        return u;
    }
    int * src;
    int build (int l, int r) {
        if(l > r) return 0;
        if(l == r) return newNode(src[l]);
        int mid = (l+r)>>1;
        int u = newNode(src[mid]);
        d[d[u].ch[0] = build(l, mid-1)].fa = u;
        d[d[u].ch[1] = build(mid+1, r)].fa = u;
        updata(u);
        return u;
    }
    inline void paint (int u, int c) {
        if(!u) return ;
        d[u].lz = c;
        d[u].sum = (LL)d[u].sz*c;
        d[u].mxsum = d[u].mxs = d[u].mxp = max(d[u].sum, (LL)c);
        d[u].val = c;
    }
    inline void filp (int u) {
        d[u].rev ^= 1;
        swap(d[u].mxp, d[u].mxs);
        swap(d[u].ch[0], d[u].ch[1]);
    }
    inline void pushdown (int u) {
        if(d[u].lz != EMPTY) {
            paint(d[u].ch[0], d[u].lz);
            paint(d[u].ch[1], d[u].lz);
            d[u].lz = EMPTY;
        }
        if(d[u].rev) {
            filp(d[u].ch[0]);
            filp(d[u].ch[1]);
            d[u].rev = false;
        }
    }
    void downlazy (int u) {
        if(d[u].fa) downlazy(d[u].fa);
        pushdown(u);
    }
    inline void rotate (int x) {
        int y = d[x].fa;
        bool f = d[y].ch[1] == x;
        d[y].ch[f] = d[x].ch[!f];
        d[d[y].ch[f]].fa = y;
        d[x].ch[!f] = y;
        d[x].fa = d[y].fa;
        d[y].fa = x;
        d[d[x].fa].ch[d[d[x].fa].ch[1] == y] = x;
        updata(y), updata(x);
    }
    inline void splay (int x, int g) {
        downlazy(x);
        while(d[x].fa != g) {
            int y = d[x].fa, z = d[y].fa;
            if(z != g) {
                if((d[z].ch[1] == y) == (d[y].ch[1] == x)) rotate(y);
                else rotate(x);
            }
            rotate(x);
        }
        updata(x);
        if(g == 0) root = x;
    }
    inline int getByRank (int rk, int u = root) {
        rk ++;
        while(u) {
            pushdown(u);
            if(d[d[u].ch[0]].sz >= rk) u = d[u].ch[0];
            else if(d[d[u].ch[0]].sz+1 == rk) return u;
            else rk -= d[d[u].ch[0]].sz+1, u = d[u].ch[1];
        }
        return u;
    }
    inline int getNext (int u, bool f) {
        splay(u, 0), pushdown(u = d[u].ch[f]);
        while(d[u].ch[!f]) u = d[u].ch[!f], pushdown(u);
        return u;
    }
    inline int getIntervalN (int a, int b) {
        splay(a, 0), splay(b, a);
        return d[b].ch[0];
    }
    inline int getInterval (int a, int b) {
        int pre = getNext(a, false), suc = getNext(b, true);
        return getIntervalN(pre, suc);
    }
    inline void insertAfter (int u, int ins) {
        int nxt = getNext(u, true);
        d[nxt].ch[0] = ins; d[ins].fa = nxt;
        splay(ins, 0);
    }
    void releaseMemory (int u) {
        if(!u) return ;
        releaseMemory(d[u].ch[0]);
        releaseMemory(d[u].ch[1]);
        stk[++stktop] = u;
    }
    inline void erase (int u) {
        d[d[u].fa].ch[d[d[u].fa].ch[1] == u] = 0;
        splay(d[u].fa, 0), releaseMemory(u);
    }
    inline LL sum (int u) {
        return d[u].sum;
    }
    inline LL maxsum () {
        int x = getIntervalN(getByRank(0), getByRank(d[root].sz-1));
        return d[x].mxsum;
    }
}
inline int getInt () {
    int ret; char ch; bool flg = false;
    while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '-');
    ret = ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+ch-'0';
    return flg ? -ret : ret;
}
char buf[20];
int src[MAXN];
int main () {
    int N = getInt(), M = getInt();
    Splay::initialize(), Splay::src = src;
    for(int i = 1; i<=N; i++) src[i] = getInt();
    Splay::root = Splay::build(0, N+1);
    while(M --) {
        scanf("%s", buf);
        if(buf[0] == 'I') {
            int pos = Splay::getByRank(getInt());
            int tot = getInt();
            for(int i = 1; i<=tot; i++) src[i] = getInt();
            Splay::insertAfter(pos, Splay::build(1, tot));
        } else if(buf[0] == 'D') {
            int pos = getInt();
            int inv = Splay::getIntervalN(Splay::getByRank(pos-1), Splay::getByRank(pos+getInt()));
            Splay::erase(inv);
        } else if(buf[0] == 'M' && buf[2] == 'K') {
            int pos = getInt();
            int inv = Splay::getIntervalN(Splay::getByRank(pos-1), Splay::getByRank(pos+getInt()));
            Splay::paint(inv, getInt());
        } else if(buf[0] == 'R') {
            int pos = getInt();
            int inv = Splay::getIntervalN(Splay::getByRank(pos-1), Splay::getByRank(pos+getInt()));
            Splay::filp(inv);
        } else if(buf[0] == 'G') {
            int pos = getInt();
            int inv = Splay::getIntervalN(Splay::getByRank(pos-1), Splay::getByRank(pos+getInt()));
            printf("%lld\n", Splay::sum(inv));
        } else if(buf[0] == 'M') printf("%lld\n", Splay::maxsum());
    }
}

Join the discussion

Your email address will not be published. Required fields are marked *