## 【BZOJ 4906】[BeiJing2017] 喷式水战改

### Code

ubuntu 16.04下也没有问题
UOJ的自定义测试也不会RE

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int SGZ = 4;
const int N = 400000;

namespace Splay{
int tot;
struct Node *null, *root;
struct Node{
Node *ch[2], *fa;
LL len, plen, adv[SGZ], sum[SGZ][SGZ];
inline Node() {
}
inline Node(LL l, LL a, LL b, LL c) {
memset(sum, 0, sizeof(sum));
sum[0][0] = adv[0] = sum[3][3] = adv[3] = l * a;
sum[1][1] = adv[1] = l * b;
sum[2][2] = adv[2] = l * c;
len = plen = l;
ch[0] = ch[1] = fa = null;
for (int i = 0; i < SGZ; i++) {
for (int j = i; j < SGZ; j++) {
for (int k = i - 1; ~k; k--) {
sum[k][j] = max(sum[k][j], sum[i][j]);
}
for (int k = j + 1; k < SGZ; k++) {
sum[i][k] = max(sum[i][k], sum[i][j]);
}
}
}
}
inline void relax(LL &a, LL b) {
a = b > a? b: a;
}
inline void maintain() {
memset(sum, 0, sizeof(sum));
//merge left son
if (ch[0] != null) {
for (int i = 0; i < SGZ; i++) {
for (int k = SGZ - 1; k >= i; k--) {
for (int j = k; j >= i; j--) {
relax(sum[i][k], ch[0]->sum[i][j] + adv[k]);
}
}
}
plen = len + ch[0]->plen;
} else {
for (int i = 0; i < SGZ; i++) {
}
plen = len;
}
//merge right son
if (ch[1] != null) {
for (int l = 0; l < SGZ; l++) {
for (int i = SGZ - 1; i >= l; i--) {
for (int r = SGZ - 1; r >= i; r--) {
relax(sum[l][r], sum[l][i] + ch[1]->sum[i][r]);
}
}
}
plen += ch[1]->plen;
}
for (int i = 0; i < SGZ; i++) {
for (int j = i; j < SGZ; j++) {
for (int k = i - 1; ~k; k--) {
relax(sum[k][j], sum[i][j]);
}
for (int k = j + 1; k < SGZ; k++) {
relax(sum[i][k], sum[i][j]);
}
}
}
}
inline void rotate() {
int t = fa->ch[1] == this;
if (fa->fa != null) {
int tt = fa->fa->ch[1] == fa;
fa->fa->ch[tt] = this;
}
fa->ch[t] = ch[t^1]; ch[t^1]->fa = fa;
ch[t^1] = fa; fa = ch[t^1]->fa;
ch[t^1]->fa = this;
ch[t^1]->maintain();
maintain();
}
inline void splay(Node *ed) {
while (fa != ed) {
if (fa->fa != ed) {
if ((fa->ch[0] == this) ^ (fa->fa->ch[0] == fa)) {
rotate();
rotate();
} else {
fa->rotate();
rotate();
}
} else {
rotate();
}
}
}
inline LL ans() {
LL ret = 0;
for (int i = 0; i < SGZ; i++) {
for (int j = i; j < SGZ; j++) {
ret = max(ret, sum[i][j]);
}
}
return ret;
}
Node *find(LL pp) {
if (ch[0]->plen >= pp) {
return ch[0]->find(pp);
} else if (ch[0]->plen + len >= pp) {
return this;
} else {
return ch[1]->find(pp - ch[0]->plen - len);
}
}
Node *min() {
if (ch[0] != null) {
return ch[0]->min();
} else {
return this;
}
}
}p[N];
inline void insert(LL pp, int a ,int b, int c, LL l) {
p[++tot] = Node(l, a, b, c);
Node *nw = p + tot;
if (root != null) {
Node *pos = root->find(pp);
pos->splay(null); root = pos;
int nlen = root->ch[0]->plen + root->len - pp, LEN = root->len, ls = root->ch[0] - p, rs = root->ch[1] - p;
p[++tot] = Node(nlen, LEN? root->adv[0] / LEN: 0, LEN? root->adv[1] / LEN: 0, LEN? root->adv[2] / LEN: 0);
*root = Node(LEN - nlen, LEN? root->adv[0] / LEN: 0, LEN? root->adv[1] / LEN: 0, LEN? root->adv[2] / LEN: 0);
root->ch[0] = p + ls, root->ch[1] = p + rs;
if (root->ch[1] != null) {
root->ch[1]->min()->splay(root);
p[tot].fa = root->ch[1];
root->ch[1]->ch[0] = p + tot;
nw->fa = p + tot;
p[tot].ch[0] = nw;
p[tot].maintain();
root->ch[1]->maintain();
root->maintain();
} else {
p[tot].fa = root;
root->ch[1] = p + tot;
nw->fa = p + tot;
p[tot].ch[0] = nw;
p[tot].maintain();
root->maintain();
}
} else {
root = nw;
}
}
inline LL query() {
return root->ans();
}
inline void init() {
null = root = p;
}
};

