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