i可以作为起点说明把边反向后可以从1和n到达i。

设fl[i]表示从1到达i至少需要加几条边，fr[i]表示从n到达i至少需要加几条边。

把图上下翻转后，从左往右依次计算fl[i]，有fl[i]=i-1-左边LIS的长度，用树状数组维护即可$O(n\log n)$求出。

从右往左计算fr[i]同理。

然后需要求i,j(i<=j)，使得fr[i]+fl[j]<=k。

由于fl单调递增，fr单调递减，因此随着i不断右移，j也会不断右移，所以可以$O(n)$求出。

 

#include
     
      #define N 100010int n,m,p,k,i,j,x,y,z,bit[N],fl[N],fr[N],pre,ans,cnt;struct E{int v,f;E*nxt;}*gl[N],*gr[N],pool[N],*cur=pool,*e;inline void addl(int x,int y){e=cur++;e->v=y;e->nxt=gl[x];gl[x]=e;}inline void addr(int x,int y){e=cur++;e->v=y;e->nxt=gr[x];gr[x]=e;}inline void up(int&a,int b){if(a
      
       ='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}int main(){  read(n),read(m),read(p),read(k);m++;  while(p--){    read(x),read(y),read(z);y=m-y;    z?addl(x+1,y):addr(x,y);  }  for(i=2;i<=n;i++){    for(e=gl[i];e;e=e->nxt)up(pre,e->f=ask(e->v)+1);    for(e=gl[i];e;e=e->nxt)add(e->v,e->f);    fl[i]=i-1-pre;  }  for(pre=0,i=1;i<=m;i++)bit[i]=0;  for(i=n-1;i;i--){    for(e=gr[i];e;e=e->nxt)up(pre,e->f=ask(e->v)+1);    for(e=gr[i];e;e=e->nxt)add(e->v,e->f);    fr[i]=n-i-pre;  }  for(i=j=1;i<=n;i++){    while(j<=n&&fr[i]+fl[j]<=k)j++;    up(ans,j-i);    if(!fl[i]&&!fr[i])cnt++;  }  return printf("%d",ans-cnt),0;}