【HAOI2011】problem a

又看题解了，这样下去要跪啊QAQ

原题：

一次考试共有n个人参加，第i个人说：“有ai个人分数比我高，bi个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数)

1≤n≤100000   0≤ai、bi≤n

想不出来做法，就去看题解了

首先这个题意很有问题，"有ai个人分数比我高"是严格的，有人这么说说明他的排名区间在l=bi+1到r=n-ai之间，且l到r这个区间中所有人的成绩都是一样的

然后有个问题就是如果供词区间在l到r中的人不够r-l+1怎么办？根据鸽巢原理应该可以证明，这样的情况一定会有人说谎，说谎的人填补整下的即可

那么完全相同的区间就可以合并，权值为供词为这个区间的人数，然后求一个线段中不相交的区间覆盖

因为n很大，所以可以用邻接表，先以r第一优先级l第二优先级排序，然后按排好的序扫一下边，如果l[i]和l[i+1]，r[i]和r[i+1]完全相同就不加入链表中，给上一个加入的边权值++，否则链表中插入一条权值为1的边

（其实有更好的实现方式，这个不难想（不是用map= =

最后dp，f[r]=max{f[l-1]+e[i].v} <- 区间覆盖DP

又看题解了，这样下去要跪啊QAQ

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int rd(){int z=0,mk=1;  char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')mk=-1;  ch=getchar();}
    while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0';  ch=getchar();}
    return z*mk;
}
struct dcd{int x,y;}a[110000];
struct ddd{int nxt,y,v;}e[110000];  int lk[110000],ltp=0;
inline void ist(int x,int y,int z){  e[++ltp].nxt=lk[x],lk[x]=ltp,e[ltp].y=y,e[ltp].v=z;}
int n;
int f[110000];
bool cmp(dcd x,dcd y){  return (x.y==y.y)?(x.x<y.x):x.y<y.y;}
int main(){//freopen("ddd.in","r",stdin);
    cin>>n;
    for(int i=1;i<=n;++i){
        a[i].x=rd()+1,a[i].y=n-rd();
        //if(a[i].x==a[i].y){  cout<<a[i].x<<endl;}
    }
    sort(a+1,a+n+1,cmp);
    int bwl;
    for(int i=1;i<=n;++i){
        bwl=1;
        while(a[i+1].x==a[i].x && a[i+1].y==a[i].y)  ++bwl,++i;
        ist(a[i].y,a[i].x-1,min(bwl,a[i].y-a[i].x+1));
    }
    for(int i=1;i<=n;++i){
        f[i]=f[i-1];
        for(int j=lk[i];j;j=e[j].nxt)  f[i]=max(f[i],f[e[j].y]+e[j].v);
    }
    cout<<n-f[n]<<endl;
    return 0;
}