%%%
by zhoujiarun @ 2024-04-26 16:17:57
%%%
by henry_qwh @ 2024-04-26 16:18:24
%%%
by xiangzhenze611 @ 2024-04-26 17:48:53
@[luuia](/user/557800) 你在reverse和cover里写pushdown干嘛，你这样每次都会遍历整个子树，肯定会超时
by qiuzijin2026 @ 2024-04-26 18:56:30
@[luuia](/user/557800) 还有，你get_node里面怎么不pushdown，有交换的话会WA。
by qiuzijin2026 @ 2024-04-26 19:00:42
@[luuia](/user/557800) 你的remove里面也有问题，你只是把它放进了队列，并没有切断他们之间的父子关系。
by qiuzijin2026 @ 2024-04-26 19:03:06
@[luuia](/user/557800) AC代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int read()
{
int s = 0,w = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') w = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
s = (s << 1) + (s << 3) + (ch ^ 48);
ch = getchar();
}
return s * w;
}
void write(int a)
{
if(a < 0) putchar('-'),a = -a;
if(a > 9) write(a / 10);
putchar(a % 10 + '0');
}
const int N = 4e6 + 10,inf = 2147483647;
int n,m,c,x,y,z,a[N];
int pos,tot;
int stk[N >> 3],len;
string opt;
struct FHQ
{
int tot,root;
int val[N],dat[N],size[N],son[N][2];
int sum[N],maxqz[N],maxhz[N],maxzd[N],cov[N];
bool lazy[N],tag[N];
int New(int x)
{
tot = stk[len--];
val[tot] = sum[tot] = x;
size[tot] = 1,dat[tot] = rand();
son[tot][0] = son[tot][1] = lazy[tot] = tag[tot] = 0;
maxqz[tot] = maxhz[tot] = max(x,0);
maxzd[tot] = x;
return tot;
}
void reverse(int p)
{
if(p == 0) return;
swap(son[p][0],son[p][1]);
swap(maxhz[p],maxqz[p]);
lazy[p] ^= 1;
}
void cover(int p,int c)
{
val[p] = cov[p] = c,sum[p] = size[p] * c;
maxqz[p] = maxhz[p] = max(sum[p],0);
maxzd[p] = max(c,sum[p]);
tag[p] = 1;
}
void pushup(int p)
{
if(p == 0) return;
size[p] = size[son[p][0]] + size[son[p][1]] + 1;
sum[p] = sum[son[p][0]] + sum[son[p][1]] + val[p];
maxqz[p] = max(max(maxqz[son[p][0]],maxqz[son[p][1]] + val[p] + sum[son[p][0]]),0);
maxhz[p] = max(max(maxhz[son[p][1]],maxhz[son[p][0]] + val[p] + sum[son[p][1]]),0);
maxzd[p] = val[p] + max(maxqz[son[p][1]] + maxhz[son[p][0]],0);
if(son[p][0]) maxzd[p] = max(maxzd[p],maxzd[son[p][0]]);
if(son[p][1]) maxzd[p] = max(maxzd[p],maxzd[son[p][1]]);
}
void pushdown(int p)
{
if(p == 0) return;
if(lazy[p])
{
if(son[p][0]) reverse(son[p][0]);
if(son[p][1]) reverse(son[p][1]);
lazy[p] = 0;
}
if(tag[p])
{
if(son[p][0]) cover(son[p][0],cov[p]);
if(son[p][1]) cover(son[p][1],cov[p]);
tag[p] = cov[p] = 0;
}
}
void split(int p,int k,int &x,int &y)
{
if(p == 0) {x = y = 0;return;}
pushdown(p);
if(size[son[p][0]] + 1 <= k) x = p,split(son[p][1],k - size[son[p][0]] - 1,son[p][1],y);
else y = p,split(son[p][0],k,x,son[p][0]);
pushup(p);
}
int merge(int u,int v)
{
if(u == 0 || v == 0) return u | v;
if(dat[u] > dat[v])
{
pushdown(u);
son[u][1] = merge(son[u][1],v);
pushup(u);
return u;
}
else
{
pushdown(v);
son[v][0] = merge(u,son[v][0]);
pushup(v);
return v;
}
}
void remove(int &p)
{
if(p == 0) return;
stk[++len] = p;
if(son[p][0]) remove(son[p][0]);
if(son[p][1]) remove(son[p][1]);
p=0;
}
int get_node(int p,int k)
{
while(1)
{
pushdown(p);
if(k <= size[son[p][0]]) p = son[p][0];
else if(k == size[son[p][0]] + 1) return p;
else k -= size[son[p][0]] + 1,p = son[p][1];
}
}
int get_val(int p,int k){return val[get_node(p,k)];}
int build(int l,int r)
{
if(l == r){return New(a[l]);}
int mid = (l + r) >> 1;
int x = merge(build(l,mid),build(mid + 1,r));
return x;
}
}tree;
int main()
{
// freopen("input.in","r",stdin);
// freopen("out.out","w",stdout);
srand(time(0));
n = read(),m = read();
for(int i = 1;i <= 2e5;i++) stk[++len] = i;
for(int i = 1;i <= n;i++) a[i] = read();
tree.root = tree.merge(tree.root,tree.build(1,n));
while(m--)
{
cin >> opt;
if(opt == "INSERT")
{
int x,y,z;
pos = read(),tot = read();
tree.split(tree.root,pos,x,y);
for(int i = 1;i <= tot;i++) a[i] = read();
tree.root = tree.merge(tree.merge(x,tree.build(1,tot)),y);
}
if(opt == "DELETE")
{
int x,y,z;
pos = read(),tot = read();
tree.split(tree.root,pos - 1,x,y);
tree.split(y,tot,y,z);
tree.remove(y);
tree.root = tree.merge(x,z);
}
if(opt == "MAKE-SAME")
{
int x,y,z;
pos = read(),tot = read(),c = read();
tree.split(tree.root,pos - 1,x,y);
tree.split(y,tot,y,z);
tree.cover(y,c);
tree.root = tree.merge(tree.merge(x,y),z);
}
if(opt == "REVERSE")
{
int x,y,z;
pos = read(),tot = read();
tree.split(tree.root,pos - 1,x,y);
tree.split(y,tot,y,z);
tree.reverse(y);
tree.root = tree.merge(tree.merge(x,y),z);
}
if(opt == "GET-SUM")
{
int x,y,z;
pos = read(),tot = read();
tree.split(tree.root,pos - 1,x,y);
tree.split(y,tot,y,z);
write(tree.sum[y]),putchar('\n');
tree.root = tree.merge(tree.merge(x,y),z);
}
if(opt == "GET")
{
pos = read();
write(tree.get_val(tree.root,pos)),putchar('\n');
}
if(opt == "MAX-SUM")
{
int x,y,z;
pos = read(),tot = read();
tree.split(tree.root,pos - 1,x,y);
tree.split(y,tot,y,z);
write(tree.maxzd[y]),putchar('\n');
tree.root = tree.merge(tree.merge(x,y),z);
}
}
return 0;
}
```
by qiuzijin2026 @ 2024-04-26 19:03:52
@[qiuzijin2026](/user/753211) 感谢 拜谢草神 /bx /bx
by luuia @ 2024-04-26 22:15:48