int main() {
Splay::init();
int n; scanf("%d", &n);
for (LL i = 1, LastAns = 0; i <= n; ++i) {
LL pos, len, tmp, a, b, c;
cin>>pos>>a>>b>>c>>len;
Splay::insert(pos, a, b, c, len);
tmp = Splay::query();
printf("%lld\n", tmp - LastAns);
LastAns = tmp;
}
return 0;
}

## 【BZOJ 4573】[ZJOI2016] 大森林

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300009;

int n,m,num[N],l[N],r[N],last[N],to[N],ans[N],id[N];
vector<int> ins[N],del[N],q[N];

inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

struct Node{int val,sum,fa,ch[2];}p[N];
int cnt;
public:
inline int NewNode(int v) {
p[cnt+1].sum = p[cnt+1].val = v;
return ++cnt;
}
inline void modify(int w, int t) {
cut(num[w]);
if (t == 1) link(num[w], id[to[w]]);
}
inline int query(int x) {
int u = id[l[N-x]], v = id[r[N-x]], ret;
access(u); splay(u); ret = p[u].sum;
x = access(v); splay(v); ret += p[v].sum;
access(x); splay(x); ret -= p[x].sum << 1;
return abs(ret);
}
inline void link(int a, int b) {
splay(a); p[a].fa = b;
}
inline void cut(int x) {
access(x); splay(x);
p[x].ch[0] = p[p[x].ch[0]].fa = 0;
maintain(x);
}
private:
inline void maintain(int w) {
p[w].sum = p[w].val + p[p[w].ch[0]].sum + p[p[w].ch[1]].sum;
}
inline bool IsRoot(int w) {
return !p[w].fa || (p[p[w].fa].ch[0] != w && p[p[w].fa].ch[1] != w);
}
inline void rotate(int x) {
int y=p[x].fa,z=p[y].fa,t=p[y].ch[1]==x;
if (!IsRoot(y)) p[z].ch[p[z].ch[1]==y] = x;
p[y].ch[t] = p[x].ch[t^1]; p[p[x].ch[t^1]].fa = y;
p[x].ch[t^1] = y; p[x].fa = z; p[y].fa = x;
maintain(y); maintain(x);
}
inline void splay(int x) {
for (int f,ff;!IsRoot(x);) {
f = p[x].fa; ff = p[f].fa;
if (IsRoot(f)) rotate(x);
else {
if ((p[ff].ch[0]==f)^(p[f].ch[0]==x)) rotate(x),rotate(x);
else rotate(f),rotate(x);
}
}
}
inline int access(int x) {
for (int last=0;;last=x,x=p[x].fa)
if (x) splay(x), p[x].ch[1] = last, maintain(x);
else return last;
}
}lct;

