Description：

$n$ 条从南往北的道路，在某两条道路之间的某个位置有一条从东向西或从西向东的单向道路，现在最多可以增加 $k$ 条道路，问最多能有多少道路从起点能到达其他所有道路。

$1\leqslant n\leqslant 10^5$

Solution：

首先发现，如果某个位置能到 $1$ 和 $n$ ，那么所有位置就都能到达了，如果 $i$ 用了 $a$ 条边能到 $n$ ，那么 $i+1$ 也一定能到，向左同理，如果设 $lef[i]$ 表示添加 $i$ 条向左的边能满足 $[1,lef[i]]$ 的点都能到 $1$ ， $rig[i]$ 类似但方向相反，那么我们可以枚举向左的边建了多少个，可以发现最后满足条件的位置一定是一个区间，但是这种状态定义不是很好求解，既然是一个区间，那么我就保证区间右端点能到 $1$ ，左端点能到 $n$ 即可，设 $fl[i]$ 表示从 $i$ 到 $1$ 最少需要加几条边， $fr[i]$ 类似但方向相反，那么有 $fl[i]=i-1-LIS$ ，求 $LIS$ 可以用树状数组，注意同一个位置的要先处理较高的不然高的会把低的算进去，然后发现 $fl[i]$ 非严格单调递增， $fr[i]$ 非严格单调递减，于是用双指针求出满足 $fr[l]+fl[r]\leqslant k$ 的最长区间即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,p,k;

#define MAXN 100010

vector<int> el[MAXN],er[MAXN];

bool cmp(int a,int b){return a > b;}

int lowbit(int x){return x & (-x);}

int c[MAXN];

void add(int p,int x){for(int i = p;i <= m;i += lowbit(i))c[i] = max(c[i],x);return;}

int query(int p){int res = 0;for(int i = p;i >= 1;i -= lowbit(i))res = max(res,c[i]);return res;}

int fl[MAXN],fr[MAXN];

int main()

{

	scanf("%d%d%d%d",&n,&m,&p,&k);

	++m;

	int pos,hei,dir;

	for(int i = 1;i <= p;++i)

	{

		scanf("%d%d%d",&pos,&hei,&dir);

		hei = m - hei;

		if(dir == 0)er[pos].push_back(hei);

		else el[pos + 1].push_back(hei);

	}

	for(int i = 1;i <= n;++i)

	{

		sort(el[i].begin(),el[i].end(),cmp);

		sort(er[i].begin(),er[i].end(),cmp);

	}

	memset(fl,0,sizeof(fl));

	memset(fr,0,sizeof(fr));

	memset(c,0,sizeof(c));

	for(int w = 1;w <= n;++w)

	{

		for(vector<int>::iterator i = el[w].begin();i != el[w].end();++i)

		{

			int s = query(*i) + 1;

			fl[w] = max(fl[w],s);

			add(*i,s);

		}

		fl[w] = max(fl[w],fl[w - 1]);

	}

	for(int w = 1;w <= n;++w)fl[w] = w - 1 - fl[w];

	memset(c,0,sizeof(c));

	for(int w = n;w >= 1;--w)

	{

		for(vector<int>::iterator i = er[w].begin();i != er[w].end();++i)

		{

			int s = query(*i) + 1;

			fr[w] = max(fr[w],s);

			add(*i,s);

		}

		fr[w] = max(fr[w],fr[w + 1]);

	}

	for(int w = n;w >= 1;--w)fr[w] = n - w - fr[w];

	int cnt = 0;

	for(int i = 1;i <= n;++i)if(fl[i] == 0 && fr[i] == 0)++cnt;

	int ans = 0;

	for(int i = 1,j = 0;i <= n;++i)

	{

		while(j < n && fl[j + 1] + fr[i] <= k)++j;

		ans = max(ans,j - i + 1);

	}

	cout << ans - cnt << endl;

	return 0;

}