自动搬运

查看原文

来自洛谷，原作者为

	Find_Yourself 竹杖芒鞋轻胜马，谁怕？一蓑烟雨任平生。

搬运于2025-08-24 21:49:15，当前版本为作者最后更新于2023-10-14 18:42:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

树状数组优化 DP。

显然，如果 $i$ 能到 $1$，那么 $j(1\le j<i)$ 也能到 $1$；

同理，如果 $i$ 能到 $n$，那么 $j(i<j\le n)$ 也能到 $n$。

定义 $l_i$ 表示从 $i$ 到 $1$ 至少要加多少条边，$r_i$ 表示从 $i$ 到 $n$ 至少要加多少条边。

答案为 $\left[\max\limits_{i=1}^{n}\max\limits_{j=1}^{n}[r_j\le k-l_i]i-j+1\right]-\sum\limits_{i=1}^{n}[l_i=r_i=0]$。用一个指针维护就可以了。

考虑将 $l,r$ 分开求。

我们从上到下，从左到右枚举每一条边，转移方程为 $l_i=\min\limits_{j=1}^{i-1}(l_j+i-j-1)$。将贡献拆一下，用树状数组维护 $(l_i-i)$ 的前缀最小值，每次算完后更新树状数组即可。$r_i$ 同理。

复杂度 $O(n\log n)$。注意初始值等细节。

code:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int n,len,m,k,ta,tb,c[N],f[N],g[N];
struct node{int x,h;node(int x=0,int h=0):x(x),h(h){}}a[N],b[N];
inline bool cmp(node x,node y){return x.h==y.h?x.x<y.x:x.h>y.h;}
inline bool cmp2(node x,node y){return x.h==y.h?x.x>y.x:x.h>y.h;}
inline int lbt(int x){return x&(-x);}
inline void upd(int i,int v){for(;i<=n;i+=lbt(i))c[i]=min(c[i],v);}
inline int get(int i){int res=1e9;for(;i;i-=lbt(i))res=min(res,c[i]);return res;}
int main(){
  cin>>n>>len>>m>>k;
  for(int i=1;i<=m;++i){
    int x=read(),w=read(),d=read();++w;
    if(!d)a[++ta]=node(x,w);
    else b[++tb]=node(x+1,w);
  }
  sort(a+1,a+ta+1,cmp2);sort(b+1,b+tb+1,cmp);
  memset(c,-1,sizeof(c));
  for(int i=1;i<=n;++i)f[i]=i-1;
  for(int i=1;i<=tb;++i){
    int x=b[i].x;
    f[x]=get(x-1)+x-1;
    upd(x,f[x]-x);
  }
  for(int i=1;i<=n;++i)f[i]=min(f[i],get(i-1)+i);
  memset(c,-1,sizeof(c));
  for(int i=1;i<=n;++i)g[i]=n-i;
  for(int i=1;i<=ta;++i){
    int x=n-a[i].x+1;
    g[a[i].x]=get(x-1)+x-1;
    upd(x,g[a[i].x]-x);
  }
  for(int i=1;i<=n;++i)g[i]=min(g[i],get(n-i)+n-i+1);
  int tmp=0;
  for(int i=1;i<=n;++i){
    if(!f[i]&&!g[i]){
      ++tmp;
    }
  }
  int cur=1,ans=0;
  for(int i=1;i<=n;++i){
    int t=k-f[i];
    while(cur<=n&&g[cur]>t)++cur;
    ans=max(ans,i-cur+1-tmp);
  }
  cout<<ans<<endl;
  return 0;
}