题解：AT_abc405_f [ABC405F] Chord Crossing

2012_Zhang_ · 2025-05-14 17:46:25 · 题解

思路解析

首先我们需要知道我们要求什么，我们不妨转化题意，
我们要求的就是对于每个 C_i,D_i，找出一个点在区间 [C_i,D_i]，另一个点在区间 [1,C_i] 或 [D_i,n] 的线的数量。
我们设 qry(l,x,y) 左端点在区间 [1,l] 右端点在 [x,y] 的线的数量。
我们就可以把答案拆成

这样我们可以使用树状数组，并且维护每个询问的左端点单调性以求出每个答案。

代码奉上

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5e6;
int a[maxn],b[maxn],c[maxn],n,m,q,res[maxn],tot;
struct lines{int a,b;}line[maxn];
struct asks{int l,x,y,tp,id;}qry[maxn];
bool cmp(lines a,lines b){return a.a<b.a;}
bool cmp2(asks a,asks b){return a.l<b.l;}
int lb(int x){return x&-x;}
void add(int x){for(int i=x;i<=n;i+=lb(i)) c[i]++;}
int ask(int x){
    int ans=0;
    for(int i=x;i>0;i-=lb(i)) ans+=c[i];
    return ans;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>line[i].a>>line[i].b;
    sort(line+1,line+m+1,cmp);
    n*=2;
    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>a[i]>>b[i];
        qry[++tot].l=b[i],qry[tot].x=b[i],qry[tot].y=n;
        qry[tot].tp=1,qry[tot].id=i;
        qry[++tot].l=a[i],qry[tot].x=b[i],qry[tot].y=n;
        qry[tot].tp=-1,qry[tot].id=i;
        qry[++tot].l=a[i],qry[tot].x=a[i],qry[tot].y=b[i];
        qry[tot].tp=1,qry[tot].id=i;
    }
    sort(qry+1,qry+tot+1,cmp2);
    int id=1;
    for(int i=1;i<=tot;i++){
        while(line[id].a<=qry[i].l&&id<=m){add(line[id].b); id++;}
        res[qry[i].id]+=qry[i].tp*(ask(qry[i].y)-ask(qry[i].x-1));
    }
    for(int i=1;i<=q;i++) cout<<res[i]<<endl;
}