int main() {
int pre = lct.NewNode(0); id[1] = lct.NewNode(1);
lct.link(pre, id[1]); l[1] = 1; r[1] = n;
for (int i=1,opt,ll,rr,x,tot=1;i<=m;i++) {
id[++tot] = lct.NewNode(1);
} else if (opt == 1) {
ll = read(); rr = read(); to[i] = x = read();
ll = max(ll, l[x]); rr = min(rr, r[x]);
if (ll <= rr) {
ins[ll].push_back(i), del[rr].push_back(i);
num[i] = lct.NewNode(0); lct.link(num[i], pre);
last[i] = pre; pre = num[i];
}
} else {
q[x].push_back(i);
}
}
memset(ans,-1,sizeof(ans));
for (int i=1;i<=n;i++) {
for (int j=ins[i].size()-1;~j;j--) lct.modify(ins[i][j], 1);
for (int j=q[i].size()-1;~j;j--) ans[q[i][j]] = lct.query(q[i][j]);
for (int j=del[i].size()-1;~j;j--) lct.modify(del[i][j], -1);
}
for (int i=1;i<=m;i++) (~ans[i])? printf("%d\n",ans[i]),1: 0;
return 0;
}

## 【BZOJ 1895】[PKU3580] SuperMemo

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int INF = 0x7fffffff;
const int N = 200009;

inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

class Splay{
struct Node{int ch[2],val,mn,sz,fa,delta,rev;}p[N]; int cnt;
public:
inline Splay() {
cnt = 2; p[1].ch[1] = 2;
p[1].val = p[1].mn = INF;
p[2].val = p[2].mn = INF;
p[1].sz = 2; p[2].sz = 1;
p[1].fa = p[2].fa = 1;
}
inline void insert(int pos, int v) { ++pos;
int w; splay(w=rank(1, pos), 1);
int nw; splay(nw=rank(1, pos+1), w);
p[nw].ch[0] = ++cnt; p[cnt].fa = nw;
p[cnt].mn = p[cnt].val = v; p[cnt].sz = 1;
maintain(nw); maintain(w); maintain(1);
}
inline void add(int l, int r, int v) { ++l; ++r;
int w; splay(w=rank(1, l-1), 1);
int nw; splay(nw=rank(1, r+1), w);
p[p[nw].ch[0]].delta += v;
PushDown(p[nw].ch[0]); maintain(nw);
maintain(w); maintain(1);
}
inline int query(int l, int r) { ++l; ++r;
int w; splay(w=rank(1, l-1), 1);
int nw; splay(nw=rank(1, r+1), w);
return PushDown(p[nw].ch[0]), p[p[nw].ch[0]].mn;
}
inline void remove(int r) { ++r;
int w; splay(w=rank(1, r-1), 1);
int nw; splay(nw=rank(1, r+1), w);
p[nw].ch[0] = 0; maintain(nw);
maintain(w); maintain(1);
}
inline void reverse(int l, int r) { ++l; ++r;
int w; splay(w=rank(1, l-1), 1);
int nw; splay(nw=rank(1, r+1), w);
p[p[nw].ch[0]].rev ^= 1;
}
inline void Rotate(int l, int r, int t) {
if (l==r||!(t%=((++r) - (++l) + 1))) return;
int w; splay(w=rank(1, l-1), 1);
int nw; splay(nw=rank(1, r+1), w);
int nnw; splay(nnw=rank(p[nw].ch[0], r-l-t+1), nw);
int nnnw; splay(nnnw=rank(p[nnw].ch[1], t), nnw);
p[nw].ch[0] = nnnw; p[nnnw].ch[1] = nnw; p[nnw].ch[1] = 0;
p[nnw].fa = nnnw; p[nnnw].fa = nw;
maintain(nnw); maintain(nnnw);
}
inline void build(int r) {
build(p[2].ch[0], 2, 1, r);
}
private:
inline void PushDown(int w) {
if (p[w].delta) {
p[w].mn += p[w].delta; p[w].val += p[w].delta;
p[p[w].ch[1]].delta += p[w].delta;
p[p[w].ch[0]].delta += p[w].delta;
p[w].delta = 0;
}
if (p[w].rev) {
swap(p[w].ch[0], p[w].ch[1]); p[w].rev = 0;
p[p[w].ch[0]].rev ^= 1; p[p[w].ch[1]].rev ^= 1;
}
}
inline void maintain(int w) {
p[w].mn = p[w].val; p[w].sz = p[p[w].ch[0]].sz + p[p[w].ch[1]].sz + 1;
if (p[w].ch[0]) PushDown(p[w].ch[0]), p[w].mn = min(p[w].mn, p[p[w].ch[0]].mn);
if (p[w].ch[1]) PushDown(p[w].ch[1]), p[w].mn = min(p[w].mn, p[p[w].ch[1]].mn);
}
inline void rotate(int w) {
int f=p[w].fa,t=p[f].ch[1]==w,ff=p[f].fa;
p[f].ch[t] = p[w].ch[t^1]; p[p[w].ch[t^1]].fa = f;
p[w].ch[t^1] = f; p[w].fa = p[f].fa; p[f].fa = w;
if (ff != f) p[ff].ch[p[ff].ch[1]==f] = w;
maintain(f); maintain(w);
}
inline void splay(int w, int pur) {
if (w == pur) return;
for (int f,ff;f=p[w].fa,p[w].fa!=pur;) {
((ff=p[f].fa) == pur)? rotate(w):
(((p[f].ch[1]==w)^(p[ff].ch[1]==f))?rotate(w),rotate(f):rotate(f),rotate(w));
}
}
int rank(int w, int t) {
PushDown(w); if (t<=0) return w; int szt = p[p[w].ch[0]].sz;
if (szt >= t) return rank(p[w].ch[0], t);
else if (szt + 1 == t) return w;
else return rank(p[w].ch[1], t-1-szt);
}
void build(int &w, int f, int l, int r) {
int mid = l + r >> 1; p[w=++cnt].fa = f; p[w].sz = 1; p[w].mn = INF;
if (l < mid) build(p[w].ch[0], w, l, mid-1), p[w].sz += p[p[w].ch[0]].sz, p[w].mn = min(p[w].mn, p[p[w].ch[0]].mn);
p[w].mn = min(p[w].mn, p[w].val = read());
if (mid < r) build(p[w].ch[1], w, mid+1, r), p[w].sz += p[p[w].ch[1]].sz, p[w].mn = min(p[w].mn, p[p[w].ch[1]].mn);
}
}SP;

