题解 | E_牛客博客

闲话：最绷的一集，秒了前三题然后 CF 味道的 D 思路假了然后卡了，F 博弈论也没猜出来，赛后发现 E 是最喜欢的分块 ds 题，难度也不高，赛时可冲。

考虑到答案很简单就是 $\max(0,a_i-a_{i-1})$ 之和。所以首先差分，得到的数组记为 $b_i$ 。

问题变成区间 +1，区间 -1，维护 $\max(0,b_i)$ 之和。这坨猎奇东西显然寻常数据结构难以维护。

所以直接大力分块，核心思路是维护答案和每个块大于等于 $0$ 的 $b_i$ 数量。

具体地，记 $cnt_{id,j}$ 表示第 $id$ 块 $b_i=j$ 的个数， $py_{id}$ 表示第 $id$ 块整块操作了多少（也就是块内 $b_i$ 的实际值是 $b_i+py_{id}$ ）， $sum_{id}$ 表示第 $id$ 块 $b_i+py_{id}\geqslant 0$ 的个数。

这样答案维护是容易的。对于整块直接修改 $py_{id}$ ，散块直接在 $b_i$ 上修改。注意修改的同时要维护发生变动的答案 $ans$ 和 $cnt_{id,j}$ 以及 $sum_{id}$ 。具体见代码，很好理解。

注意到这里 $cnt_{id,j}$ 的主要目的是在修改的同时借此维护 $sum_{id}$ ，所以虽然值域非常巨大，但是我们要考虑到由于每次修改只会 +1 或者 -1，所以只有 $|b_i|\le q$ 的元素可能会在修改过程中越过 $0$ 从而影响 $sum_{id}$ ，因此 $cnt_{id,j}$ 中只要考虑 $|b_i|\le q$ 的元素即可。

最后一个提醒，注意开 ll。

code

自我感觉实现良好，代码比较短而且跑得很快。

#include <bits/stdc++.h>
//taskkill /f /im 未命名1.exe
#define ED cerr<<endl;
#define TS cerr<<"I AK IOI"<<endl;
#define cr(x) cerr<<x<<endl;
#define cr2(x,y) cerr<<x<<" "<<y<<endl;
#define cr3(x,y,z) cerr<<x<<" "<<y<<" "<<z<<endl;
#define cr4(x,y,z,w) cerr<<x<<" "<<y<<" "<<z<<" "<<w<<endl;
#define popcnt __builtin_popcount
#define all(s) s.begin(),s.end()
#define bstring basic_string
//#define add(x,y) (x+=y)%=mod
#define pii pair<int,int>
#define epb emplace_back
#define pb push_back
#define mk make_pair
#define ins insert
#define fi first
#define se second
#define ll long long
//#define ull unsigned long long
using namespace std;
const int N=1e5+5,B=405,INF=2e9,mod=1e9+7;
int t,n,q,sq;
ll a[N],ans=0;int bel[N],is[N],st[B],ed[B];
int cnt[B][N<<1],sum[B],py[B];

void brute(int l,int r,int x) {
	int id=bel[l];
	for(int i=l;i<=r;++i) {
		if(is[i]) --cnt[id][a[i]+N];
		if(a[i]+py[id]>=0) --sum[id];
		ans-=max(0ll,a[i]+py[id]),a[i]+=x,ans+=max(0ll,a[i]+py[id]);
		if(is[i]) ++cnt[id][a[i]+N];
		if(a[i]+py[id]>=0) ++sum[id];
	}
}

void upd(int l,int r,int x) {
	if(r<l) return;
	if(bel[l]==bel[r]) {
		brute(l,r,x);return;
	}
	for(int id=bel[l]+1;id<=bel[r]-1;++id) {
		if(x==1) ans+=sum[id],sum[id]+=cnt[id][N-py[id]-1];
		else sum[id]-=cnt[id][N-py[id]],ans-=sum[id];
		py[id]+=x;
	}
	brute(l,ed[bel[l]],x),brute(st[bel[r]],r,x);
}

int main()
{
	scanf("%d%d",&n,&q);sq=sqrt(n);
	for(int i=1;i<=n;++i) {
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n/sq;++i) {
		st[i]=(i-1)*sq+1;ed[i]=i*sq;
		if(i==n/sq) ed[i]=n;
		for(int j=st[i];j<=ed[i];++j) {
			bel[j]=i;
		}
	}
	for(int i=n;i>=1;--i) a[i]-=a[i-1];
	for(int i=1;i<=n;++i) {
		int id=bel[i];
		if(abs(a[i])<=q) is[i]=1,++cnt[id][a[i]+N];
		if(a[i]>=0) ++sum[id];
		ans+=max(0ll,a[i]);
	}
	int x,p;printf("%lld\n",ans);
	while(q--) {
		scanf("%d%d",&x,&p);
		upd(p-x+1,p,-1),upd(p+1,min(n,p+x),1);
		printf("%lld\n",ans);
	}
	return 0;
}