hehehehehehehehehehe这道题我已经没有什么想说的了
zsl告诉我这道题他写的时候被恶心惨了 其实我写的时候觉得还蛮好写的 因为之前差不多的线段树的题
写好以后本机测cena全挂 然后姜神帮窝在linux下测一组wa两组卡过 因为哨兵没有特殊考虑orz。。。
然后交OJ！最开始没写回收空间！！！于是我就开了很大的空间！！！并没有MLE！！！！一直告诉我TLE！我把main函数注释得只剩读入了依旧TLE！！！！
后来翔爷告诉我 你内存开大了可能把评测机直接整死了……整死了……死了……了…………
改到最后看见accept的我眼泪掉下来
题目点这里
思路很简单不写了 差不多都是splay的基本操作 处理的时候注意细节就好了
#include <cstdio>
#include <iostream>
#include <queue>
#define lc c[0]
#define rc c[1]
using namespace std;
int readint()
{
char c;int sign = 1, n = 0; c = getchar();
while(c > '9' || c < '0'){ if(c == '-')sign = -1; c = getchar(); }
while(c <= '9' && c >= '0'){ n = n*10 + c-'0'; c = getchar();}
return n*sign;
}
const int inf = 0x3f3f3f3f;
const int maxn = 500005;
int N, M;
int cnt;
int a[maxn];
struct Splay{
struct node{
node *c[2], *f;
int w, s, sum;
int same; bool flag, rev;
int lm, rm, mm;
inline bool right() { return f -> rc == this; }
inline void setch(node *p, bool r) { c[r] = p; p -> f = this; }
inline void Same(int x)
{
flag = 1;
same = w = x;
sum = s * x;
lm = rm = mm = max(sum, w);
}
inline void flip()
{
rev ^= 1;
swap(lc, rc);
swap(lm, rm);
}
}T[maxn], *root, *null, *left, *right;
queue <node*> q;
inline node *NewNode(int w = 0)
{
if(q.size())
{
node *p = q.front(); q.pop();
p -> lc = p -> rc = p -> f = null;
p -> w = p -> sum = p -> lm = p -> rm = p -> mm = w;
p -> s = 1; p -> same = p -> rev = p -> flag = 0;
return p;
}
else
{
T[cnt].lc = T[cnt].rc = T[cnt].f = null;
T[cnt].w = T[cnt].sum = T[cnt].lm = T[cnt].rm = T[cnt].mm = w;
T[cnt].s = 1; T[cnt].same = T[cnt].rev = T[cnt].flag = 0;
return &T[cnt++];
}
}
inline void pushup(node *p)
{
p -> s = 1 + p -> lc -> s + p -> rc -> s;
p -> sum = p -> w + p -> lc -> sum + p -> rc -> sum;
if(p == left || p == right)
{
p -> lm = p -> lc -> lm;
p -> rm = p -> rc -> rm;
p -> mm = max(p->lc->mm, p->rc->mm);
return;
}
p -> lm = max(p->lc->lm, p->lc->sum + p->w + max(0, p->rc->lm));
p -> rm = max(p->rc->rm, p->rc->sum + p->w + max(0, p->lc->rm));
p -> mm = max(max(p->lc->mm, p->rc->mm), max(0,p->lc->rm) + p->w + max(0,p->rc->lm));
}
inline void pushdown(node *p)
{
if(p -> flag)
{
if(p -> lc != null) p -> lc -> Same(p -> same);
if(p -> rc != null) p -> rc -> Same(p -> same);
p -> flag = 0;
}
if(p -> rev)
{
if(p -> lc != null) p -> lc -> flip();
if(p -> rc != null) p -> rc -> flip();
p -> rev = 0;
}
}
inline void init()
{
null = NewNode(); null -> s = 0;
null -> lm = null -> rm = null -> mm = -inf;
root = NewNode(); node *p = NewNode();
root -> lm = root -> rm = root -> mm = -inf;
p -> lm = p -> rm = p -> mm = -inf; left = root; right = p;
root -> setch(p, 1); root -> s = 2;
}
void rotate(node *p)
{
node *fa = p -> f; bool r = p -> right();
fa -> f -> setch(p, fa -> right());
fa -> setch(p -> c[r ^ 1], r);
p -> setch(fa, r ^ 1);
pushup(fa);
}
void splay(node *p, node *fa)
{
while(p -> f != fa)
{
if(p -> f -> f == fa) rotate(p);
else if(p -> right() == p -> f -> right())
{
rotate(p -> f);
rotate(p);
}
else
{
rotate(p);
rotate(p);
}
}
pushup(p);
if(p -> f == null) root = p;
}
node *find(int k)
{
for(node *p = root; ; )
{
pushdown(p);
int rank = p -> lc -> s + 1;
if(rank == k) return p;
if(rank > k) p = p -> lc;
else
{
k -= rank;
p = p -> rc;
}
}
}
node *getrange(int l, int r)
{
--l; ++r;
splay(find(l), null); splay(find(r), root);
return root -> rc -> lc;
}
void build(node *&p, node *fa, int l, int r, int rank)
{
p = NewNode(a[rank]); p -> f = fa;
if(l ^ rank) build(p -> lc, p, l, rank-1, l+rank-1 >> 1);
if(r ^ rank) build(p -> rc, p, rank+1, r, rank+1+r >> 1);
pushup(p);
}
inline void pushrange() { pushup(root -> rc); pushup(root); }
inline void insert(int k, int num) // 将num个数放在第k个位置
{
node *temp = getrange(k, k - 1);
build(temp, root -> rc, 1, num, 1+num >> 1); root -> rc -> lc = temp;
pushrange();
}
void re(node *p)
{
q.push(p);
if(p -> lc != null) re(p -> lc);
if(p -> rc != null) re(p -> rc);
}
inline void del(int l, int r)
{
getrange(l, r);
re(root -> rc -> lc);
root -> rc -> lc = null;
pushrange();
}
inline void makesame(int l, int r, int x)
{
node *temp = getrange(l, r);
temp -> Same(x);
pushrange();
}
inline void reverse(int l, int r)
{
node *temp = getrange(l, r);
temp -> flip();
pushrange();
}
inline void getsum(int l, int r)
{
node *temp = getrange(l, r);
printf("%d\n", temp -> sum);
}
inline void maxsum()
{
printf("%d\n", root -> mm);
}
}s;
int main()
{
scanf("%d%d", &N, &M); s.init();
for(int i = 1; i <= N; ++i) scanf("%d", &a[i]);
s.insert(2, N);
char sign[10];
while(M--)
{
scanf("%s", sign); int pos, tot, c;
switch(sign[2])
{
case 'S' : // insert
{
scanf("%d%d", &pos, &tot);
for(int i = 1; i <= tot; ++i) scanf("%d", &a[i]);
s.insert(pos + 2, tot);break;
}
case 'L' : // delete
{
scanf("%d%d", &pos, &tot);
s.del(pos + 1, pos + tot); break;
}
case 'K' : // makesame
{
scanf("%d%d%d", &pos, &tot, &c);
s.makesame(pos + 1, pos + tot, c); break;
}
case 'V' : // reverse
{
scanf("%d%d", &pos, &tot);
s.reverse(pos + 1, pos + tot); break;
}
case 'T' : // getsum
{
scanf("%d%d", &pos, &tot);
s.getsum(pos + 1, pos + tot); break;
}
case 'X' : // maxsum
{
s.maxsum(); break;
}
}
}
return 0;
}
![树的基本概念(定义、基本术语、性质)[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)