CF1045G AI robots

题目大意就不说了

这道题可以用CDQ分治做

但是,如何选择CDQ分治的维度一直是CDQ分治的难点所在

这道题我们有三种选择

1.让智商高的数智商低的

2.让看的近的数看的远的

3.让靠右的数靠左的

但是,1和3都不好满足让这两个机器人分别都能看到的要求(因为不保证所以的机器人的视野范围相同)

所以我们以其视野范围当做第一维(从大到小排序)

之后我们发现对于左边\(i\)

右边满足其智商限制的一定是一个区间,之后这个区间我们可以用双指针维护

之后将这个区间里的数加入权值树状数组查询

另外由于至于范围很大

我们要离散化,但是离散化\(a_i-r_i\)和\(a_i+r_i\)也应当离散化

所以数组开三倍,之前因为这个RE了

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cctype>

using namespace std;

const int N = 5e5 + 3;

struct node{

    int xi;

    int ri;

    int qi;

}a[N];

int b[N];

int n,k;

long long ans;

struct BIT{

    int c[N << 1];

    inline void ins(int x,int v){for(;x <= b[0];x += x & -x) c[x] += v;}

    inline int query(int x){

        int res = 0;

        for(;x;x -= x & -x) res += c[x];

        return res;

    }

}T;

inline bool cmp1(node x,node y){

    if(x.ri != y.ri) return x.ri > y.ri;

    if(x.qi != y.qi) return x.qi < y.qi;

    return x.xi < y.xi;

}

inline bool cmp2(node x,node y){

    if(x.qi != y.qi) return x.qi < y.qi;

    return x.xi < y.xi;

}

inline int read(){

    int v = 0,c = 1;char ch = getchar();

    while(!isdigit(ch)){

        if(ch == '-') c = -1;

        ch = getchar();

    }

    while(isdigit(ch)){

        v = v * 10 + ch - 48;

        ch = getchar();

    }

    return v * c;

}

inline void solve(int l,int r){

    if(l == r) return ;

    int mid = (l + r) >> 1;

    solve(l,mid);solve(mid + 1,r);

    sort(a + l,a + mid + 1,cmp2);sort(a + mid + 1,a + r + 1,cmp2);

    int L = l,R = l - 1;

    for(int i = mid + 1;i <= r;++i){

        while(R + 1 <= mid && a[R + 1].qi <= a[i].qi + k) T.ins(a[R + 1].xi,1),R++;

        while(L <= mid && a[L].qi < a[i].qi - k) T.ins(a[L].xi,-1),L++;

        int from = lower_bound(b + 1,b + b[0] + 1,b[a[i].xi] - a[i].ri) - b;

        int to = lower_bound(b + 1,b + b[0] + 1,b[a[i].xi] + a[i].ri) - b;

        ans += T.query(to) - T.query(from - 1);

    }

    for(int i = L;i <= R;++i) T.ins(a[i].xi,-1);

}

int main(){

    n = read(),k = read();

    for(int i = 1;i <= n;++i){

        a[i].xi = read();

        a[i].ri = read();

        a[i].qi = read();

        b[++b[0]] = a[i].xi - a[i].ri;

        b[++b[0]] = a[i].xi + a[i].ri;

        b[++b[0]] = a[i].xi;

    }

    sort(b + 1,b + b[0] + 1);

    b[0] = unique(b + 1,b + b[0] + 1) - b - 1;

    for(int i = 1;i <= n;++i) a[i].xi = lower_bound(b + 1,b + b[0] + 1,a[i].xi) - b;

    sort(a + 1,a + n + 1,cmp1);

    solve(1,n);

    printf("%I64d\n",ans);

    return 0;

}

巴特西

CF1045G AI robots

CF1045G AI robots

最新文章

热门文章