题解 P2042 【[NOI2005]维护数列】
Creeper_LKF
2018-02-02 10:44:23
# 指针版非旋Treap
本来写的好好的，然后调指针调的......大概是我太弱了
然后就拿了@曦月__OFN 大佬的代码来对着调
然后代码就长得极其相似......
似乎楼下题解还有一篇差不多的，但是我们不在意这些细节
指针的好处:
1. 写多了其实就好调了
1. ~~锻炼代码能力~~
1. 方便递归
1. 可以回收内存
1. 有些操作方便
指针的坏处：
1. 同一个程序在不同机子下的表现不同（例如32位和64位）
1. 蒟蒻杀手，不方便调试
1. 分配内存略慢（当然可以开内存池）
1. 莫名RE
1. 有些操作不方便
然后接下来是代码部分，最后一段的system是用来检测内存大小：
```
#include <cstdio>
#include <cctype>
#include <cstdlib>
using namespace std;
#define MAXN 500050
#define INF 0x3f3f3f3f
#define Finline __inline__ __attribute__ ((always_inline))
const int MODS = 5371321, PRI = 832211;
Finline char get_char(){
static char buf[10000001], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 10000000, stdin), p1 == p2) ? EOF : *p1 ++;
}
inline int read(){
int num = 0;
char c, sf = 1;
while (!isdigit(c = get_char()) && c != '-');
if(c == '-') c = get_char(), sf = -1;
while (num = num * 10 + c - 48, isdigit(c = get_char()));
return num * sf;
}
inline void swap(int &x, int &y){
int t = x;
x = y;
y = t;
}
Finline int max(int a, int b){
int c = (a - b) >> 31;
return (a & ~ c) | (b & c);
}
Finline int min(int a, int b){
int c = (a - b) >> 31;
return (a & c) | (b & ~ c);
}
Finline void upmin(int &a, const int &b){
if(a > b) a = b;
}
Finline void upmax(int &a, const int &b){
if(a < b) a = b;
}
struct Node{
int size, val, wv, cov;
int sum, lm, rm, sm;
bool rev;
Node *lc, *rc;
};
int top, cnt;
Node* root, *stack[MAXN];
inline void swap(Node* &x, Node* &y){
Node* t = x;
x = y;
y = t;
}
inline Node* NewNode(int val){
Node *ret;
if((ret = (Node*)malloc(sizeof(Node))) == NULL) return NULL;
if(cnt) cnt--;
ret -> rev = false;
ret -> size = 1;
ret -> val = ret -> sum = ret -> sm = val;
ret -> wv = rand();
ret -> cov = INF;
ret -> lm = ret -> rm = max(val, 0);
ret -> lc = ret -> rc = NULL;
return ret;
}
int n, m;
inline int rand(){
static int sed = 15;
return sed = 1ll * sed * PRI % MODS;
}
inline void Del(Node *node){
if(node == NULL) return ;
Del(node -> lc), Del(node -> rc);
free(node);
cnt++;
}
inline void Cover(Node *node, int val){
node -> val = val;
node -> sum = (node -> size) * val;
node -> lm = node -> rm = max(node -> sum, 0);
node -> sm = max(node -> sum, node -> val);
node -> cov = val;
}
inline void Reverse(Node* &node){
swap(node -> lc, node -> rc);
swap(node -> lm, node -> rm);
node -> rev ^= 1;
}
inline void Push_Up(Node *node){
bool l = node -> lc == NULL, r = node -> rc == NULL;
node -> size = (l ? 0 : node -> lc -> size) + (r ? 0 : node -> rc -> size) + 1;
node -> sum = (l ? 0 : node -> lc -> sum) + (r ? 0 : node -> rc -> sum) + node -> val;
node -> sm = max(max((l ? -INF : node -> lc -> sm), (r ? -INF : node -> rc -> sm)), (l ? 0 : node -> lc -> rm) + (r ? 0 : node -> rc -> lm) + node -> val);
node -> lm = max((l ? 0 : node -> lc -> lm), (l ? 0 : node -> lc -> sum) + (r ? 0 : node -> rc -> lm) + node -> val);
node -> rm = max((r ? 0 : node -> rc -> rm), (r ? 0 : node -> rc -> sum) + (l ? 0 : node -> lc -> rm) + node -> val);
}
inline void Push_Down(Node *node){
if(node -> rev){
node -> rev = false;
if(node -> lc != NULL) Reverse(node -> lc);
if(node -> rc != NULL) Reverse(node -> rc);
}
if(node -> cov != INF){
if(node -> lc != NULL) Cover(node -> lc, node -> cov);
if(node -> rc != NULL) Cover(node -> rc, node -> cov);
node -> cov = INF;
}
}
inline Node* Merge(Node* x, Node* y){
if(x != NULL) Push_Down(x);
if(y != NULL) Push_Down(y);
if(x == NULL || y == NULL) return x == NULL ? y : x;
if(x -> wv < y -> wv){
x -> rc = Merge(x -> rc, y);
Push_Up(x);
return x;
} else {
y -> lc = Merge(x, y -> lc);
// if(y == y -> lc) printf("Dead in line %d of %d\n", __LINE__, y -> wv);
Push_Up(y);
return y;
}
}
inline void Split(Node* node, int k, Node* &x, Node* &y){
if(node == NULL){
x = y = NULL;
return;
}
Push_Down(node);
if((node -> lc == NULL ? 0 : node -> lc -> size) >= k){
y = node;
Split(node -> lc, k, x, node -> lc);
} else {
x = node;
Split(node -> rc, k - 1 - (node -> lc == NULL ? 0 : node -> lc -> size), node -> rc, y);
}
Push_Up(node);
}
int main(){
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
n = read(), m = read();
for(int i = 1; i <= n; i++){
int val = read();
Node *p = NewNode(val), *tmp = NULL;
if(top) stack[top] -> rc = p;
p -> lc = tmp, stack[++top] = p;
}
while(top) Push_Up(stack[top--]);
root = stack[1];
while(m--){
char cons;
while(!isalpha(cons = get_char()));
if(cons == 'I'){
int st = read(), tot = read();
for(int i = 1; i <= tot; i++){
int val = read();
Node *p = NewNode(val), *tmp = NULL;
while(cnt && stack[top] != NULL && stack[top] -> wv > p -> wv){
Push_Up(stack[top]);
tmp = stack[top];
stack[top--] = NULL;
}
if(top) stack[top] -> rc = p;
p -> lc = tmp, stack[++top] = p;
}
Node *ls = NULL, *rs = NULL, *tmp;
while(top) Push_Up(stack[top--]);
tmp = stack[1];
Split(root, st, ls, rs);
root = Merge(Merge(ls, tmp), rs);
} else if(cons == 'D'){
int st = read(), k = read();
Node *ls = NULL, *rs = NULL, *xs = NULL, *ys = NULL;
Split(root, st - 1, ls, rs);
Split(rs, k, xs, ys);
root = Merge(ls, ys);
cnt += xs == NULL ? 0 : xs -> size;
Del(xs);
} else if(cons == 'R'){
int st = read(), k = read();
Node *ls = NULL, *rs = NULL, *xs = NULL, *ys = NULL;
Split(root, st - 1, ls, rs);
Split(rs, k, xs, ys);
Reverse(xs);
root = Merge(ls, Merge(xs, ys));
} else if(cons == 'G'){
while(!isspace(get_char()));
int st = read(), k = read();
Node *ls = NULL, *rs = NULL, *xs = NULL, *ys = NULL;
Split(root, st - 1, ls, rs);
Split(rs, k, xs, ys);
if(xs == NULL) puts("0");
else printf("%d\n", xs -> sum);
root = Merge(ls, Merge(xs, ys));
} else {
cons = get_char(), cons = get_char();
while(!isspace(get_char()));
if(cons == 'X') printf("%d\n", root -> sm);
else {
int st = read(), k = read(), val = read();
Node *ls = NULL, *rs = NULL, *xs = NULL, *ys = NULL;
Split(root, st - 1, ls, rs);
Split(rs, k, xs, ys);
Cover(xs, val);
root = Merge(ls, Merge(xs, ys));
}
}
}
// Debug Get Running Memery
// system("wmic process where name=\"a.exe\" get WorkingSetSize");
return 0;
}
```