Vol6

BZOJ1107

显然，i能作为出发点的充分必要条件是它能够到达左右端点。

引入辅助函数f(i)，表示i作为出发点到达左端点至少需要新建多少条路。将所有向左的道路按高度排序，以编号为关键字求LIS，然后f(i)就等于i-1-{max:n[i]

然后，能够到达左右端点的点一定是连续的，这是显然的。于是我们枚举这区间的左右端点，容易证明，区间[l,r]里的点都能够作为出发点的充分必要条件是f(r)+g(l)<=k。(注意到f和g无关，于是必要性是显然的，而注意到任意i

注意题目要求减掉不需要加边就可作为出发点的点数量。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=100005,INF=0x3f3f3f3f;
struct Node{
    int high;
    int Num;
    Node(){
        high=Num=0;
    }
    Node(int high_,int num_){
        high=high_;
        Num=num_;
    }
    bool operator <(const Node& a)const{
        if(high==a.high)
            return Num<a.Num; 
        return high>a.high;
    }
};
Node l[maxn],r[maxn];
int g[maxn];
int lt[maxn],rt[maxn];
int nl,nr;
int n,m,k,p;
void Clear()
{
    memset(g,0x3f,sizeof(g));
    g[0]=0;
}
int Find(int key,int size)
{
    int l=0,r=size;
    while(l+1<r){
        int mid=(l+r)/2;
        if(g[mid]<key)
            l=mid;
        else
            r=mid;
    }
    return l;
}
void First()
{
    Clear();
    for(int i=1;i<=nl;i++){
        int calc=Find(l[i].Num,nl)+1;
        g[calc]=min(g[calc],l[i].Num);
    }
    for(int i=0;i<=nl&&g[i]<n;i++)
        for(int j=g[i]+1;j<=g[i+1]&&j<=n;j++)
            lt[j]=j-i-1;
    Clear();
    for(int i=1;i<=nr;i++){
        int calc=Find(r[i].Num,nr)+1;
        g[calc]=min(g[calc],r[i].Num);
    }
    for(int i=0;i<=nr&&g[i]<n;i++)
        for(int j=g[i]+1;j<=g[i+1]&&j<=n;j++)
            rt[n-j+1]=j-i-1;
}
void Solve()
{
    int ans=0;
    //for(int i=1;i<=n;i++)
    //  printf("%d %d\n",rt[i],lt[i]);
    for(int i=1,j=1;i<=n;i++){
        while(j<=i&&rt[j]+lt[i]>k)
            j++; 
        ans=max(ans,i-j+1);
    }
    for(int i=1;i<=n;i++)
        if(lt[i]==0&&rt[i]==0)
            ans--;
    printf("%d\n",ans);
}
void Readdata()
{
    freopen("loli.in","r",stdin);
    scanf("%d%d%d%d",&n,&m,&p,&k);
    for(int i=1;i<=p;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(c==1)
            l[++nl]=Node(b,a);
        else
            r[++nr]=Node(b,n-a);
    }
    sort(l+1,l+nl+1);
    sort(r+1,r+nr+1);
}
void Close()
{
    fclose(stdin);
    fclose(stdout);
}
int main()
{
    Readdata();
    First();
    Solve();
    Close();
    return 0;
}