题解：P13963 [ICPC 2023 Nanjing R] 接雨水
zhangjunyu_sixi · · 题解
Update
格式问题已更正，感谢管理员的指正。
前言
本篇题解注重于呈现本人从暴力到正解的思维过程，如果只想学习正解的话可直接跳过前半部分。
而为了帮助大家更好的看清这个过程，我自己大概测了一下本题划分的数据阶梯。
数据范围
本题共
对于
对于
对于
对于
时间限制
空间限制
（注：本题原题在 ICPC 赛制下不存在部分分，所以【数据范围】这部分是我自己用程序测试出来的，并不保证准确，仅仅方便教学而已）。
正文
解题过程
首先考虑把原公式拆开，发现可以把所有
接下来我们只需要看公式的前半部分即可，就是对于每个点将他的前缀最大值和后缀最大值中较小者作为贡献加入。
这里可以想到最天真的，不带任何优化的暴力，即每次修改完之后
代码实现
（非正解代码均只展示部分）。
cin >> n;
sumf=0;
for (int i = 1;i <= n;i++)
{
cin >> a[i];
sumf+=a[i];
}
cin >> q;
for (int tiat=1;tiat <= q;tiat++)
{
cin >> x >> v;
a[x]+=v;
sumf+=v;
long long ans=0;
for (int i = 1;i <= n;i++)
{
int maxn1=a[i],maxn2=a[i];
for (int j = i-1;j >= 1;j--)
{
maxn1=max(maxn1,a[j]);
}
for (int j = i+1;j <= n;j++)
{
maxn2=max(maxn2,a[j]);
}
ans+=min(maxn1,maxn2);
}
cout << ans-sumf << endl;
}这个显然有点过于暴力了，考虑进一步的优化。
经过浅浅的思考，发现在每次更新完
代码实现
f[1] = a[1];
for (int j = 2;j <= n;j++)
{
f[j] = max(f[j-1],a[j]);
}
g[n] = a[n];
for (int j = n-1;j >= 1;j--)
{
g[j] = max(g[j+1],a[j]);
}这个优化经实测无法直接获得比朴素暴力更高的分数，但这个让我们可以注意到一个性质，即前缀最大值这个数组单调不降，后缀最大值数组单调不增。
进一步思考可发现，对于每次单点修改可分为两种情况：
-
修改完之后没有成为任何一个点的新最大值，可以直接忽略。
-
修改完后可以顶替掉原来某些点的前后缀最大值。
（后续讨论均以修改前缀最大值为例，后缀最大值同理）。
对于第二种情况，由于前缀最大值序列单调不增，所以某些点也一定在序列上属于一段连续的区间。
那么对于每次修改操作的最大值序列维护，只需要将以被修改的点为左端点，其右边最后一个小于
到此我们可以将题目的要求转为两个操作：
-
选取一段符合条件的区间进行推平。
-
求出整个序列的和。
到这里可能一眼会想到用线段树维护两个序列，但考虑到用线段树好像还得套一层二分，还会添上一层
（好吧我承认我就是想写珂朵莉）。
这样我们每次修改后就先去对应的树上确定起始修改点的位置，然后也不需要二分，直接暴力扫到终止点所在的区间段，然后进行推平即可。
但紧接着又会面临一个问题，我们每次要加的是单个点的前后缀最大值中的较小值，而珂朵莉树只分别存了前后缀最大值序列，该怎么合并呢？
这里我想到过一个暴力写法，可以顺序遍历第一棵树（假设是后缀最大值），依次取出该树的颜色段作为询问区间去第二棵树上比较。
由于这样做在每次查询中询问的区间段的后缀最大值是一定的，所以对于第二棵树只需要与这个值进行比较，然后按照珂朵莉树正常的统计方式即可。
（一些注释写代码里了）。
代码实现
#include <bits/stdc++.h>
using namespace std;
#define IT set<node>::iterator
#define int long long
inline void read(long long &a)
{//省略
}
inline void write(long long x)
{//省略
}
struct node
{
int l,r;
mutable int v;
node(int L,int R=-1,int V=0):l(L),r(R),v(V){}
bool friend operator<(node a,node b)
{
return a.l < b.l;
}
};
set<node> tree;
set<node> tree2;
long long a[100005];
IT cut(int pos)
{
IT it=tree.lower_bound(node(pos));
if (it != tree.end() and it->l == pos)
{
return it;
}
it--;
int l=it->l,r=it->r,v=it->v;
tree.erase(it);
tree.insert(node(l,pos-1,v));
return tree.insert(node(pos,r,v)).first;
}
IT cut2(int pos)
{
//同cut，只不过针对tree2
}
IT xun(int pos)
{
IT it=tree.lower_bound(node(pos));
if (it != tree.end() and it->l == pos)
{
return it;
}
it--;
return it;
}
IT xun2(int pos)
{
//同xun，针对tree2
}
bool gai(int pos)
{
//基本同2，只是遍历顺序不一样，这里拿2演示
}
bool gai2(int pos)//维护前缀最大值序列
{
IT fz=xun2(pos);
//这里判断一下要不要修改，如果不需要就跳过了，不进行切割
//有对这种优化感兴趣的可以看我主页的一篇文章 （无耻推荐~~
if (fz->v > a[pos])
{
return 0;
}
IT it=cut2(pos);
IT fit=it;
while (it->v <= a[pos] and it != tree2.end())
//暴力扫就行，期望块数不是很多
{
it++;
}
it--;
int r=it->r;
it++;
tree2.erase(fit,it);
tree2.insert(node(pos,r,a[pos]));
return 1;
}
int cha(int l,int r,int v)//v是传入的比较值，即从tree中获取的最大值
{
IT itr=cut2(r+1),itl=cut2(l);
int sum=0;
for (;itl != itr;itl++)
{
sum+=min(itl->v,v)*(itl->r-itl->l+1);
}
return sum;
}
signed main()
{
long long T,n,q,x,v;
long long sumf=0;
read(T);
for (int chtholly=1;chtholly <= T;chtholly++)
{
//建树和读入先省略了，sumf是统计的所有a[i]的和
for (int i = 1;i <= q;i++)
{
read(x),read(v);
a[x]+=v;
sumf+=v;
lstans-=v;
bool flag1=gai(x);
bool flag2=gai2(x);
//这里做个优化，如果本次没触发任何修改直接输出上次答案即可
if (flag1 or flag2 or lstans < 0)
{
long long ans=0;
for (IT it = tree.begin();it != tree.end();it++)
{
ans+=cha(it->l,it->r,it->v);
}
ans-=sumf;
lstans=ans;
}
write(lstans);
putchar('\n');
}
}
return 0;
}上述做法可以成功通过 subtask2 的部分分（其实好像卡卡能卡到19号点，但这里不展开讲了），但面对后续的数据还是显得有些无能为力，但只看代码确实无法继续优化了，思考陷入僵局。。。
既然代码上卡住了，不妨再来推推性质。
我们最终答案要求的是这个柿子：