二维平面数点

目录
  • CDQ分治
    • BZOJ1935 园丁的烦恼
    • BZOJ1176 Mokia
    • Distance(2019年牛客多校第八场D题+CDQ+树状数组)
  • 线段树
    • PUBG 1V3 CSUST2015
      • 题意
      • 思路
      • 代码
    • Popping Balloons(2019年牛客多校第十场F题)
      • 题意
      • 思路
      • 代码
    • Rikka with Cake(2019年杭电多校02)
      • 题意
      • 思路
      • 代码

最近经常遇到二维平面统计点的个数，稍微写个总结。

CDQ分治

BZOJ1935 园丁的烦恼

题目传送门

题解地址：

BZOJ1176 Mokia

题目传送门

题目链接：

Distance(2019年牛客多校第八场D题+CDQ+树状数组)

题解链接：

线段树

PUBG 1V3 CSUST2015

题目传送门

题意

故事是以吃鸡为背景的，总共有\(n\)个人，总共有\(m\)个队伍，每个人属于某一个队伍，每个队伍最多\(4\)个人。

每个人的攻击范围是一个\(|x-x_i|\leq d_i,|y-y_i|\leq d_i\)的正方形，现在告诉你每个人的坐标和攻击范围\(d_i\)，及其所属的队伍编号。

现在有\(q\)次查询，每次给你一个队伍编号，问你这个队伍内攻击范围内敌人数最多的那个人对应攻击范围内的敌人数量。

思路

我的写法比较暴力，貌似比标程慢了很多。

我的写法是用线段树维护每个\(y\)上的人数，然后加点照常加，统计每个人攻击范围内的人时把他拆成\(x_i-d_i-1\)和\(x_i+d_i\)，在\(x_i-d_i-1\)处减去\([y_i-d_i,y_i+d_i]\)内的人数，然后在\(x_i+d_i\)处加上这个范围的人数，就得到了横坐标在\([x_i-d_i,x_i+d_i]\)且纵坐标在\([y_i-d_i,y_i+d_i]\)内的人数，对于同一个队伍里面的人就暴力去重即可。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
typedef pair pLL;
typedef pair pLi;
typedef pair pil;;
typedef pair pii;
typedef unsigned long long uLL;

#define lson (rt<<1)
#define rson (rt<<1|1)
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
}

void update(int rt, int pos) {
    if(segtree[rt].l == segtree[rt].r) {
        ++segtree[rt].sum;
        return;
    }
    int mid = (segtree[rt].l + segtree[rt].r) >> 1;
    if(pos <= mid) update(lson, pos);
    else update(rson, pos);
    push_up(rt);
}

int query(int rt, int l, int r) {
    if(segtree[rt].l == l && segtree[rt].r == r) {
        return segtree[rt].sum;
    }
    int mid = (segtree[rt].l + segtree[rt].r) >> 1;
    if(r <= mid) return query(lson, l, r);
    else if(l > mid) return query(rson, l, r);
    else return query(lson, l, mid) + query(rson, mid + 1, r);
}

inline LL read() {
    int x=0,f=1;char ch=getchar();
    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;
}

int main() {
#ifndef ONLINE_JUDGE
    FIN;
#endif
    n = read(), m = read();
    for(int i = 1; i <= n; ++i) {
        x[i] = read(), y[i] = read(), d[i] = read(), belong[i] = read();
        vec[belong[i]][++all[belong[i]]] = i;
        num[++cnt] = y[i];
        num[++cnt] = y[i] + d[i];
        num[++cnt] = y[i] - d[i];
        pp[i] = {x[i], y[i]};
    }
    sort(num + 1, num + cnt + 1);
    cnt = unique(num + 1, num + cnt + 1) - num - 1;
    sort(pp + 1, pp + n + 1);
    build(1, 1, cnt);
    for(int i = 1; i <= n; ++i) {
        pp[i].y = getid(pp[i].y);
        a[++tot].type = 1, a[tot].x = x[i] - d[i] - 1, a[tot].id = i, a[tot].d = d[i], a[tot].pos = y[i];
        a[++tot].type = 2, a[tot].x = x[i] + d[i], a[tot].id = i, a[tot].d = d[i], a[tot].pos = y[i];
    }
    sort(a + 1, a + tot + 1);
    for(int i = 1; i <= tot; ++i) {
        vis[i][0] = getid(a[i].pos-a[i].d);
        vis[i][1] = getid(a[i].pos+a[i].d);
    }
    int las = 1;
    for(int i = 1; i <= tot; ++i) {
        while(las <= n && pp[las].x <= a[i].x) {
            update(1, pp[las].y);
            ++las;
        }
        if(a[i].type == 1) ans[a[i].id] -= query(1, vis[i][0], vis[i][1]);
        else ans[a[i].id] += query(1, vis[i][0], vis[i][1]);
    }
    for(int i = 1; i <= n; ++i) {
        int be = belong[i];
        for(int j = 1; j <= all[be]; ++j) {
            if(x[vec[be][j]] >= x[i] - d[i] && x[vec[be][j]] <= x[i] + d[i] && y[vec[be][j]] >= y[i] - d[i] && y[vec[be][j]] <= y[i] + d[i]) --ans[i];
        }
        fin[belong[i]] = max(fin[belong[i]], ans[i]);
    }
    q = read();
    while(q--) {
        team = read();
        printf("%d\n", fin[team]);
    }
    return 0;
}

Popping Balloons(2019年牛客多校第十场F题)

题目传送门

题意

在二维平面内有\(n\)个气球，玩家可以选择三条横线(相邻两条的距离恰好为\(r\))三条竖线(距离也为\(r\))，问你最多能打破多少个气球。

