P5044 [IOI2018] meetings 会议 思考--zhengjun

在 NFLS 模拟赛上遇到的，赛后订正过的。

隔了蛮长时间的，总结一下。

• 首先转化为笛卡尔树上后缀前缀的问题。

• 然后考虑如何转移，发现转移形如 \(f(x)=\min\{f(x)+C,kx+b\}\) 的形式。

• 可以直接线段树维护每个点的最优直线，在 update 的时候：

  • 如果 \(f(x)+C\le kx+b\) 恒成立（左右两端点成立即可），区间加
  • 如果 \(f(x)+C\ge kx+b\) 恒成立，区间覆盖
  • 否则递归左右子树

  因为最后修改的位置一定是一段区间，所以复杂度为 \(O(\log n)\)。

代码

#include<bits/stdc++.h>
using namespace std;using ll=long long;const int N=7.5e5+10,K=__lg(N)+2,M=N<<2;const ll INF=1e18;
int n,m,a[N],f[K][N];ll ans[N];struct ops{int l,r,id;};vector<ops>o[N];
struct SegTree{
	ll f[M],g[M],laz[M],tag[M],K[M],B[M];
	void pushup(int rt){f[rt]=f[rt<<1];g[rt]=g[rt<<1|1];}
	void pushadd(int rt,ll x){laz[rt]+=x;f[rt]+=x;g[rt]+=x;}
	void pushcov(int rt,int l,int r,ll k,ll b){laz[rt]=0;tag[rt]=1;K[rt]=k;B[rt]=b;f[rt]=l*k+b;g[rt]=r*k+b;}
	void pushdown(int rt,int l,int mid,int r){
		if(tag[rt])pushcov(rt<<1,l,mid,K[rt],B[rt]),pushcov(rt<<1|1,mid+1,r,K[rt],B[rt]),tag[rt]=0;
		if(laz[rt])pushadd(rt<<1,laz[rt]),pushadd(rt<<1|1,laz[rt]),laz[rt]=0;
	}
	void build(int l=1,int r=n,int rt=1){
		f[rt]=g[rt]=INF;if(l==r)return;int mid=(l+r)>>1;build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);
	}
	void update(int L,int R,ll k,ll b,ll x,int l=1,int r=n,int rt=1){
		if(L<=l&&r<=R){
			if(f[rt]+x>=k*l+b&&g[rt]+x>=k*r+b)return pushcov(rt,l,r,k,b);
			if(f[rt]+x<=k*l+b&&g[rt]+x<=k*r+b)return pushadd(rt,x);
		}int mid=(l+r)>>1;pushdown(rt,l,mid,r);
		if(L<=mid)update(L,R,k,b,x,l,mid,rt<<1);if(mid<R)update(L,R,k,b,x,mid+1,r,rt<<1|1);pushup(rt);
	}
	ll query(int x,int l=1,int r=n,int rt=1){
		if(l==r)return f[rt];int mid=(l+r)>>1;pushdown(rt,l,mid,r);
		return x<=mid?query(x,l,mid,rt<<1):query(x,mid+1,r,rt<<1|1);
	}
}A,B;
int Max(int x,int y){return a[x]>a[y]?x:y;}
int find(int l,int r){int k=__lg(r-l+1);return Max(f[k][l],f[k][r-(1<<k)+1]);}
void dfs(int l,int r){
	if(l>r)return;int u=find(l,r);dfs(l,u-1);dfs(u+1,r);
	for(ops x:o[u]){int l=x.l,r=x.r,id=x.id;
		ans[id]=(r-l+1ll)*a[u];
		if(l<u)ans[id]=min(ans[id],B.query(l)+(r-u+1ll)*a[u]);
		if(r>u)ans[id]=min(ans[id],A.query(r)+(u-l+1ll)*a[u]);
	}ll x=0,y=0;if(l<u)x=B.query(l);if(r>u)y=A.query(r);
	A.update(u,r,a[u],x-(u-1ll)*a[u],(u-l+1ll)*a[u]);
	B.update(l,u,-a[u],y+(u+1ll)*a[u],(r-u+1ll)*a[u]);
}
int main(){
	scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]),f[0][i]=i;
	for(int i=1;(1<<i)<=n;i++)for(int j=1;j+(1<<i)-1<=n;j++)f[i][j]=Max(f[i-1][j],f[i-1][j+(1<<i-1)]);
	for(int i=1,l,r;i<=m;i++)scanf("%d%d",&l,&r),l++,r++,o[find(l,r)].push_back({l,r,i});
	A.build();B.build();dfs(1,n);for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);return 0;
}