[BZOJ 1251]シーケンスターミネーター
http://www.lydsy.com/JudgeOnline/problem.php?id=1251
裸splayは、小さなモデルとして…
ACコード:
裸splayは、小さなモデルとして…
ACコード:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf = 0x3f3f3f3f ;
const int N = 50020 ;
inline void read(int &x)
{
char c; bool f = 0;
while ((c = getchar()) < '0' || c > '9') if (c == '-') f = 1;
for (x = c - '0'; (c = getchar()) >= '0' && c <= '9'; x = x * 10 + c - '0');
if (f) x = -x;
}
struct node
{
node *ch[2], *fa;
int val, mx, size;
int add, rev;
inline void Add(int v);
inline void Rev();
inline void push_down();
inline void push_up();
}poolNode[N], *nil, *cur, *root;
inline void node::Add(int v)
{
if (this != nil)
val += v, mx += v, add += v;
}
inline void node::Rev()
{
if (this != nil) swap(ch[0], ch[1]), rev ^= 1;
}
inline void node::push_down()
{
if (add) ch[0]->Add(add), ch[1]->Add(add), add = 0;
if (rev) ch[0]->Rev(), ch[1]->Rev(), rev = 0;
}
inline void node::push_up()
{
size = ch[0]->size + ch[1]->size + 1;
mx = max(max(ch[0]->mx, ch[1]->mx), val);
}
inline node* newnode(node *pre)
{
cur++;
cur->ch[0] = cur->ch[1] = nil;
cur->fa = pre;
return cur;
}
inline void rotate(node *o)
{
node *u = o->fa;
int d = u->ch[0] == o;
u->ch[d ^ 1] = o->ch[d], o->ch[d]->fa = u;
o->fa = u->fa, o->fa->ch[o->fa->ch[1] == u] = o;
o->ch[d] = u, u->fa = o;
u->push_up();
}
void splay(node *x, node *goal)
{
while (x->fa != goal)
{
node *y = x->fa, *z = y->fa;
if (z != goal)
{
if ((z->ch[0] == y) ^ (y->ch[0] == x))
rotate(x);
else rotate(y);
}
rotate(x);
}
x->push_up();
if (goal == nil) root = x;
}
node* getK(node *o, int k)
{
while (1)
{
o->push_down();
int tmp = o->ch[0]->size;
if (tmp < k)
{
k -= tmp + 1;
if (!k) return o;
o = o->ch[1];
}
else o = o->ch[0];
}
}
inline void split(int l, int r)
{
splay(getK(root, l), nil);
splay(getK(root->ch[1], (r - l + 2)), root);
}
#define need (root->ch[1]->ch[0])
inline void modify(int l, int r, int v)
{
split(l, r);
need->Add(v);
}
inline void reverse(int l, int r)
{
split(l, r);
need->Rev();
}
inline int query(int l, int r)
{
split(l, r);
return need->mx;
}
#undef need
node* makeTree(node *p, int l, int r)
{
node *o = newnode(p);
int mid = (l + r) >> 1;
if (l < mid) o->ch[0] = makeTree(o, l, mid - 1);
if (mid < r) o->ch[1] = makeTree(o, mid + 1, r);
o->push_up();
return o;
}
inline void prepare(int n)
{
cur = nil = poolNode;
nil->ch[0] = nil->ch[1] = nil, nil->val = nil->mx = -inf;
root = newnode(nil);
root->ch[1] = newnode(root);
root->ch[1]->ch[0] = makeTree(root->ch[1], 1, n);
root->ch[1]->push_up(), root->push_up();
}
int main()
{
// freopen("in.txt", "r", stdin);
int n, m;
read(n), read(m);
prepare(n);
int opt, l, r, v;
while (m--)
{
read(opt), read(l), read(r);
switch(opt)
{
case 1 : read(v); modify(l, r, v); break;
case 2 : reverse(l, r); break;
case 3 : printf("%d
", query(l, r)); break;
}
}
return 0;
}