求助,AC#4,其余全WA,用的树状数组
查看原帖
求助,AC#4,其余全WA,用的树状数组
1155762
TCIC_4294967296楼主2024/7/12 09:47
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+5,A = 1e7+5;
#define int long long

int n,m,a[N],b[N],c[N],d[N],ans[N],tot;
struct pos{
    int x,y;
    bool operator<(pos p){
        return x<p.x;
    }
} ps[N];
struct quer{
    int x,y,p,c;
    bool operator<(quer q){
        return x<q.x;
    }
} q[N<<2];

int t[A];
int lowbit(int x){return 1<<__builtin_ctz(x);}
void add(int x,int v){for(;x<A;x+=lowbit(x)) t[x]+=v;}
int get(int x){int res=0; for(;x>0;x-=lowbit(x)) res+=t[x]; return res;}

signed main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>ps[i].x>>ps[i].y;
    for(int i=1;i<=m;i++) cin>>a[i]>>b[i]>>c[i]>>d[i];
    
    for(int i=1;i<=m;i++){
        q[++tot]={c[i],d[i],i,0};
        if(a[i]) q[++tot]={a[i]-1,d[i],i,1};
        if(b[i]) q[++tot]={c[i],b[i]-1,i,2};
        if(a[i]&&b[i]) q[++tot]={a[i]-1,b[i]-1,i,3};
    }
    sort(ps+1,ps+n+1);
    sort(q+1,q+(m<<2)+1);
    int j=0;
    for(int i=1;i<=n;i++){
        add(ps[i].y,1);
        if(ps[i].x!=ps[i+1].x){
            for(;q[j].x!=ps[i+1].x&&j<=tot;j++){
                int cnt=get(q[j].y);
                switch(q[j].c){
                    case 0:ans[q[j].p]+=cnt;break;
                    case 1:ans[q[j].p]-=cnt;break;
                    case 2:ans[q[j].p]-=cnt;break;
                    case 3:ans[q[j].p]+=cnt;break;
                }
            }
        }
    }
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<"\n";
    }
    return 0;
}
2024/7/12 09:47
加载中...