尝试用splay来做一下这个题,效率果然比线段树低好多…甚至快赶上在线下标计算的分块了
debug了好久,最后发现是打懒标记时对应节点信息的处理时机不对
懒标记如果会影响到节点内部的信息(例如sum, max之类),应该在
- 每次做修改操作打懒标记
- pushdown操作懒标记下传
这两个地方就把对应的节点信息或者子节点信息更新成懒标记影响后的值,避免在pushup时才不会出现只打了标记信息没有及时更新的情况
y总在Acwing 955 维护数列这个题有讲到过这种懒标记处理的问题
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m, root, idx;
int a[N];
struct Node{
int s[2], p, v, size;
LL add, sum;
void init(int v_, int p_)
{
v = v_, p = p_ , sum = v, size = 1;
}
} tr[N];
void pushup(int u)
{
tr[u].sum = tr[tr[u].s[0]].sum + tr[tr[u].s[1]].sum + tr[u].v;
tr[u].size = tr[tr[u].s[0]].size + tr[tr[u].s[1]].size + 1;
}
void pushdown(int u)
{
if(tr[u].add)
{
tr[tr[u].s[0]].add += tr[u].add, tr[tr[u].s[0]].sum += tr[tr[u].s[0]].size * tr[u].add;
tr[tr[u].s[1]].add += tr[u].add, tr[tr[u].s[1]].sum += tr[tr[u].s[1]].size * tr[u].add;
tr[tr[u].s[0]].v += tr[u].add, tr[tr[u].s[1]].v += tr[u].add;
tr[u].add = 0;
}
}
void rotate(int x)
{
int y = tr[x].p, z = tr[y].p;
int k = tr[y].s[1] == x;
tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
tr[x].s[k ^ 1] = y, tr[y].p = x;
pushup(y), pushup(x);
}
void splay(int x, int k)
{
while(tr[x].p != k)
{
int y = tr[x].p, z = tr[y].p;
if(z != k)
if((tr[z].s[1] == y) ^ (tr[y].s[1] == x)) rotate(x);
else rotate(y);
rotate(x);
}
if(!k) root = x;
}
int get_k(int k)
{
int u = root;
while(true)
{
pushdown(u);
if(tr[tr[u].s[0]].size >= k) u = tr[u].s[0];
else if(tr[tr[u].s[0]].size + 1 == k) return u;
else k -= tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
}
return -1;
}
int build(int l, int r, int p)
{
int mid = l + r >> 1;
int u = ++idx;
tr[u].init(a[mid], p);
if(l < mid) tr[u].s[0] = build(l, mid - 1, u);
if(r > mid) tr[u].s[1] = build(mid + 1, r, u);
pushup(u);
return u;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) scanf("%d", a + i);
root = build(0, n + 1, 0);
while(m --)
{
char op[2];
int l, r, d;
scanf("%s", op);
if(*op == 'C')
{
scanf("%d%d%d", &l, &r, &d);
l = get_k(l), r = get_k(r + 2);
splay(l, 0), splay(r, l);
tr[tr[r].s[0]].v += d, tr[tr[r].s[0]].add += d, tr[tr[r].s[0]].sum += tr[tr[r].s[0]].size * d;
pushup(r), pushup(l);
}
else
{
scanf("%d%d", &l, &r);
l = get_k(l), r = get_k(r + 2);
splay(l, 0), splay(r, l);
printf("%lld\n", tr[tr[r].s[0]].sum);
pushup(r), pushup(l);
}
}
return 0;
}