专栏文章

题解：P11368 [Ynoi2024] After god

hhongyuecheng
P11368题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@minkij61
此快照首次捕获于
2025/12/02 03:54
3 个月前
此快照最后确认于
2025/12/02 03:54
3 个月前
查看原文

P11368 [Ynoi2024] After god 题解

前言

这是道好题。前置知识点： 线段树3

题意

对一个初始状态全为 00 的序列维护一个前缀最大值，有 nn 次修改，每次修改完查询一个区间历史和。

解题思路

样例
这个是题目给出的样例，从下往上第 ii 行对应进行第 ii 次操作后的 aa 序列（如红框代表第 11 次修改完后的 aa 序列）。其中标红数字的是每次的修改。
前缀最大值
上面这幅图从下往上第 ii 行对应进行第 ii 次操作后的前缀最大值序列。有颜色部分代表 aa 序列，其中蓝色代表每次修改。
每次修改的影响
我们发现每次修改，只会影响发生修改的位置及其之后的位置。（红框内为修改后影响前缀最大值的范围）
扫描线
我们现在横过来（横过来处理的原因之后会说明），对序列轴进行扫描。 将修改优先按 xx 从小到大排序，再按 tt（修改的时间，即这是第几次修改）从大到小排序。然后用线段树进行区间 max 操作维护。最后询问区间历史和（历史和是什么与如何维护后面会讲）。
以第一行为例。
示例1
先处理 tt 最大的这个 22，这里我们记第 ii 行上一次处理的位置为 lastilast_i(初始都为 m+1m+1)，那么我们对区间 [t,lasti−1][t,last_i-1]（即 [6,6][6,6]）进行区间 max 操作，然后 last1last_1 变为 66。
示例2
再处理 44,此时 t=4t=4、last1=6last_1=6，就对 [4,5][4,5] 区间进行区间 max 操作。 再把 last1last_1 修改为 44。
然后以此类推处理其他修改。每一行处理完后对于这一行的第 jj 个修改，记录答案为 [1,tj][1,t_j] 的历史和。

为什么维护时间维

可能有人会有疑问：为什么我们不直接维护序列，而要横向维护时间轴，对序列维扫描线？
原因是这样的，当对一个位置 xix_i 修改时，若其在此前不为零，则我们需先抹除其对后面的影响，再修改。而区间取 max 无法回退，就会导致错误。
举个例子。（其中标蓝为修改，标黑为前缀最大值）
特殊的例子
从下向上看，我们发现在第 33 次修改时，无法单纯通过前一层得到。而横向扫描就不会出现这种问题。

区间历史和如何维护

记第 ii 次操作后第 jj 个位置上的值为 ai,ja_{i,j}，那么经过 kk 次操作后，第 jj 个位置上的历史和可以表示为如下。
hj=∑i=1kai,jh_j=\sum_{i=1}^{k}a_{i,j}
而区间 [l,r][l,r] 的区间历史和可以表示为如下。
histl,r=∑j=lrhj=∑j=lr∑i=1kai,jhist_{l,r}=\sum_{j=l}^{r}h_j=\sum_{j=l}^{r}\sum_{i=1}^{k}a_{i,j}
假设我们在 ii 时刻，对长为 lenlen 的区间加了 xix_i，那么在 tt 时刻查询时这次修改对这段区间历史和的贡献就为 (t−i+1)×xi×len(t-i+1)\times x_i\times len。
展开后得到：
hi=(t+1)×xi×len+(xi×i)×lenh_i=(t+1)\times x_i\times len+(x_i\times i)\times len
tt 时刻这段所有操作区间历史和为：
histt=∑i=1k[(t+1)×xi×len+(xi×i)×len]hist_t=\sum_{i=1}^k [(t+1)\times x_i\times len+(x_i\times i)\times len] histt=(t+1)×∑i=1k(xi×len)+∑i=1k(xi×i×len)hist_t=(t+1)\times \sum_{i=1}^k (x_i\times len)+ \sum_{i=1}^k (x_i\times i\times len)
而查询时我们知道 tt 的值，于是我们线段树就维护 xix_i 和 xi×ix_i\times i 的区间和就行了。
其实区间取 max 也可以看为区间加，原因就不细讲了。

代码实现

注意：我的代码中 hist_sumhist\_sum 存的不是历史和，而是 xi×ix_i\times i。
CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...