7.20套娃（tao）

套娃（tao）

input
7 3
9 5
3 7
10 6
5 10
2 6
10 10
4 1
10 5
3 5
3 9
output
0
1
2

sol：

把查询想象成(x1,y1)向(x2,y2)有边当且仅当(x1<x2,y1<y2)

有个性质就是：这张图的最小链覆盖=最长反链

反链就是满足(x1<x2,y1>y2) ,所以把点按照x排序后就是求最长下降子序列

然后扫描线扫过去，用树状数组维护一下最长下降子序列即可

#include <bits/stdc++.h>

using namespace std;

typedef int ll;

inline ll read()

{

    ll s=; bool f=; char ch=' ';

    while(!isdigit(ch)) {f|=(ch=='-'); ch=getchar();}

    while(isdigit(ch)) {s=(s<<)+(s<<)+(ch^); ch=getchar();}

    return (f)?(-s):(s);

}

#define R(x) x=read()

inline void write(ll x)

{

    if(x<) {putchar('-'); x=-x;}

    if(x<) {putchar(x+''); return;}

    write(x/); putchar((x%)+'');

}

#define W(x) write(x),putchar(' ')

#define Wl(x) write(x),putchar('\n')

const int N=;

int n,Q,c[N],ans[N];

struct Node

{

    int r,h,id;

    inline bool operator<(const Node &tmp)const

    {

        return r>tmp.r||(r==tmp.r&&h<tmp.h)||(r==tmp.r&&h==tmp.h&&id<tmp.id);

    }

}a[N<<];

struct BIT

{

    int S[N];

    #define lowbit(x) ((x)&(-x))

    inline void add(int x,int y)

    {

        for(;x<=n;x+=lowbit(x)) S[x]=max(S[x],y);

    }

    inline int Que(int x)

    {

        int ans=;

        for(;x;x-=lowbit(x)) ans=max(ans,S[x]);

        return ans;

    }

}T;

int main()

{

    freopen("tao.in","r",stdin);

    freopen("tao.out","w",stdout);

    int i;

    R(n); R(Q);

    for(i=;i<=n;i++)

    {

        R(a[i].r); R(a[i].h); a[i].id=; c[i]=a[i].h;

    }

    for(i=;i<=Q;i++)

    {

        R(a[n+i].r); R(a[n+i].h); a[n+i].id=i;

    }

    sort(c+,c+n+); *c=unique(c+,c+n+)-c-;

    sort(a+,a+n+Q+);

    for(i=;i<=n+Q;i++)

    {

        a[i].h=upper_bound(c+,c+*c+,a[i].h)-c-;

        if(a[i].id) ans[a[i].id]=T.Que(a[i].h);

        else T.add(a[i].h,T.Que(a[i].h)+);

    }

    for(i=;i<=Q;i++) Wl(ans[i]);

    return ;

}

/*

input

7 3

9 5

3 7

10 6

5 10

2 6

10 10

4 1

10 5

3 5

3 9

output

0

1

2

*/