CodeForces 1045G (G)

动态开点线段树。
首先以机器人的看见距离排序，那么如果遍历到i，那么i前面的机器人，如果i能看见他，反过来他也能看见i。
我们再利用机器人的智商建立权值线段树。每颗线段树中维护+-k范围内能有的机器人数量。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<bitset>
#include<map>
//#include<regex>
#include<cstdio>
#pragma GCC optimize(2)
#define up(i,a,b)  for(int i=a;i<b;i++)
#define dw(i,a,b)  for(int i=a;i>b;i--)
#define upd(i,a,b) for(int i=a;i<=b;i++)
#define dwd(i,a,b) for(int i=a;i>=b;i--)
//#define local
typedef long long ll;
typedef unsigned long long ull;
const double esp = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int inf = 1e9;
using namespace std;
ll read()
{
    char ch = getchar(); ll x = 0, f = 1;
    while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
typedef pair<int, int> pir;
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lrt root<<1
#define rrt root<<1|1
const int N = 1e5 + 10;
int n, k;
int lisan[N];
struct node {
    int xi, ri, qi;
    bool operator<(const node a)const
    {
        return ri > a.ri;
    }
}rob[N];
vector<int>vec;
int sz;
int tree[N * 40];
int lc[N * 40], rc[N * 40];
int root[42 * N];
int cnt = 0;
int newnode()
{
    return ++cnt;
}
int findpos(int num)
{
    return lower_bound(vec.begin(), vec.end(), num) - vec.begin();
}
void update(int &o, int l, int r, int pos)
{
    if (!o)o = newnode();
    int mid = (l + r) >> 1;
    tree[o]++;
    if (l == r)return;
    if (pos <= mid)update(lc[o], l, mid, pos);
    else update(rc[o], mid + 1, r, pos);
}
int query(int o, int l, int r, int lf, int rt)
{
    if (!o)return 0;
    if (lf <= l && r <= rt)
    {
        return tree[o];
    }
    int mid = (l + r) >> 1;
    int sum = 0;
    if (lf <= mid)sum += query(lc[o], l, mid, lf, rt);
    if (rt > mid)sum += query(rc[o], mid + 1, r, lf, rt);
    return sum;
}
int main()
{
    n = read(), k = read();
    up(i, 0, n) {
        rob[i].xi = read(), rob[i].ri = read(), rob[i].qi = read();
        upd(j, max(rob[i].qi - k, 0), min((int)1e9, rob[i].qi + k))vec.push_back(j);
    }
    sort(rob, rob + n);
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    sz = vec.size();
    ll ans = 0;
    //up(i, 0, n)cout << rob[i].xi << endl;
    up(i, 0, n)
    {
        upd(j, max(rob[i].qi - k, 0), min(rob[i].qi + k, (int)1e9))
        {
            ans += query(root[findpos(j)], 0, 1e9, max(rob[i].xi - rob[i].ri, 0), min(rob[i].xi + rob[i].ri, (int)1e9));
        }
        update(root[findpos(rob[i].qi)], 0, 1e9, rob[i].xi);
    }
    cout << ans << endl;
}

CodeForces 1045G (G)

原文：https://www.cnblogs.com/LORDXX/p/12454407.html