题解：AT_abc106_d [ABC106D] AtCoder Express 2

· · 题解

大致题意：给定 Q 个询问点对 (x,y) ，求给定的 m 个点对 (l_i,r_i) 中有多少个满足 l_i \geq x 且 r_i \leq y 。

很显然的一个二维偏序问题，考虑二维数点。值得注意的是这里找的应是以 (x,y) 为左上角端点，一直向右扩展的矩形，所以从右向左做扫描线，树状数组维护竖着的一维就好了。

复杂度是 O((n+m) \log n) 的，本题不算特别优秀，但思路是值得借鉴和推广的。

参考代码如下：

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define INF 1e10
#define eb emplace_back
#define pb push_back
#define ls (u<<1)
#define rs ((u<<1)|1)
#define lowbit(x) (x&(-x))
#define pii pair<int,int> 
#define fi first
#define se second
using namespace std;
const int maxn=505;
const int maxm=2e5+5;
const int mod=1e9+7;
int n,m,Q,ans[maxm];
struct node{
    int l,r;
    friend bool operator<(node x,node y){
        return x.l<y.l;
    }
}a[maxm];
struct ques{
    int y,id,op;
};
vector<ques> q[maxn];
struct BIT{
    int c[maxn];
    void add(int x,int k){
        while(x<=501){
            c[x]+=k;
            x+=lowbit(x);
        }
    }
    int qry(int x){
        int ans=0;
        while(x){
            ans+=c[x];
            x-=lowbit(x);
        }
        return ans;
    }
}bit;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>Q;
    for (int i=1;i<=m;i++){
        cin>>a[i].l>>a[i].r;
    }
    sort(a+1,a+1+m);
    for (int x,y,i=1;i<=Q;i++){
        cin>>x>>y;
        q[501].eb((ques){y,i,-1});
        q[x].eb((ques){y,i,1});
    }
    int lst=m;
    for (int i=501;i;i--){
        while(a[lst].l>=i){
            bit.add(a[lst].r,1);
            lst--;
        }
        for (int j=0;j<q[i].size();j++){
            int y=q[i][j].y,op=q[i][j].op,id=q[i][j].id;
            ans[id]+=bit.qry(y)*op;
        }
    }
    for (int i=1;i<=Q;i++){
        cout<<ans[i]<<"\n";
    }
    return 0;
}