LYDSY 1500
题目大意
暂无
题目解法
暂无
RTFC
#include <cctype>
#include <cstdio>
const int inf = 0x3f3f3f3f;
template <typename T>
inline T max(const T &x, const T &y) { return x > y ? x : y; }
template <typename T>
inline void swap(T &x, T &y)
{
T t = x;
x = y;
y = t;
}
char buf[1 << 24], *S;
inline void read(int &x)
{
char ch = x = 0, flag = 1;
while (!isdigit(ch = *S++))
if (ch == '-') flag = -1;
for (; isdigit(ch); ch = *S++) x = x * 10 + ch - '0';
x *= flag;
}
inline char readop()
{
while (!isupper(*S++))
;
char *ret = ++S;
S += 5;
return *ret;
}
struct node
{
int val, sum, mx, lx, rx, sz;
node *fa, *ch[2];
bool rev, tag;
#define _get(x, y) \
int get##x() { return this == 0 ? (y) : this->x; }
_get(sum, 0) _get(mx, -inf) _get(lx, 0) _get(rx, 0) _get(sz, 0)
} *root;
struct
{
int cnt;
node pool[510010], *ptrs[510010];
void init()
{
cnt = 0;
for (int i = 0; i < 510010; i++) ptrs[i] = &pool[i];
}
inline node *alloc() { return ptrs[cnt++]; }
inline void free(node *x) { ptrs[--cnt] = x; }
} mem;
int a[510010];
inline int dir(node *x)
{
node *f = x->fa;
if (f == 0)
return -1;
else
return x == f->ch[1];
}
inline void rev_tree(node *x)
{
if (x == 0) return;
swap(x->lx, x->rx);
swap(x->ch[0], x->ch[1]);
x->rev ^= 1;
}
inline void set_tree(node *x, int v)
{
if (x == 0) return;
x->sum = x->sz * (x->val = v);
x->mx = max(v, v * x->sz);
x->lx = x->rx = max(0, x->mx);
x->tag = true, x->rev = false;
}
inline void push_down(node *x)
{
if (x == 0) return;
if (x->rev)
{
if (x->ch[0]) rev_tree(x->ch[0]);
if (x->ch[1]) rev_tree(x->ch[1]);
x->rev = false;
}
if (x->tag)
{
if (x->ch[0]) set_tree(x->ch[0], x->val);
if (x->ch[1]) set_tree(x->ch[1], x->val);
x->tag = false;
}
}
inline void push_down_recursive(node *x)
{
static node *stk[500010];
int top = 0;
while (x->fa) stk[top++] = (x = x->fa);
while (top) push_down(stk[--top]);
}
inline void update(node *x)
{
node *lc = x->ch[0], *rc = x->ch[1];
x->sum = x->val + lc->getsum() + rc->getsum();
x->sz = lc->getsz() + rc->getsz() + 1;
x->mx = max(x->val, max(lc->getmx(), rc->getmx()));
x->mx = max(x->mx, lc->getrx() + x->val + rc->getlx());
x->lx = max(lc->getlx(), lc->getsum() + x->val + max(0, rc->getlx()));
x->rx = max(rc->getrx(), rc->getsum() + x->val + max(0, lc->getrx()));
}
node *build_tree(int l, int r, node *f)
{
node *newNode = mem.alloc();
newNode->tag = newNode->rev = false;
int m = l + ((r - l) >> 1);
newNode->fa = f;
newNode->val = newNode->lx = newNode->rx = a[m];
newNode->ch[0] = l < m ? build_tree(l, m - 1, newNode) : 0;
newNode->ch[1] = m < r ? build_tree(m + 1, r, newNode) : 0;
update(newNode);
return newNode;
}
inline void liftup(node *x)
{
node *f = x->fa;
if (f == 0) return;
int d = dir(x);
node *ff = f->fa, *c = x->ch[d ^ 1];
if (ff == 0)
root = x;
else
ff->ch[dir(f)] = x;
x->fa = ff, f->fa = x, x->ch[d ^ 1] = f, f->ch[d] = c;
if (c) c->fa = f;
update(f), update(x);
}
inline void splay(node *x, node *target)
{
if (x == 0) return;
push_down_recursive(x);
node *f = 0, *ff = 0;
while ((f = x->fa) != target)
if ((ff = f->fa) == target)
liftup(x);
else if (dir(x) ^ dir(f))
liftup(x), liftup(x);
else
liftup(f), liftup(x);
}
inline void erase(node *x)
{
if (x == 0) return;
erase(x->ch[0]);
erase(x->ch[1]);
mem.free(x);
}
node *kth(node *x, int k)
{
push_down(x);
if (x->ch[0]->getsz() == k - 1)
return x;
else if (x->ch[0]->getsz() > k - 1)
return kth(x->ch[0], k);
else
return kth(x->ch[1], k - x->ch[0]->getsz() - 1);
}
int main()
{
fread(buf, 1, 1 << 24, stdin);
S = buf;
mem.init();
int n, m;
read(n), read(m);
a[0] = a[n + 1] = -inf;
for (int i = 1; i <= n; i++) read(a[i]);
root = build_tree(0, n + 1, 0);
while (m--)
{
char op = readop();
if (op == 'S') //INSERT
{
int posi, tot;
read(posi), read(tot);
for (int i = 1; i <= tot; i++) read(a[i]);
splay(kth(root, posi + 1), 0);
splay(kth(root->ch[1], 1), root);
root->ch[1]->ch[0] = build_tree(1, tot, root->ch[1]);
update(root->ch[1]), update(root);
}
if (op == 'L') //DELETE
{
int posi, tot;
read(posi), read(tot);
splay(kth(root, posi), 0);
splay(kth(root->ch[1], tot + 1), root);
erase(root->ch[1]->ch[0]);
root->ch[1]->ch[0] = 0;
update(root->ch[1]), update(root);
}
if (op == 'K') //MAKE-SAME
{
int posi, tot, val;
read(posi), read(tot), read(val);
splay(kth(root, posi), 0);
splay(kth(root->ch[1], tot + 1), root);
set_tree(root->ch[1]->ch[0], val);
update(root->ch[1]), update(root);
}
if (op == 'V') //REVERSE
{
int posi, tot;
read(posi), read(tot);
splay(kth(root, posi), 0);
splay(kth(root->ch[1], tot + 1), root);
rev_tree(root->ch[1]->ch[0]);
update(root->ch[1]), update(root);
}
if (op == 'T') //GET-SUM
{
int posi, tot;
read(posi), read(tot);
splay(kth(root, posi), 0);
splay(kth(root->ch[1], tot + 1), root);
printf("%d\n", root->ch[1]->ch[0]->getsum());
}
if (op == 'X') //MAX-SUM
{
printf("%d\n", root->getmx());
}
}
return 0;
}