【BZOJ 1251】序列终结者

2019-11-14 09:05:49

字体：大中小

来源：转载

供稿：网友

Splay的序列操作注意：更新的时候，要先确定子树不为空在进行更新。空指针的mx值要设为-inf

#include <cstdio>#include <iostream>#include <algorithm>using namespace std;const int maxn = 50010;struct node{ int num, val, size, turn, mx, add; node *PRe, *ch[2]; void update(){ size = ch[0]->size + ch[1]->size + 1; mx = max(max(ch[0]->mx, ch[1]->mx), val); } int wh(){return pre->ch[0] == this ? 0 : 1;} void set_ch(int wh, node *child);}pool[maxn], *root, *null;void node::set_ch(int wh, node *child){ ch[wh] = child; if(child != null) child->pre = this; update();}int cnt, n, m;node *get(int num, int val){ node *now = &pool[++cnt]; now->mx = now->val = val, now->num = num, now->size = 1; now->pre = now->ch[0] = now->ch[1] = null; now->turn = now->add = 0; return now;}void down(node *now){ if(now->add != 0){ if(now->ch[0] != null) { now->ch[0]->add += now->add; now->ch[0]->mx += now->add; now->ch[0]->val += now->add; } if(now->ch[1] != null){ now->ch[1]->add += now->add; now->ch[1]->mx += now->add; now->ch[1]->val += now->add; } now->add = 0; } if(now->turn != 0){ now->turn = 0; swap(now->ch[0]->ch[0], now->ch[0]->ch[1]); swap(now->ch[1]->ch[0], now->ch[1]->ch[1]); now->ch[0]->turn ^= 1; now->ch[1]->turn ^= 1; }}node *find(int num){ node *now = root; int rank = num; while(now != null){ down(now); if(now->ch[0]->size+1 == rank) return now; else if(now->ch[0]->size+1 < rank){ rank -= now->ch[0]->size+1; now = now->ch[1]; }else now = now->ch[0]; } return null;}void rotate(node *now){ node *fa = now->pre, *gra = now->pre->pre; int wh = now->wh(); fa->set_ch(wh, now->ch[wh^1]); now->set_ch(wh^1, fa); now->pre = gra; if(gra != null) gra->ch[gra->ch[0] == fa ? 0 : 1] = now;}void splay(node *now, node *tar){ for( ; now->pre != tar; rotate(now)) if(now->pre->pre != tar) now->wh() == now->pre->wh() ? rotate(now->pre) : rotate(now); if(tar == null) root = now;}void insert(int num, int val){ node *now = root, *last = null; while(now != null){ last = now; if(now->num > num) now = now->ch[0]; else now = now->ch[1]; } now = get(num, val); if(last == null) root = now; else{ if(num < last->num) last->set_ch(0, now); else last->set_ch(1, now); splay(now, null); }}int main(){ null = pool; null->add = null->num = 0, null->mx = -2e9; null->turn = null->size = null->val = 0; null->ch[0] = null->ch[1] = null->pre = null; root = null; scanf("%d%d", &n, &m); insert(0, 0), insert(n+1, 0); for(int i = 1; i <= n; i ++) insert(i, 0); for(int i = 1; i <= m; i ++){ int a, b, c, d; scanf("%d%d%d", &a, &b, &c); if(a == 1){ scanf("%d", &d); node *l = find(b), *r = find(c+2); splay(r, null), splay(l, r); l->ch[1]->add += d; l->ch[1]->val += d; l->ch[1]->mx += d; }else if(a == 2){ node *l = find(b), *r = find(c+2); splay(r, null), splay(l, r); l->ch[1]->turn ^= 1; swap(l->ch[1]->ch[0], l->ch[1]->ch[1]); }else{ node *l = find(b), *r = find(c+2); splay(r, null), splay(l, r); printf("%d/n", l->ch[1]->mx); } } return 0;}

上一篇：Unity跑酷扭曲shader

下一篇：蓝桥杯练习-01字串