题解：AT_abc405_f [ABC405F] Chord Crossing

· · 题解

模拟赛题，经典套路，断环成链。

两条弦有交当且仅当其对应区间有交且无包含关系。

具体地，对于弦 (l,r)，与其相交的弦应该满足 (l_i < l \wedge l \le r_i \le r)\lor (l \le l_i \le r \wedge r>r_i)。

满足的条件是互斥的，算两次。

第一次将弦按照 l 升序排序做二维数点，第二次同理。

时间复杂度 \Theta(n\log n)。

#include <bits/stdc++.h>
#define umap unordered_map
#define vint vector<int>
#define ll long long
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ull unsigned long long
#define uint unsigned int
#define rg register
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define sqr(x) ((x)*(x))
using namespace std;
const int INF=0x3f3f3f3f;
inline int read(){
    int w=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        w=(w<<1)+(w<<3)+(ch^48);
        ch=getchar();
    }
    return w*f;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

const int N=2e6+10;
int n,m,q,ans[N];
struct node{
    int l,r,id;
}a[N],b[N];
bool cmp1(node a,node b){
    return a.l<b.l;
}
bool cmp2(node a,node b){
    return a.r>b.r;
}
struct bit{
    int tr[N];
    int lowbit(int x){
        return x&-x;
    }
    void add(int x,int k){
        for(;x<=2*n;x+=lowbit(x)) tr[x]+=k;
    }
    int query(int x){
        int res=0;
        for(;x>0;x-=lowbit(x)) res+=tr[x];
        return res;
    }
    int query(int l,int r){
        return query(r)-query(l-1);
    }
}t;
int main(){
    #ifndef ONLINE_JUDGE
    //freopen("in.txt","r",stdin);
    #endif
    cin>>n>>m;
    rep(i,1,m){
        auto &[l,r,id]=a[i];
        l=read(),r=read();
    }
    cin>>q;
    rep(i,1,q){
        auto &[l,r,id]=b[i];
        l=read(),r=read(),id=i;
    }
    sort(a+1,a+m+1,cmp1),sort(b+1,b+q+1,cmp1);
    int p=0;
    for(int i=1;i<=q;++i){
        auto [l,r,id]=b[i];
        while(p+1<=m&&a[p+1].l<l) ++p,t.add(a[p].r,1);
        ans[id]+=t.query(l,r);
    }
    memset(t.tr,0,sizeof t.tr);
    sort(a+1,a+m+1,cmp2),sort(b+1,b+q+1,cmp2);
    p=0;
    for(int i=1;i<=q;++i){
        auto [l,r,id]=b[i];
        while(p+1<=m&&a[p+1].r>r) ++p,t.add(a[p].l,1);
        ans[id]+=t.query(l,r);
    }
    rep(i,1,q) cout<<ans[i]<<"\n";
    #ifndef ONLINE_JUDGE
    fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
    #endif
    return 0;
}