@Jerusalem
2016-02-14T20:18:41.000000Z
字数 1689
阅读 1322
显然,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;
}