[DS记录]P5069 [Ynoi2015] 纵使日薄西山
command_block
2021-07-02 16:42:59
**题意** ： 对于序列 $A$ ，不断进行如下操作 ：
选择 $A$ 中最靠左的最大值 $A_x$ ，将 $A_{x-1},A_x,A_{x+1}$ 都减去一，然后将小于 $0$ 的元素置为 $0$。
记 $S(A)$ 为：整个序列变为 $0$ 之前进行的操作数。
维护一个长为 $n$ 的序列 $A$ ，支持单点修改，查询 $S(A)$ 的值。
$n,q\leq 10^5$ ，时限$\texttt{1s}$。
------------
先不考虑修改，思考如何求出 $S(A)$。
观察 ： 若我们操作了 $A_{x-1},A_x,A_{x+1}$ ，之后总有 $A_x>A_{x-1},A_x\geq A_{x+1}$ ，故不会再以 $x-1,x+1$ 为中心进行操作。
其他可能的操作均不再会影响 $A_x$ 的值，故 $A_x$ 必须要使用 $A_x$ 次操作。
不妨将过程等价地改为 ： 每次选出最靠左的最大值 $A_x$，将 $A_{x-1},A_x,A_{x+1}$ 变为 $0$ ，次数加上 $A_x$。
于是答案就是所有被操作的位置的和。
进一步观察，对于单调不增的序列，被操作的下标是所有奇数。
对于一般的序列，我们将其看成若干段单调序列。
对于“山峰”，必然有贡献。
对于“山坡”上的点，下标奇偶性与对应“山峰”相同的位置有贡献。
对于“山谷”，必须奇偶性与相邻的两个山峰都相同才有贡献。
用树状数组分别维护奇下标与偶下标的部分和。用 `std::set` 维护山峰和山谷。
复杂度 $O(n\log n)$。
本题对时间常数的要求较为宽松，可以适当简化代码。
```cpp
#include<algorithm>
#include<cstdio>
#include<set>
#define ll long long
#define MaxN 100500
using namespace std;
int n;
#define lbit(p) (p&-p)
struct SumDS
{
ll t[MaxN];
void add(int p,int c)
{while(p<=n){t[p]+=c;p+=lbit(p);}}
ll qry(int p){
ll ret=0;
while(p){ret+=t[p];p^=lbit(p);}
return ret;
}
}T[2];
set<int> s;ll ans;
int a[MaxN],fl[MaxN];
int chk(int p)
{
if (fl[p]==1)return a[p];
if (p<1||p>n||fl[p]!=2)return 0;
int pre=*(--s.lower_bound(p))
,nxt=*s.upper_bound(p);
if (fl[pre]==1&&(p&1)!=(pre&1))return 0;
if (fl[nxt]==1&&(p&1)!=(nxt&1))return 0;
return a[p];
}
ll calc(int l,int r)
{
int sav=-1;
if (fl[l]==1&&fl[r]==2)sav=l&1;
if (fl[l]==2&&fl[r]==1)sav=r&1;
return sav==-1 ? 0 : T[sav].qry(r-1)-T[sav].qry(l);
}
int calc2(int l,int p,int r)
{
if (fl[l]==1&&fl[r]==2)return (l&1)==(p&1) ? a[p] : 0;
if (fl[l]==2&&fl[r]==1)return (r&1)==(p&1) ? a[p] : 0;
return 0;
}
void add(int p)
{
int pre=*(--s.lower_bound(p))
,nxt=*s.upper_bound(p);
if (fl[p]){
ans-=calc(pre,nxt)+chk(pre)+chk(nxt);
s.insert(p);
ans+=calc(pre,p)+calc(p,nxt)+chk(p)+chk(pre)+chk(nxt);
}else {
T[p&1].add(p,a[p]);
ans+=calc2(pre,p,nxt);
}
}
void del(int p)
{
int pre=*(--s.lower_bound(p))
,nxt=*s.upper_bound(p);
if (fl[p]){
ans-=calc(pre,p)+calc(p,nxt)+chk(p)+chk(pre)+chk(nxt);
s.erase(p);
ans+=calc(pre,nxt)+chk(pre)+chk(nxt);
}else {
T[p&1].add(p,-a[p]);
ans-=calc2(pre,p,nxt);
}
}
int gfl(int p)
{
if (a[p]>a[p-1]&&a[p]>=a[p+1])return 1;
if (a[p]<=a[p-1]&&a[p]<a[p+1])return 2;
return 0;
}
int m;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)scanf("%d",&a[i]);
fl[0]=fl[n+1]=2;
s.insert(0);s.insert(n+1);
for (int i=1;i<=n;i++)
{fl[i]=gfl(i);add(i);}
scanf("%d",&m);
for (int i=1,p,x;i<=m;i++){
scanf("%d%d",&p,&x);
if (1<=p-1)del(p-1);
del(p);
if (p+1<=n)del(p+1);
a[p]=x;
if (1<=p-1){fl[p-1]=gfl(p-1);add(p-1);}
fl[p]=gfl(p);add(p);
if (p+1<=n){fl[p+1]=gfl(p+1);add(p+1);}
printf("%lld\n",ans);
}return 0;
}
```