n.
边反向后就相当于 能从1和n走到i.
为了方便叙述,把1~n叫做x坐标,1~(m+1)叫做y坐标.
然后我们将图上下翻转(y坐标)后,能从1走到i的话一定经过i−1条向右的边,且这些边的y坐标不下降.
那么我们设fl[i]表示从1走到i最小加边数量,那么有fl[i]=i−1−LIS这里的LIS是x坐标在1~(i−1)的边的y坐标形成的最长不下降子序列长度.
这个东西可以O(nlogn)预处理出来,同时我们反着处理一遍向左的边就能处理出从n走到i的最小加边数量fr[i].
最终答案一定是一段连续的区间[i,j].因为如果两个满足答案的位置不相邻,体现在边的y坐标序列上就是两座山峰,中间的值也一定可以形成山峰.如下图
假设两座山峰为L,R.那么对于在[L,R]中的点,如果在M左边就取①上的点,如果在M右边就取②上的点,这样也一定能够形成总长为n的山峰.
所以说要求的就是区间[i,j]满足fr[i]+fl[j]<=k的最长区间长度.
由于fr[i]递减,fl[i]递增,那么枚举i增加的时候,为了让区间长度尽量大,j也一定不会变小.那么就开个变量存一下当前j的位置然后往后面挪动就行了.O(n)
总时间复杂度O(nlogn).
注意这道题要减去原本就能够被1,n都到达的跑道的数量.
#include<bits/stdc++.h>
using namespace std;
char cb[1<<15],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)
template<class T>inline void read(T &res) {
char ch; int flg = 1; for(;!isdigit(ch=getc());)if(ch=='-')flg=-flg;
for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0'); res*=flg;
}
const int MAXN = 100005;
int n, m, p, k, T[MAXN], fl[MAXN], fr[MAXN];
vector<pair<int,int> >el[MAXN], er[MAXN];
inline void chkmax(int &x, int y) { if(y > x) x = y; };
inline void upd(int x, int val) {
while(x <= m) chkmax(T[x], val), x += x&-x;
}
inline int qsum(int x) { int re = 0;
while(x) chkmax(re, T[x]), x -= x&-x;
return re;
}
int main() {
read(n), read(m), read(p), read(k); ++m;
for(int i = 1, x, y, z; i <= p; ++i) {
read(x), read(y), read(z); y = m-y;
if(z) el[x+1].push_back(make_pair(y, 0));
else er[x].push_back(make_pair(y, 0));
}
int LIS = 0;
for(int i = 2; i <= n; ++i) {
for(int j = 0, siz = el[i].size(); j < siz; ++j)
chkmax(LIS, el[i][j].second = qsum(el[i][j].first) + 1);
fl[i] = i - 1 - LIS;
for(int j = 0, siz = el[i].size(); j < siz; ++j)
upd(el[i][j].first, el[i][j].second);
}
for(int i = 1; i <= m; ++i) T[i] = 0;
LIS = 0;
for(int i = n-1; i >= 1; --i) {
for(int j = 0, siz = er[i].size(); j < siz; ++j)
chkmax(LIS, er[i][j].second = qsum(er[i][j].first) + 1);
fr[i] = n - i - LIS;
for(int j = 0, siz = er[i].size(); j < siz; ++j)
upd(er[i][j].first, er[i][j].second);
}
int j = 1, ans = 0, cnt = 0;
for(int i = 1; i <= n; ++i) {
while(j <= n && fr[i] + fl[j] <= k) ++j;
chkmax(ans, j - i);
if(!fl[i] && !fr[i]) ++cnt;
}
printf("%d
", ans-cnt);
}