思路

我们用线段树来维护选择最下面的那个\(y\)时能打破的气球数量，然后枚举最左边的\(x\)来统计答案，在统计答案时我们先把这个\(x,x+r,x+2*r\)上的点全部去掉(去重)，然后查询最大的\(y\)是多少加上这三条竖线上的点数即可。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
 
typedef long long LL;
typedef pair pLL;
typedef pair pLi;
typedef pair pil;;
typedef pair pii;
typedef unsigned long long uLL;
 
#define lson (rt<<1)
#define rson (rt<<1|1)
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["< vec[maxn];
 
struct node {
    int l, r, mx;
}segtree[maxn<<2];
 
void build(int rt, int l, int r) {
    segtree[rt].l = l, segtree[rt].r = r;
    segtree[rt].mx = 0;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
}
 
void update(int rt, int pos, int val) {
    if(segtree[rt].l == segtree[rt].r) {
        segtree[rt].mx += val;
        return;
    }
    int mid = (segtree[rt].l + segtree[rt].r) >> 1;
    if(pos <= mid) update(lson, pos, val);
    else update(rson, pos, val);
    segtree[rt].mx = max(segtree[lson].mx, segtree[rson].mx);
}
 
int main() {
#ifndef ONLINE_JUDGE
    FIN;
#endif
    scanf("%d%d", &n, &r);
    build(1, 0, 100000);
    for(int i = 1; i <= n; ++i) {
        scanf("%d%d", &x, &y);
        vec[x].emplace_back(y);
        if(x - r >= 0) vec[x-r].emplace_back(y);
        if(x - 2 * r >= 0) vec[x-2*r].emplace_back(y);
        update(1, y, 1);
        if(y - r >= 0) update(1, y - r, 1);
        if(y - 2 * r >= 0) update(1, y - 2 * r, 1);
    }
    int ans = 0;
    for(int i = 0; i <= 100000; ++i) {
        for(int j = 0; j < (int)vec[i].size(); ++j) {
            update(1, vec[i][j], -1);
            if(vec[i][j] - r >= 0) update(1, vec[i][j] - r, -1);
            if(vec[i][j] - 2 * r >= 0) update(1, vec[i][j] - 2 * r, -1);
        }
        ans = max(ans, (int)vec[i].size() + segtree[1].mx);
        for(int j = 0; j < (int)vec[i].size(); ++j) {
            update(1, vec[i][j], 1);
            if(vec[i][j] - r >= 0) update(1, vec[i][j] - r, 1);
            if(vec[i][j] - 2 * r >= 0) update(1, vec[i][j] - 2 * r, 1);
        }
    }
    printf("%d\n", ans);
    return 0;
}

Rikka with Cake(2019年杭电多校02)

题目传送门

题意

在\(n\times m\)的平面内有\(k\)条射线，问你这些射线把这个平面分成了多少块。

思路

答案是交点数\(+1\)。

写法和上面两题差不多，按照\(x\)排序，线段树维护\(y\)。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
typedef pair pLL;
typedef pair pLi;
typedef pair pil;;
typedef pair pii;
typedef unsigned long long uLL;

#define lson (rt<<1)
#define rson (rt<<1|1)
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
}

void update(int rt, int pos, int val) {
    if(segtree[rt].l == segtree[rt].r) {
        segtree[rt].sum += val;
        segtree[rt].lazy += val;
        return;
    }
    push_down(rt);
    int mid = (segtree[rt].l + segtree[rt].r) >> 1;
    if(pos <= mid) update(lson, pos, val);
    else update(rson, pos, val);
    push_up(rt);
}

int query(int rt, int l, int r) {
    if(segtree[rt].l == l && segtree[rt].r == r) return segtree[rt].sum;
    push_down(rt);
    int mid = (segtree[rt].l + segtree[rt].r) >> 1;
    if(r <= mid) return query(lson, l, r);
    else if(l > mid) return query(rson, l, r);
    else return query(lson, l, mid) + query(rson, mid + 1, r);
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d%d", &n, &m, &q);
        cnt = tot = 0;
        num[++tot] = -1, num[++tot] = 0, num[++tot] = m, num[++tot] = m + 1;
        for(int i = 1; i <= q; ++i) {
            scanf("%d%d%s", &x[i], &y[i], op[i]);
            num[++tot] = y[i];
            num[++tot] = y[i] + 1;
            num[++tot] = y[i] - 1;
        }
        sort(num + 1, num + tot + 1);
        tot = unique(num + 1, num + tot + 1) - num - 1;
        build(1, 1, tot);
        for(int i = 1; i <= q; ++i) {
            if(op[i][0] == 'L') {
                ask[++cnt] = {1, 0, y[i], 0};
                ask[++cnt] = {2, x[i] + 1, y[i], 0};
            } else if(op[i][0] == 'R') {
                ask[++cnt] = {1, x[i], y[i], 0};
                ask[++cnt] = {2, n + 1, y[i], 0};
            } else if(op[i][0] == 'U') {
                ask[++cnt] = {3, x[i], y[i], m};
            } else {
                ask[++cnt] = {3, x[i], 0, y[i]};
            }
        }
        sort(ask + 1, ask + cnt + 1);
        LL ans = 1;
        for(int i = 1; i <= cnt; ++i) {
            if(ask[i].type == 1) update(1, getid(ask[i].y), 1);
            else if(ask[i].type == 2) update(1, getid(ask[i].y), -1);
            else {
                ans += query(1, getid(ask[i].y), getid(ask[i].yy));
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}
迷之线段树迷之CDQ

相关

标签