ZOJ 4008.Yet Another Tree Query Problem（问题模型转化+线段树离线处理）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#define ls l,mid,rt<<1
#define rs mid+1,r,rt<<1|1
#define endl ‘\n‘
#define p4 puts("444")
const int MAXN = 1e6+10;
const double EPS = 1e-12;

int n,q;
int ans[MAXN],sum[MAXN];
struct node{
    int l,r,sx,id;
}a[MAXN];

bool cmp(node aa,node bb){
    if(aa.r!=bb.r)return aa.r<bb.r;
    else return aa.sx<bb.sx;
}

void Build(int l,int r,int rt){
    if(l==r){
        sum[rt]=0;
        return ;
    }
    int mid=(l+r)/2;
    Build(ls);
    Build(rs);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

void Update(int l,int r,int rt,int pos){
    if(pos==l&&l==r){
        sum[rt]++;
        return ;
    }
    int mid=(l+r)/2;
    if(pos<=mid)Update(ls,pos);
    else Update(rs,pos);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

int Query(int l,int r,int rt,int pos){
    if(pos==0)return 0;
    if(pos>=r)return sum[rt];
    int mid=(l+r)/2,ans=0;
    ans+=Query(ls,pos);
    if(pos>mid)ans+=Query(rs,pos);
    return ans;
}

void solve(){
    scanf("%d %d",&n,&q);
    Build(1,n,1);
    for(int i=1;i<n+q;i++){
        scanf("%d %d",&a[i].l,&a[i].r);
        if(a[i].l>a[i].r)swap(a[i].l,a[i].r);
        a[i].id=i;
        if(i<n)a[i].sx=0;
        else a[i].sx=1;
    }
    sort(a+1,a+n+q,cmp);
    int now=0;
    for(int i=1;i<n+q;i++){
        if(!a[i].sx){
            now++;
            Update(1,n,1,a[i].l);
        }
        else {
            ans[a[i].id]=(a[i].r-a[i].l+1)-(now-Query(1,n,1,a[i].l-1));
            //cout<<" ### "<<now<<" "<<Query(1,n,1,a[i].l-1)<<endl;
        }
    }
    for(int i=n;i<n+q;i++)printf("%d\n",ans[i]);
}

int main()
{
    int T=1;
    scanf("%d",&T);
    while(T--) solve();
}