int main() {
int n = read(); char opt[10]; SP.build(n);
for (int m=read(),l,r,x;m;--m) {
scanf("%s",opt+1);
if (opt[1] == 'A') {
} else if (opt[1] == 'R' && opt[4] == 'E') {
SP.reverse(l, r);
} else if (opt[1] == 'R') {
} else if (opt[1] == 'I') {
SP.insert(l, r);
} else if (opt[1] == 'D') {
} else {
printf("%d\n",SP.query(l,r));
}
}
return 0;
}

## 【模板库】Splay

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int INF = 0x7fffffff;
const int N = 200009;

inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

class Splay{
struct Node{int ch[2],val,mn,sz,fa,delta,rev;}p[N]; int cnt;
public:
inline Splay() { //init the splay and place begining(1) and ending(2) of the sequence
cnt = 2; p[1].ch[1] = 2;
p[1].val = p[1].mn = INF;
p[2].val = p[2].mn = INF;
p[1].sz = 2; p[2].sz = 1;
p[1].fa = p[2].fa = 1;
}
inline void insert(int pos, int v) { ++pos; //insert a new node with value v as ths (pos + 1) node
int w; splay(w=rank(1, pos), 1);
int nw; splay(nw=rank(1, pos+1), w);
p[nw].ch[0] = ++cnt; p[cnt].fa = nw;
p[cnt].mn = p[cnt].val = v; p[cnt].sz = 1;
maintain(nw); maintain(w); maintain(1);
}
inline void add(int l, int r, int v) { ++l; ++r; //add value v to elements of range[l,r]
int w; splay(w=rank(1, l-1), 1);
int nw; splay(nw=rank(1, r+1), w);
p[p[nw].ch[0]].delta += v;
PushDown(p[nw].ch[0]); maintain(nw);
maintain(w); maintain(1);
}
inline int query(int l, int r) { ++l; ++r; //query the min element in range[l,r]
int w; splay(w=rank(1, l-1), 1);
int nw; splay(nw=rank(1, r+1), w);
return PushDown(p[nw].ch[0]), p[p[nw].ch[0]].mn;
}
inline void remove(int r) { ++r; //remove the r node
int w; splay(w=rank(1, r-1), 1);
int nw; splay(nw=rank(1, r+1), w);
p[nw].ch[0] = 0; maintain(nw);
maintain(w); maintain(1);
}
inline void reverse(int l, int r) { ++l; ++r; //reverse the elements in range[l,r]
int w; splay(w=rank(1, l-1), 1);
int nw; splay(nw=rank(1, r+1), w);
p[p[nw].ch[0]].rev ^= 1;
}
inline void Rotate(int l, int r, int t) { //rotate the elements in range[l,r] t steps
if (l==r||!(t%=((++r) - (++l) + 1))) return;
int w; splay(w=rank(1, l-1), 1);
int nw; splay(nw=rank(1, r+1), w);
int nnw; splay(nnw=rank(p[nw].ch[0], r-l-t+1), nw);
int nnnw; splay(nnnw=rank(p[nnw].ch[1], t), nnw);
p[nw].ch[0] = nnnw; p[nnnw].ch[1] = nnw; p[nnw].ch[1] = 0;
p[nnw].fa = nnnw; p[nnnw].fa = nw;
maintain(nnw); maintain(nnnw);
}
private:
inline void PushDown(int w) {
if (p[w].delta) {
p[w].mn += p[w].delta; p[w].val += p[w].delta;
p[p[w].ch[1]].delta += p[w].delta;
p[p[w].ch[0]].delta += p[w].delta;
p[w].delta = 0;
}
if (p[w].rev) {
swap(p[w].ch[0], p[w].ch[1]); p[w].rev = 0;
p[p[w].ch[0]].rev ^= 1; p[p[w].ch[1]].rev ^= 1;
}
}
inline void maintain(int w) {
p[w].mn = p[w].val; p[w].sz = p[p[w].ch[0]].sz + p[p[w].ch[1]].sz + 1;
if (p[w].ch[0]) PushDown(p[w].ch[0]), p[w].mn = min(p[w].mn, p[p[w].ch[0]].mn);
if (p[w].ch[1]) PushDown(p[w].ch[1]), p[w].mn = min(p[w].mn, p[p[w].ch[1]].mn);
}
inline void rotate(int w) { //rotate w to its father
int f=p[w].fa,t=p[f].ch[1]==w,ff=p[f].fa;
p[f].ch[t] = p[w].ch[t^1]; p[p[w].ch[t^1]].fa = f;
p[w].ch[t^1] = f; p[w].fa = p[f].fa; p[f].fa = w;
if (ff != f) p[ff].ch[p[ff].ch[1]==f] = w;
maintain(f); maintain(w);
}
inline void splay(int w, int pur) { //splay w to pur's son
if (w == pur) return;
for (int f,ff;f=p[w].fa,p[w].fa!=pur;) {
((ff=p[f].fa) == pur)? rotate(w):
(((p[f].ch[1]==w)^(p[ff].ch[1]==f))?rotate(w),rotate(f):rotate(f),rotate(w));
}
}
int rank(int w, int t) { //function rank is needed to be called before each splay operation to push down tags
PushDown(w); if (t<=0) return w; int szt = p[p[w].ch[0]].sz;
if (szt >= t) return rank(p[w].ch[0], t);
else if (szt + 1 == t) return w;
else return rank(p[w].ch[1], t-1-szt);
}
}SP;

int main() {
int n = read(); char opt[10];
for (int i=1;i<=n;i++) SP.insert(i-1, read());
for (int m=read(),l,r,x;m;--m) {
scanf("%s",opt+1);
if (opt[1] == 'A') {
} else if (opt[1] == 'R' && opt[4] == 'E') {
SP.reverse(l, r);
} else if (opt[1] == 'R') {
} else if (opt[1] == 'I') {
SP.insert(l, r);
} else if (opt[1] == 'D') {
} else {
printf("%d\n",SP.query(l,r));
}
}
return 0;
}

## 【日常小测】市场

### 题目大意

1. 区间加$c(-10^4 \le c \le 10^4)$
2. 区间除$d$。即对于单个元素$a_i$，除以$d$后变为$\lfloor \frac{a_i}{d} \rfloor$
3. 询问区间和
4. 询问区间最值