AT_abc339_g 题解
yyrwlj
·
·
题解
题意简述
给定一个序列，每次询问要求回答 [l, r] 区间中不大于 x 的数的和。强制在线。
思路
先考虑简化版，每次回答整个序列中不大于 x 的数的和，可以使用权值线段树维护。
然后回到原问题，发现这个满足前缀和的思想。$[l,r]$ 区间中不大于 $x$ 的数的和，就等于 $[1,r]$ 区间中不大于 $x$ 的数的和，减去 $[1,l-1]$ 区间中不大于 $x$ 的数的和。
我们可以建立 $n$ 棵权值线段树，让第 $r$ 棵减去第 $l-1$ 棵，在得到的新的权值线段树上查询。
发现这样空间会炸，我们可以使用“动态开点”的技巧。
每棵权值线段树相比上一棵，都只会有一条从根到叶的链发生改变。既然都不变了，那就让它们共用同一个空间，这样每次就只需要新建出 $\log_2n$ 个节点了。
这种数据结构叫做“可持久化权值线段树”。
注意：当离散化二分时，二分出来的位置对应的数不等于 $x$，那就让位置减一进行查询。
## Code
```cpp
struct Tree{
long long v;
int ls, rs;
}t[N << 8];
int a[N], tmp[N], root[N], cnt;
inline void pushup(int u)
{
t[u].v = t[t[u].ls].v + t[t[u].rs].v;
}
void update(int last,int u,int l,int r,int q)
{
if (l == r)
{
t[u].v += tmp[l];
return;
}
int mid = (l + r) >> 1;
if (q <= mid)
{
t[u].rs = t[last].rs;
t[u].ls = ++ cnt;
t[t[u].ls] = t[t[last].ls];
update(t[last].ls, t[u].ls, l, mid, q);
}
else
{
t[u].ls = t[last].ls;
t[u].rs = ++ cnt;
t[t[u].rs] = t[t[last].rs];
update(t[last].rs, t[u].rs, mid + 1, r, q);
}
pushup(u);
}
long long query(int u1,int u2,int l,int r,int x)
{
if (x < l)
return 0;
if (r <= x)
return t[u2].v - t[u1].v;
int mid = (l + r) >> 1;
return query(t[u1].ls, t[u2].ls, l, mid, x) + query(t[u1].rs, t[u2].rs, mid + 1, r, x);
}
int main()
{
for (int i=1;i<=n;i++)
{
scanf("%d", &a[i]);
tmp[i] = a[i];
}
sort(tmp + 1, tmp + n + 1);
int end = unique(tmp + 1, tmp + n + 1) - tmp - 1;
for (int i=1;i<=n;i++)
{
root[i] = ++cnt;
update(root[i - 1], root[i], 1, end, lower_bound(tmp + 1, tmp + end + 1, a[i]) - tmp);
}
long long ans = 0;
while (m--)
{
long long l, r, x;
l ^= ans, r ^= ans, x ^= ans;
int xx = lower_bound(tmp + 1, tmp + end + 1, x) - tmp;
if (x != tmp[xx])
xx --;
ans = query(root[l - 1], root[r], 1, end, xx);
}
return 0;
}
```