codeforces 1046_problem_A AI robots (cdq分治)

墨蓝 2022-05-10 03:28 156阅读 0赞

[传送门][Link 1]

题意：给n个机器人，机器人都有自己的位置x，可见范围r，智商q，问两个机器人互相可见，并且智商相差不多于k的对数有多少。

思路：运用分治思想，第一维对于r非递减排序，分治，考虑对于左半部分的每一个机器人，右半部分有多少个和它配对的，因为r及从小到大排序，所以只要左能看见右，右就一定能看到左，

第二维对q排序，然后用树状数组维护x，对于q要保证是和枚举的左边的那个机器人智商保持在k的范围之内。

#include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+10;
    typedef long long ll;
    int k;
    int val[N], cnt;
    ll ans=0;
    
    struct Robot{
        int x, r, q;
        int L, R;
    }p[N], fz[N];
    
    bool cmp1(Robot a, Robot b){
        return a.r<b.r;
    }
    
    ll s[N];
    
    void upd(int x, int v){
        for(;x<N; x+=x&-x){
            s[x]+=v;
        }
    }
    
    ll query(int x){
        ll ret=0;
        for(; x>0; x-=x&-x){
            ret+=s[x];
        }
        return ret;
    }
    
    bool cmp2(Robot a, Robot b){
        return a.q<b.q;
    }
    
    void cdq(int l, int r){
    
        if(l==r) return;
        int mid=(l+r)>>1;
        cdq(l, mid); cdq(mid+1, r);
        int p1, p2;
        p1=p2=mid+1;
        for(int i=l; i<=mid; i++){
    
            while(p2<=r && p[p2].q<=p[i].q+k){
                upd(p[p2].x, 1);
                p2++;
            }
    
            while(p1<p2 && p[p1].q<p[i].q-k){
                upd(p[p1].x, -1);
    
                p1++;
            }
            ans+=query(p[i].R)-query(p[i].L-1);
        }
        for(int i=p1; i<p2; i++) upd(p[i].x, -1);
        inplace_merge(p+l, p+mid+1, p+r+1, cmp2);
    
    }
    
    int main(){
        int n, x, r, q;
        scanf("%d%d", &n, &k);
    
        for(int i=1; i<=n; i++){
            scanf("%d%d%d", &p[i].x, &p[i].r, &p[i].q);
    
           val[++cnt]=p[i].x;
        }
    
        sort(val+1, val+1+cnt);
        cnt=unique(val+1, val+1+cnt)-val-1;
        for(int i=1; i<=n; i++){
    
            p[i].L=lower_bound(val+1, val+1+cnt, p[i].x-p[i].r)-val;
            p[i].R=upper_bound(val+1, val+1+cnt, p[i].x+p[i].r)-val-1;
            p[i].x=lower_bound(val+1, val+1+cnt, p[i].x)-val;
        }
    
        sort(p+1, p+1+n, cmp1);
    
    
        cdq(1, n);
    
        printf("%I64d\n", ans);
    
    
        return 0;
    }

[Link 1]: http://codeforces.com/contest/1046/problem/A