GYM101630A.Archery Tournament(动态开点线段树+时间分治)

题目链接:GYM101630A.Archery Tournament

题意:

有一个坐标轴,两种操作:

  1. x y:放置一个圆心在(x,y),半径为y的靶子。
  2. x y:射击该点,若射中靶子,则输出编号,并且取消靶子,否则输出-1。

题解:

动态开点线段树。

建一个线段树,每个节点用set维护,维护当前区间内完全覆盖的圆的编号,该线段树子节点与父节点不存在继承关系,对于每次查询,暴力遍历节点中所有的编号。

参考代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
int m;
int rt, tot = 0, ls[MAXN * 20], rs[MAXN * 20];
struct NODE
{
    ll x, y;
    NODE() {}
    NODE(int x, int y)
    {
        this->x = x, this->y = y;
    }
} a[MAXN];
set<int> s[MAXN * 20];
int sum = 0;
void update(ll L, ll R, int id, int f, ll l, ll r, int &rt)
{
    if (!rt)
        rt = ++tot;
    if (L <= l && r <= R)
    {
        if (f)
            s[rt].insert(id);
        else
            s[rt].erase(id);
        return;
    }
    int mid = (l + r) >> 1;
    if (L <= mid)
        update(L, R, id, f, l, mid, ls[rt]);
    if (R > mid)
        update(L, R, id, f, mid + 1, r, rs[rt]);
}
int ans;
void query(ll x, ll y, ll l, ll r, int rt)
{
    if (!rt)
        return;
    if (l <= x && x <= r)
    {
        for (auto now : s[rt])
        {
            if ((x - a[now].x) * (x - a[now].x) + (y - a[now].y) * (y - a[now].y) < a[now].y * a[now].y)
            {
                ans = now;
                return;
            }
        }
    }
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    if (x <= mid)
        query(x, y, l, mid, ls[rt]);
    if (x > mid)
        query(x, y, mid + 1, r, rs[rt]);
}
int main()
{
    scanf("%d", &m);
    rt = tot = 0;
    for (int ii = 1; ii <= m; ii++)
    {
        int op;
        ll x, y;
        scanf("%d%lld%lld", &op, &x, &y);
        a[ii] = NODE(x, y);
        if (op == 1)
        {
            update((x - y), (x + y), ii, 1, -1e9, 1e9, rt);
        }
        else
        {
            ans = -1;
            query(x, y, -1e9, 1e9, rt);
            printf("%d\n", ans);
            if (ans != -1)
                update((a[ans].x - a[ans].y), (a[ans].x + a[ans].y), ans, 0, -1e9, 1e9, rt);
        }
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。