开始进入平衡树时代!
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