AT_abc106_d [ABC106D] AtCoder Express 2 题解

· · 题解

分析

对于求满足 l \le i \le j \le r 的二元组 (i,j) 数量，很容易想到二分。我们先用二分求出对于所有的 (i,j)，满足 l \le i \le r 的区间。最终的答案就是在这个区间里面 l \le j \le r 的数量。

很显然，我们是无法二分 j 的，因为同一组 (i,j) 是有依赖性，也就是保序 i 后，j 是无法保序的。考虑使用其它方法维护答案。

对于求区间答案，不难想到莫队。对于指针的每次移动，我们可用一棵树状数组更新数量。而在指针移动完之后，该询问的答案就可以直接用树状数组求得 j \le r 的数量了。在这里，为了减小复杂度，我们可以对 (i,j) 合并一下相同项。这样的话在用树状数组更新数量时就可能不是 1，而是更新的 (i,j) 的出现次数。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define x first
#define y second
#define re register 
const int N=1e6+10,M=1e4+10;
int n,m,q;
struct node{
    int l,r,cnt;
}c[N],c1[N];
int cidx;
struct node2{
    int p,q;
}Q[N];
struct node3{
    int l,r,id,k;
}Q2[N];
int ANS[N],idx,len;
int tr[M];//树状数组 
inline bool cmp(node a,node b){
    return ((a.l!=b.l)?(a.l<b.l):(a.r<b.r));
}
inline bool cmp2(node3 a,node3 b){
    if(a.l/len!=b.l/len) return a.l<b.l;
    if((a.l/len)&1) return a.r<b.r;
    return a.r>b.r;
}
inline int find1(int l,int r,int x){
    int ans=0;
    while(l<=r){
        int mid=l+r>>1;
        if(c1[mid].l>=x) ans=mid,r=mid-1;
        else l=mid+1;
    }
    return ans;
}
inline int find2(int l,int r,int x){
    int ans=0;
    while(l<=r){
        int mid=l+r>>1;
        if(c1[mid].l<=x) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}
inline void insert(int x,int y){
    while(x<=n+10) tr[x]+=y,x+=x&(-x);
}
inline int query(int x){
    int ans=0;
    while(x) ans+=tr[x],x-=x&(-x);
    return ans;
}
inline void read(){
    scanf("%lld%lld%lld",&n,&m,&q);
    for(re int i=1;i<=m;++i)
        scanf("%lld%lld",&c[i].l,&c[i].r);
    for(re int i=1;i<=q;++i)
        scanf("%lld%lld",&Q[i].p,&Q[i].q);
    return ;
}
inline void solve(){
    sort(c+1,c+m+1,cmp);
    int last=1;
    for(re int i=2;i<=m+1;++i)//合并相同项 
        if(c[i].l!=c[i-1].l||c[i].r!=c[i-1].r) c1[++cidx]={c[i-1].l,c[i-1].r,last},last=1;
        else ++last;
    for(re int i=1;i<=q;++i){//二分查找i的区间 
        int where=find1(1,cidx,Q[i].p);
        int where2=find2(where,cidx,Q[i].q);
        if(where>where2||where<1||where2<1) ANS[i]=0;
        else Q2[++idx]={where,where2,i,Q[i].q};
    }
    len=sqrt(idx);
    sort(Q2+1,Q2+idx+1,cmp2);
    int l=1,r=0;
    for(re int i=1;i<=idx;++i){//莫队 
        while(l>Q2[i].l) --l,insert(c1[l].r,c1[l].cnt);
        while(r<Q2[i].r) ++r,insert(c1[r].r,c1[r].cnt);
        while(l<Q2[i].l) insert(c1[l].r,-c1[l].cnt),++l;
        while(r>Q2[i].r) insert(c1[r].r,-c1[r].cnt),--r;
        ANS[Q2[i].id]=query(Q2[i].k);
    }
    for(re int i=1;i<=q;++i)
        printf("%lld\n",ANS[i]);
    return ;
}
signed main(){
    read(),solve();return 0;
}