| 记录编号 |
251884 |
评测结果 |
MMMMMMMMMM |
| 题目名称 |
[NOI 2005]维护数列 |
最终得分 |
0 |
| 用户昵称 |
 Fmuckss |
是否通过 |
未通过 |
| 代码语言 |
C++ |
运行时间 |
0.000 s |
| 提交时间 |
2016-04-18 19:54:04 |
内存使用 |
0.00 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
using namespace std;
int n, m;
const int maxn = 5e6;
const int inf = 2e9;
class splay_tree {
private:
struct node {
int ls, rs, fa;
int v, sum, mx_l, mx_r, mx, size;
//权值， 子树和， 从子树区间内从左延伸的最大和， ....右....， 子树最大和
bool revc, same;
//反转标记，同化标记
node() {
size = ls = rs = fa = v = sum = mx_l = mx_r = 0;
mx = -inf;
same = revc = false;
}
}ns[maxn];
int node_cnt;
int del_que[maxn], del_top;
inline int new_node() {
if(del_top) return del_que[del_top--];
return ++node_cnt;
}
inline void del_node(int &now) {
ns[now] = node();
del_que[++del_top] = now;
now = 0;
}
inline void update(int &tar) {
if(!tar) return;//对于根节点不做处理，下面同此
int ls = ns[tar].ls, rs = ns[tar].rs;
ns[tar].size = ns[ls].size + ns[rs].size + 1;
ns[tar].sum = ns[ls].sum + ns[rs].sum + ns[tar].v;
ns[tar].mx_l = max(ns[ls].mx_l, ns[ls].sum + ns[tar].v + ns[rs].mx_l);
ns[tar].mx_r = max(ns[rs].mx_r, ns[rs].sum + ns[tar].v + ns[ls].mx_r);
ns[tar].mx = max(ns[ls].mx, ns[rs].mx);
ns[tar].mx = max(ns[tar].mx, ns[ls].mx_r + ns[tar].v + ns[rs].mx_l);
}
inline void make_same(int &tar, int &v) {
if(!tar) return;
ns[tar].v = v;
ns[tar].sum = ns[tar].v * ns[tar].size;
if(v > 0) ns[tar].mx_l = ns[tar].mx_r = ns[tar].mx = ns[tar].sum;//如果v大于0，这是显然的.....
else ns[tar].mx_l = ns[tar].mx_r = 0, ns[tar].mx = v; //mxl与mxr可以为0
ns[tar].same = true;
}
inline void make_revc(int &tar) {
if(!tar) return;
swap(ns[tar].mx_l, ns[tar].mx_r);
swap(ns[tar].ls, ns[tar].rs);
ns[tar].revc ^= 1;
}
inline void push_down(int &tar) {
if(!tar) return;
if(ns[tar].same) {
make_same(ns[tar].ls, ns[tar].v);
make_same(ns[tar].rs, ns[tar].v);
ns[tar].same = ns[tar].revc = false;//同化之后可以不用旋转
}
if(ns[tar].revc) {
make_revc(ns[tar].ls);
make_revc(ns[tar].rs);
ns[tar].revc = false;
}
}
inline void zig(int &tar) {
int fa = ns[tar].fa;
if(ns[ns[fa].fa].ls == fa) ns[ns[fa].fa].ls = tar;
else ns[ns[fa].fa].rs = tar;
ns[tar].fa = ns[fa].fa;
if(ns[tar].rs) ns[ns[tar].rs].fa = fa;
ns[fa].ls = ns[tar].rs;
ns[tar].rs = fa, ns[fa].fa = tar;
update(fa);
}
inline void zag(int &tar) {
int fa = ns[tar].fa;
if(ns[ns[fa].fa].ls == fa) ns[ns[fa].fa].ls = tar;
else ns[ns[fa].fa].rs = tar;
ns[tar].fa = ns[fa].fa;
if(ns[tar].ls) ns[ns[tar].ls].fa = fa;
ns[fa].rs = ns[tar].ls;
ns[tar].ls = fa, ns[fa].fa = tar;
update(fa);
}
inline void splay(int &now, int &tar) {
push_down(now);
if(now == tar) return;
int fa;
bool done = false;
while(!done) {
fa = ns[now].fa;
push_down(ns[fa].fa), push_down(fa), push_down(now);
if(fa == tar) done = true, ns[fa].ls == now ? zig(now) : zag(now);
else {
if(ns[fa].fa == tar) done = true;
if(ns[ns[fa].fa].ls == fa) ns[fa].ls == now ? zig(fa) : zag(now), zig(now);
else ns[fa].rs == now ? zag(fa) : zig(now), zag(now);
}
}
update(now);
}
public:
int cnt;
void outer(int tar) {
printf("now = %d ls = %d rs = %d v = %d size = %d\n", tar, ns[tar].ls, ns[tar].rs, ns[tar].v, ns[tar].size);
}
void dfs_test(int now) {
printf("%d ", cnt++);
outer(now);
push_down(now);
if(ns[now].ls) dfs_test(ns[now].ls);
//printf("%d ", cnt++);
//outer(now);
if(ns[now].rs) dfs_test(ns[now].rs);
update(now);
}
void test() {
cnt = 0;
dfs_test(ns[0].ls);
}
splay_tree() {
int be = new_node(), en = new_node();
ns[0].ls = be, ns[be].rs = en, ns[en].fa = be;
ns[0].v = ns[be].v = ns[en].v = -inf;
update(en), update(be);
}
inline void set_beg() {
int now = new_node();
ns[now].v = -inf;
}
inline int find(int &anc, int size) {//找到以anc为根的子树中第size个，并直接提到根
int now = anc;
while(true) {
push_down(now);//查找操作不进行更改，不需要update
int ls = ns[now].ls, rs = ns[now].rs;
if(size == ns[ls].size+1) break;
if(size <= ns[ls].size) now = ls;
else now = rs, size -= ns[ls].size+1;
}
splay(now, anc);
return now;
}
int build(int *a, int l, int r, int fa) {//直接根据序列建一颗完全二叉树插进去
if(l > r) return 0;
int now_root = new_node();
int mid = (l+r) >> 1;
ns[now_root].mx = ns[now_root].v = a[mid];
ns[now_root].fa = fa;
if(l == r) { update(now_root); return now_root; }
ns[now_root].ls = build(a, l, mid-1, now_root);
ns[now_root].rs = build(a, mid+1, r, now_root);
update(now_root);
return now_root;
}
inline void get_min(int &anc) {//将当前子树的最小值旋转到根节点
int now = anc;
while(ns[now].ls) {
push_down(now);
now = ns[now].ls;
}
splay(now, anc);
}
inline void insert(int tar, int *a, int &end) {
int son = build(a, 1, end, 0);
int now_root = find(ns[0].ls, tar+1);
if(ns[now_root].rs) {
push_down(now_root);
get_min(ns[now_root].rs);//把右子树最小的提到当前树根
// printf("\nbefore_insert_test\n");
// test();
ns[ns[now_root].rs].ls = son;
ns[son].fa = ns[now_root].rs;
update(ns[now_root].rs);
} else {//如果右节点为空直接加进去
// printf("\nbefore_insert_test\n");
// test();
ns[now_root].rs = son;
ns[son].fa = now_root;
}
update(now_root);
// printf("\nafter_insert_test\n");
// test();
}
void del(int &now) {
if(ns[now].ls) del(ns[now].ls);
if(ns[now].rs) del(ns[now].rs);
del_node(now);
}
inline void remove(int &tar, int &tot) {
int now_root = find(ns[0].ls, tar), to = find(ns[now_root].rs, tot+1);
del(ns[to].ls);
ns[to].ls = 0;
update(to), update(now_root);
// printf("\nremove_test:\n");
// test();
}
inline void change_same(int &tar, int &tot, int &v) {
int now_root = find(ns[0].ls, tar), to = find(ns[now_root].rs, tot+1);
make_same(ns[to].ls, v), push_down(ns[to].ls);
update(to), update(now_root);
// printf("\nsame_test:\n");
// test();
}
inline void change_revc(int &tar, int &tot) {
int now_root = find(ns[0].ls, tar), to = find(ns[now_root].rs, tot+1);
make_revc(ns[to].ls), push_down(ns[to].ls);
update(to), update(now_root);
// printf("\nrevc_test:\n");
// test();
}
inline int get_sum(int &tar, int &tot) {
int now_root = find(ns[0].ls, tar), to = find(ns[now_root].rs, tot+1);
// printf("\nsum_test:\n");
// test();
return ns[ns[to].ls].sum;
}
inline int get_max() {
return ns[ns[0].ls].mx;
}
}spt;
int get_num() {
int ans = 0, f = 1;
char tmp = getchar();
while(tmp < '0' || tmp > '9') { if(tmp == '-') f = -1; tmp = getchar(); }
while(tmp <= '9' && tmp >= '0') { ans = ans*10 + tmp - '0', tmp = getchar(); }
return f*ans;
}
int add[maxn];
void read() {
n = get_num(); m = get_num();
for(int i = 1; i <= n; i++) {
add[i] = get_num();
}
spt.insert(0, add, n);
}
void solve() {
char han[10];
int cnt;
int tar, tot, c;
for(int i = 1; i <= m; i++) {
// printf("%d:\n", i);
cnt = 0;
char tmp = getchar();
while(tmp < 'A' || tmp > 'Z') tmp = getchar();
while((tmp >= 'A' && tmp <= 'Z') || tmp == '-') { han[++cnt] = tmp, tmp = getchar(); }
if(han[1] == 'I') {
tar = get_num(), tot = get_num();
for(int j = 1; j <= tot; j++) add[j] = get_num();
spt.insert(tar, add, tot);
} else if(han[1] == 'D') {
tar = get_num(), tot = get_num();
spt.remove(tar, tot);
} else if(han[1] == 'R') {
tar = get_num(), tot = get_num();
spt.change_revc(tar, tot);
} else if(han[1] == 'G') {
tar = get_num(), tot = get_num();
printf("%d\n", spt.get_sum(tar, tot));
} else if(han[1] == 'M') {
if(han[3] == 'K') {
tar = get_num(), tot = get_num(), c = get_num();
spt.change_same(tar, tot, c);
} else {
printf("%d\n", spt.get_max());
}
}
}
}
int main() {
freopen("seq2005.in", "r", stdin);
freopen("seq2005.out", "w", stdout);
read();
solve();
return 0;
}