题解：P11368 [Ynoi2024] After god
hongyuecheng
·
·
题解
P11368 [Ynoi2024] After god 题解
前言
这是道好题。前置知识点： 线段树3
题意
对一个初始状态全为 0 的序列维护一个前缀最大值，有 n 次修改，每次修改完查询一个区间历史和。
解题思路
这个是题目给出的样例，从下往上第 i 行对应进行第 i 次操作后的 a 序列（如红框代表第 1 次修改完后的 a 序列）。其中标红数字的是每次的修改。
上面这幅图从下往上第 i 行对应进行第 i 次操作后的前缀最大值序列。有颜色部分代表 a 序列，其中蓝色代表每次修改。
我们发现每次修改，只会影响发生修改的位置及其之后的位置。（红框内为修改后影响前缀最大值的范围）
我们现在横过来（横过来处理的原因之后会说明），对序列轴进行扫描。
将修改优先按 x 从小到大排序，再按 t（修改的时间，即这是第几次修改）从大到小排序。然后用线段树进行区间 max 操作维护。最后询问区间历史和（历史和是什么与如何维护后面会讲）。
以第一行为例。
先处理 t 最大的这个 2，这里我们记第 i 行上一次处理的位置为 last_i(初始都为 m+1)，那么我们对区间 [t,last_i-1]（即 [6,6]）进行区间 max 操作，然后 last_1 变为 6。
再处理 4,此时 t=4、last_1=6，就对 [4,5] 区间进行区间 max 操作。
再把 last_1 修改为 4。
然后以此类推处理其他修改。每一行处理完后对于这一行的第 j 个修改，记录答案为 [1,t_j] 的历史和。
为什么维护时间维
可能有人会有疑问：为什么我们不直接维护序列，而要横向维护时间轴，对序列维扫描线？
原因是这样的，当对一个位置 x_i 修改时，若其在此前不为零，则我们需先抹除其对后面的影响，再修改。而区间取 max 无法回退，就会导致错误。
举个例子。（其中标蓝为修改，标黑为前缀最大值）
从下向上看，我们发现在第 3 次修改时，无法单纯通过前一层得到。而横向扫描就不会出现这种问题。
区间历史和如何维护
记第 i 次操作后第 j 个位置上的值为 a_{i,j}，那么经过 k 次操作后，第 j 个位置上的历史和可以表示为如下。
h_j=\sum_{i=1}^{k}a_{i,j}
而区间 [l,r] 的区间历史和可以表示为如下。
hist_{l,r}=\sum_{j=l}^{r}h_j=\sum_{j=l}^{r}\sum_{i=1}^{k}a_{i,j}
假设我们在 i 时刻，对长为 len 的区间加了 x_i，那么在 t 时刻查询时这次修改对这段区间历史和的贡献就为 (t-i+1)\times x_i\times len。
展开后得到：
h_i=(t+1)\times x_i\times len+(x_i\times i)\times len
$$
hist_t=\sum_{i=1}^k [(t+1)\times x_i\times len+(x_i\times i)\times len]
$$
$$
hist_t=(t+1)\times \sum_{i=1}^k (x_i\times len)+ \sum_{i=1}^k (x_i\times i\times len)
$$
而查询时我们知道 $t$ 的值，于是我们线段树就维护 $x_i$ 和 $x_i\times i$ 的区间和就行了。
其实区间取 max 也可以看为区间加，原因就不细讲了。
## 代码实现
注意：我的代码中 $hist\_sum$ 存的不是历史和，而是 $x_i\times i$。
```cpp line-numbers
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m;
ll last[1000007],ans[1000007];
struct Node{
ll t,x,y;
bool operator <(const Node b)const{
if(x!=b.x) return x>b.x;//x小在前
return t<b.t;//t大在前
}
};
priority_queue<Node> pq;
struct segment_tree_beats{
ll minn,se_minn;
ll min_cnt;
ll hist_sum,sum;
ll min_tag,hist_add_tag;
}tr[4000007];
inline ll ls(ll p){return p<<1;}
inline ll rs(ll p){return p<<1|1;}
void push_up(ll p){
tr[p].hist_sum=tr[ls(p)].hist_sum+tr[rs(p)].hist_sum;
tr[p].sum=tr[ls(p)].sum+tr[rs(p)].sum;
if(tr[ls(p)].minn==tr[rs(p)].minn){
tr[p].minn=tr[ls(p)].minn;
tr[p].se_minn=min(tr[ls(p)].se_minn,tr[rs(p)].se_minn);
tr[p].min_cnt=tr[ls(p)].min_cnt+tr[rs(p)].min_cnt;
}
else if(tr[ls(p)].minn<tr[rs(p)].minn){
tr[p].minn=tr[ls(p)].minn;
tr[p].se_minn=min(tr[ls(p)].se_minn,tr[rs(p)].minn);
tr[p].min_cnt=tr[ls(p)].min_cnt;
}
else{
tr[p].minn=tr[rs(p)].minn;
tr[p].se_minn=min(tr[rs(p)].se_minn,tr[ls(p)].minn);
tr[p].min_cnt=tr[rs(p)].min_cnt;
}
return;
}
void butr(ll p,ll l,ll r){
tr[p].hist_sum=0;
tr[p].sum=0;
tr[p].min_tag=0;
tr[p].hist_add_tag=0;
if(l==r){
tr[p].min_cnt=1;
tr[p].minn=0;
tr[p].se_minn=LLONG_MAX;
return;
}
ll mid=(l+r)>>1;
butr(ls(p),l,mid);
butr(rs(p),mid+1,r);
push_up(p);
return;
}
void update_node(ll p,ll min_add,ll hist_add){
tr[p].hist_sum+=hist_add*tr[p].min_cnt;
tr[p].sum+=min_add*tr[p].min_cnt;
tr[p].minn+=min_add;
tr[p].min_tag+=min_add;
tr[p].hist_add_tag+=hist_add;
}
void push_down(ll p){
ll old_minn=min(tr[ls(p)].minn,tr[rs(p)].minn);
if(old_minn==tr[ls(p)].minn){
update_node(ls(p),tr[p].min_tag,tr[p].hist_add_tag);
}
if(old_minn==tr[rs(p)].minn){
update_node(rs(p),tr[p].min_tag,tr[p].hist_add_tag);
}
tr[p].min_tag=0;
tr[p].hist_add_tag=0;
}
void max_update(ll ul,ll ur,ll p,ll l,ll r,ll k,ll base){
if(k<=tr[p].minn) return;
if(k<tr[p].se_minn&&ul<=l&&ur>=r){
update_node(p,k-tr[p].minn,(k-tr[p].minn)*base);
return;
}
push_down(p);
ll mid=(l+r)>>1;
if(ul<=mid) max_update(ul,ur,ls(p),l,mid,k,base);
if(ur>mid) max_update(ul,ur,rs(p),mid+1,r,k,base);
push_up(p);
return;
}
ll hist_qry(ll ql,ll qr,ll p,ll l,ll r){
if(ql<=l&&qr>=r){
return tr[p].hist_sum;
}
push_down(p);
ll res=0,mid=(l+r)>>1;
if(ql<=mid) res+=hist_qry(ql,qr,ls(p),l,mid);
if(qr>mid) res+=hist_qry(ql,qr,rs(p),mid+1,r);
return res;
}
ll sum_qry(ll ql,ll qr,ll p,ll l,ll r){
if(ql<=l&&qr>=r){
return tr[p].sum;
}
push_down(p);
ll res=0,mid=(l+r)>>1;
if(ql<=mid) res+=sum_qry(ql,qr,ls(p),l,mid);
if(qr>mid) res+=sum_qry(ql,qr,rs(p),mid+1,r);
return res;
}
ll min_qry(ll ql,ll qr,ll p,ll l,ll r){
if(ql<=l&&qr>=r){
return tr[p].minn;
}
push_down(p);
ll minn=LLONG_MAX,mid=(l+r)>>1;
if(ql<=mid) minn=min(minn,min_qry(ql,qr,ls(p),l,mid));
if(qr>mid) minn=min(minn,min_qry(ql,qr,rs(p),mid+1,r));
return minn;
}
void init(){
for(int i=1;i<=n;i++){
last[i]=m+1;
}
butr(1,1,m);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
Node a;
cin>>a.x>>a.y;
a.t=i;
pq.push(a);
}
init();
ll last_x=-1;
stack<Node> stk;
while(!pq.empty()){
Node v=pq.top();
pq.pop();
if(last_x!=v.x){
while(!stk.empty()){
Node u=stk.top();
stk.pop();
ans[u.t]=sum_qry(1,u.t,1,1,m)*(u.x+1)+hist_qry(1,u.t,1,1,m);
}
}
max_update(v.t,last[v.x]-1,1,1,m,v.y,-v.x);
last[v.x]=v.t;
stk.push(v);
last_x=v.x;
}
while(!stk.empty()){
Node u=stk.top();
stk.pop();
ans[u.t]=sum_qry(1,u.t,1,1,m)*(u.x+1)+hist_qry(1,u.t,1,1,m);
}
for(int i=1;i<=m;i++){
cout<<ans[i]<<'\n';
}
return 0;
}
```