题解：P16715 哀叹
lailai0916
·
·
题解
题意简述
令 c_i 为 a_1\sim a_i 中最大的 b_i 个数之和。每次询问临时把 a_x 改为 w，并把 b_y 改为 k，求修改后的 \sum c_i。各次询问互相独立。
解题思路
记 T(i,k) 为前缀 a_1\sim a_i 中最大的 k 个数之和。若已知前缀和 s_i，只需求出最小的 i-k 个数之和：
T(i,k)=s_i-\operatorname{small}(1,i,i-k)
先按原数组计算所有 c_i=T(i,b_i)，并求出总和 S。每次询问都在 S 上叠加修改产生的差值。
考虑把 a_x=v 改为 w。只有 i\ge x 的前缀会受影响。令：
d_i=i-b_i
原来未被选中的是前缀中最小的 d_i 个数。定义 X_i 为第 d_i+1 小值，也就是被选部分的最小边界。定义 Y_i 为第 d_i 小值，也就是未选部分的最大边界。若 d_i=0，令 Y_i=0。
当 w>v 时，修改对前缀 i 的贡献为：
\Delta_i=
\begin{cases}
w-v & X_i\le v \\
w-X_i & v<X_i<w \\
0 & X_i\ge w
\end{cases}
第一种情况中，旧值已经位于被选集合，增大后仍被选。第二种情况中，旧值未被选，新值则替换边界 X_i。第三种情况中新值仍未越过边界。
当 w<v 时，贡献改由 Y_i 决定：
\Delta_i=
\begin{cases}
0 & Y_i\ge v \\
Y_i-v & w\le Y_i<v \\
w-v & Y_i<w
\end{cases}
若 Y_i\ge v，旧值本来就未被选。若 w\le Y_i<v，降低后的旧值退出被选集合，Y_i 补入。若 Y_i<w，新旧值都在被选集合中，只产生自身差值。
这些分类只比较顺序统计量，不依赖某个相同数值的具体副本。因此，数组存在相同元素时结论仍成立。
要求所有 i\in[x,n] 的贡献和，只需按值域统计下标区间内 X_i 或 Y_i 的个数与总和。
例如 w>v 时，设 X_i\le v 的个数为 p_1。再设 v<X_i<w 的个数、总和为 p_2,z_2，则：
\Delta_a=p_1(w-v)+p_2w-z_2
这里使用静态小波矩阵。对一个非负整数序列，从最高位到最低位稳定划分。当前位为 $0$ 的元素放在前半，为 $1$ 的元素放在后半。每一层保存三项信息：
- 每个前缀中零位元素的个数；
- 每个前缀中零位元素的总和；
- 本层全部零位元素的数量。
给定下标区间与值 $z$，从高位向低位下降。若 $z$ 当前位为 $1$，本层所有零位元素都小于 $z$。把它们的个数和总和加入答案，再进入一位区间。否则，直接进入零位区间。这样可求出值小于 $z$ 的元素个数与总和。
两个「小于」查询相减，就能得到任意值域区间的个数与总和。同样沿层下降，还可以求区间第 $k$ 小值，以及最小 $k$ 个数之和。值域不超过 $10^6$，固定处理 $20$ 个二进制位即可。
分别对原数组 $a$、阈值数组 $X$ 和阈值数组 $Y$ 建立小波矩阵。第一份结构计算 $T(i,k)$、$X_i$ 和 $Y_i$；后两份结构批量计算 $\Delta_a$。
最后处理 $b_y$ 的同时修改。定义 $H(y,k)$ 为已经把 $a_x$ 改成 $w$ 后，前缀 $y$ 中最大的 $k$ 个数之和。
先用原数组的小波矩阵求 $T(y,k)$。若 $y<x$，前缀不包含被修改的元素，答案无需调整。若 $y\ge x$，令 $d=y-k$，再取该前缀的第 $d+1$ 小值或第 $d$ 小值。按照前述单个前缀的分类，便能把 $T(y,k)$ 修正为 $H(y,k)$。
$\Delta_a$ 已经包含位置 $y$ 在原参数 $b_y$ 下受到的变化。把 $b_y$ 改为 $k$ 时，只需补上：
$$
\Delta_b=H(y,k)-H(y,b_y)
$$
相减会先撤销位置 $y$ 在旧参数下的完整结果，再加入新参数下的完整结果。因此，不会重复计算 $a_x$ 对位置 $y$ 的影响。
每次询问的答案为：
$$
S+\Delta_a+\Delta_b
$$
小波矩阵的预处理时间和空间复杂度均为 $O(n\log V)$。每次询问只执行常数次顺序统计与二维区间统计。因此，询问时间复杂度为 $O(\log V)$。这里 $V=10^6$。
## 正确性证明
先证明 $a_x$ 修改的分类。前缀最大的 $b_i$ 个数与最小的 $d_i=i-b_i$ 个数以 $X_i,Y_i$ 为边界。
增大元素时，它只可能保持原归属，或越过 $X_i$ 替换最小被选值。减小元素时，它只可能保持原归属，或跌破 $Y_i$ 并由最大未选值补入。所有情况对应给出的三段公式。因此，$\Delta_a$ 等于所有受影响前缀的真实变化量之和。
再证明小波矩阵查询。每一层的稳定划分保持同一位分支内的相对下标区间。沿目标值的二进制位下降时，加入的零分支恰好是已经确定小于目标的元素。故区间计数、区间求和、第 $k$ 小值和最小 $k$ 个数之和都准确。
最后证明两个修改的合并。$S+\Delta_a$ 是只修改 $a_x$ 后的完整答案，其中位置 $y$ 仍使用 $b_y$。$H(y,b_y)$ 正是此时位置 $y$ 的值，$H(y,k)$ 是再修改 $b_y$ 后的新值。减去前者并加入后者，恰好只替换 $c_y$。因此，最终表达式同时且仅计算了题目要求的两处临时修改。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pil=pair<int,ll>;
const int N=100005;
const int B=20;
struct WM
{
vector<int> c[B];
vector<ll> s[B];
int mid[B];
void build(vector<int> a)
{
int n=a.size();
vector<int> b(n);
for(int k=B-1;k>=0;k--)
{
c[k].resize(n+1);
s[k].resize(n+1);
for(int i=0;i<n;i++)
{
c[k][i+1]=c[k][i]+(!(a[i]>>k&1));
s[k][i+1]=s[k][i]+((a[i]>>k&1)?0:a[i]);
}
mid[k]=c[k][n];
int x=0,y=mid[k];
for(auto v:a)
{
if(v>>k&1)b[y++]=v;
else b[x++]=v;
}
a.swap(b);
}
}
pil less(int l,int r,int x)
{
int cnt=0;
ll sum=0;
for(int k=B-1;k>=0;k--)
{
int x1=c[k][l],x2=c[k][r];
if(x>>k&1)
{
cnt+=x2-x1;
sum+=s[k][r]-s[k][l];
l=mid[k]+l-x1;
r=mid[k]+r-x2;
}
else
{
l=x1;
r=x2;
}
}
return {cnt,sum};
}
pil query(int l,int r,int x,int y)
{
if(x>y)return {0,0};
auto p=less(l-1,r,y+1),q=less(l-1,r,x);
return {p.first-q.first,p.second-q.second};
}
int kth(int l,int r,int x)
{
l--;
int res=0;
for(int k=B-1;k>=0;k--)
{
int cnt=c[k][r]-c[k][l];
if(x<=cnt)
{
l=c[k][l];
r=c[k][r];
}
else
{
x-=cnt;
res|=1<<k;
l=mid[k]+l-c[k][l];
r=mid[k]+r-c[k][r];
}
}
return res;
}
ll sum(int l,int r,int x)
{
if(!x)return 0;
l--;
ll res=0;
int val=0;
for(int k=B-1;k>=0;k--)
{
int cnt=c[k][r]-c[k][l];
if(x<=cnt)
{
l=c[k][l];
r=c[k][r];
}
else
{
x-=cnt;
res+=s[k][r]-s[k][l];
val|=1<<k;
l=mid[k]+l-c[k][l];
r=mid[k]+r-c[k][r];
}
}
return res+1LL*x*val;
}
}ta,tx,ty;
int a[N],b[N],xv[N],yv[N];
ll s[N];
ll get(int i,int k)
{
return s[i]-ta.sum(1,i,i-k);
}
ll change(int x,int y,int w,int k)
{
ll res=get(y,k);
if(y<x)return res;
int v=a[x],d=y-k;
if(w>v)
{
int z=ta.kth(1,y,d+1);
if(z<=v)res+=w-v;
else if(z<w)res+=w-z;
}
else if(w<v)
{
int z=d?ta.kth(1,y,d):0;
if(z>=v)return res;
if(z>=w)res+=z-v;
else res+=w-v;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,q;
cin>>n>>q;
vector<int> z(n);
for(int i=1;i<=n;i++)
{
cin>>a[i];
s[i]=s[i-1]+a[i];
z[i-1]=a[i];
}
for(int i=1;i<=n;i++)cin>>b[i];
ta.build(z);
ll ans=0;
for(int i=1;i<=n;i++)
{
int d=i-b[i];
ans+=get(i,b[i]);
xv[i]=ta.kth(1,i,d+1);
yv[i]=d?ta.kth(1,i,d):0;
}
for(int i=1;i<=n;i++)z[i-1]=xv[i];
tx.build(z);
for(int i=1;i<=n;i++)z[i-1]=yv[i];
ty.build(z);
while(q--)
{
int x,w,y,k;
cin>>x>>w>>y>>k;
int v=a[x];
ll da=0;
if(w>v)
{
auto p=tx.query(x,n,0,v);
da+=(ll)p.first*(w-v);
p=tx.query(x,n,v+1,w-1);
da+=(ll)p.first*w-p.second;
}
else if(w<v)
{
auto p=ty.query(x,n,0,w-1);
da+=(ll)p.first*(w-v);
p=ty.query(x,n,w,v-1);
da+=p.second-(ll)p.first*v;
}
ll db=change(x,y,w,k)-change(x,y,w,b[y]);
cout<<ans+da+db<<'\n';
}
return 0;
}
```