LOJ

分析

我们把每个套娃看做一个点 $(R_i,H_i)$，把套在一起的若干个套娃看做一条链，把每条链 $H$ 最大的那个套娃称作这条链的头。

这样子问题就变为，每个点可以向右上方某一个点连边，求最小链数。

先考虑只有一组询问的情况。

我们把所有物品按 $H$ 从小到大排序，然后依次加入。对于每个物品，显然选择能选择的最右的链头连上最优。于是我们只需要找到左边第一个链头即可。

考虑处理询问。可以将链头的权值设为 $1$，其它点权值设为 $0$，容易发现此时答案即为满足条件的点的权值和。将询问离线按 $H$ 的限制排序，用一个支持单点修改、区间求和、查询左边第一个权值不为 $0$ 的点的数据结构维护即可。代码中写的是二分+树状数组。

实现时可以把 $R$ 作为第二关键字从大到小排序来避免 $H$ 相同的点间的影响。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,Q,ans[N],S[N<<1],c=0;
struct node { int r,h; } a[N];
bool operator <(node a,node b) { return a.h!=b.h?a.h<b.h:a.r>b.r; }
struct query { int a,b,id; } q[N];
bool operator <(query a,query b) { return a.b<b.b; }

int s[N<<1];
void add(int x,int w) { for (;x<=c;x+=x&-x) s[x]+=w; }
int qsum(int x) { int w=0; for (;x;x-=x&-x) w+=s[x]; return w; }
int findpos(int p) {
    if (!p||!qsum(p)) return 0;
    int L=1,R=p;
    while (L<R) {
        int mid=(L+R+1)>>1;
        if (qsum(p)-qsum(mid-1)) L=mid;
        else R=mid-1;
    }
    return L;
}

int main() {
    n=read(),Q=read();
    for (int i=1;i<=n;++i) a[i]=(node){read(),read()};
    for (int i=1;i<=Q;++i) q[i]=(query){read(),read(),i};
    for (int i=1;i<=n;++i) S[++c]=a[i].r;
    for (int i=1;i<=Q;++i) S[++c]=q[i].a;
    sort(S+1,S+c+1); c=unique(S+1,S+c+1)-S-1;
    for (int i=1;i<=n;++i) a[i].r=lower_bound(S+1,S+c+1,a[i].r)-S;
    for (int i=1;i<=Q;++i) q[i].a=lower_bound(S+1,S+c+1,q[i].a)-S;
    sort(a+1,a+n+1); sort(q+1,q+Q+1);
    for (int i=1,j=1;i<=Q;++i) {
        while (j<=n&&a[j].h<=q[i].b) {
            int p=findpos(a[j].r-1);
//          printf("%d %d %d\n",S[a[j].r],a[j].h,S[p]);
            if (p) add(p,-1);
            add(a[j].r,1);
            ++j;
        }
        ans[q[i].id]=qsum(c)-qsum(q[i].a-1);
    }
    for (int i=1;i<=Q;++i) printf("%d\n",ans[i]);
    return 0;
}