文档章节

二维平面数点

o
 osc_g8254g7s
发布于 2019/08/19 20:29
字数 2394
阅读 14
收藏 0

精选30+云产品,助力企业轻松上云!>>>

[toc]

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

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 <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> 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"=["<<x<<"]" <<endl
#define FIN freopen("/home/dillonh/CLionProjects/Dillonh/in.txt","r",stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0)

const double eps = 1e-8;
const int mod = 1000000007;
const int maxn = 1000000 + 7;
const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;

int n, m, cnt, tot, q, team;
int vec[maxn][5], all[maxn];
int ans[maxn], num[maxn*3], fin[maxn], vis[maxn*3][3];
int x[maxn], y[maxn], d[maxn], belong[maxn];

struct pp {
    int x, y;
    bool operator < (const pp& a) const {
        return x < a.x;
    }
}pp[maxn];

struct ask {
    int type, x, pos, id, d;
    bool operator < (const ask& a) const {
        return x < a.x;
    }
}a[maxn*3];

int getid(int x) {
    return lower_bound(num + 1, num + cnt + 1, x) - num;
}

struct node {
    int l, r, sum;
}segtree[maxn*12];

void push_up(int rt) {
    segtree[rt].sum = segtree[lson].sum + segtree[rson].sum;
}

void build(int rt, int l, int r) {
    segtree[rt].l = l, segtree[rt].r = r;
    segtree[rt].sum = 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) {
    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 <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
 
typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> 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"=["<<x<<"]" <<endl
#define FIN freopen("/home/dillonh/CLionProjects/Dillonh/in.txt","r",stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0)
 
const double eps = 1e-8;
const int mod = 1000000007;
const int maxn = 200000 + 7;
const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;
 
int n, r, x, y;
vector<int> 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 <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> 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"=["<<x<<"]" <<endl
#define FIN freopen("/home/dillonh/CLionProjects/Dillonh/in.txt","r",stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0)

const double eps = 1e-8;
const int mod = 1000000007;
const int maxn = 400000 + 7;
const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;

char op[maxn][3];
int t, n, m, q, tot, cnt;
int x[maxn], y[maxn], num[maxn*6];

int getid(int x) {
    return lower_bound(num + 1, num + tot + 1, x) - num;
}

struct ask {
    int type, x, y, yy;
    bool operator < (const ask& a) const {
        return x == a.x ? type < a.type : x < a.x;
    }
}ask[maxn * 6];

struct node {
    int l, r, lazy, sum;
}segtree[maxn * 12];

void push_down(int rt) {
    int x = segtree[rt].lazy;
    segtree[rt].lazy = 0;
    segtree[lson].sum += x;
    segtree[rson].sum += x;
    segtree[lson].lazy += x;
    segtree[rson].lazy += x;
}

void push_up(int rt) {
    segtree[rt].sum = segtree[lson].sum + segtree[rson].sum;
}

void build(int rt, int l, int r) {
    segtree[rt].l = l, segtree[rt].r = r;
    segtree[rt].lazy = segtree[rt].sum = 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].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;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
二维数点问题

二维数点问题: 给定平面上的$n$个点$(xi,yi)$, 权值$f(xi,yi)$, $m$次矩形查询$sumlimits_{substack{a le i le b \ c le j le d}}f(i,j)$ 以下记$S(a,b)=sumlimits_{substack{i le a \ j le......

osc_3uvms8cw
2019/04/16
2
0
二维数点问题

二维数点问题 二维数点在OI中有着广泛的应用,很多题目正解或其部分分都可以转化为二维数点的模型. 一般性的静态二维数点问题: 给出平面上的$n$个点的坐标$Pi(xi,y_i)$,$Q$次查询,每次查询$(a...

osc_v9knegpw
2019/04/04
2
0
IOI2018题解

只有部分题解 练习赛 T2 自然还是要简单考虑了 0~n-1的排列,考虑相对的大小 我们先考虑对于前三个:a,b,c 询问a,b,询问b,c,再询问a,b,c 发现,如果三个知道两个,那么第三个可以唯一确定 ...

osc_02vmpq90
2019/02/04
1
0
BZOJ1935: [Shoi2007]Tree 园丁的烦恼(树状数组 二维数点)

题意 题目链接 Sol 二维数点板子题 首先把询问拆成四个矩形 然后离散化+树状数组统计就可以了

osc_db1n5a75
2019/01/03
1
0
loj#6041. 「雅礼集训 2017 Day7」事情的相似度(SAM set启发式合并 二维数点)

题意 题目链接 Sol 只会后缀数组+暴躁莫队套set$n sqrt{n} log n$但绝对跑不过去。 正解是SAM + set启发式合并 + 二维数点/ SAM + LCT 但是我只会第一种qwq 首先一个性质是两个前缀的最长公共...

osc_8mj3ztvg
2019/03/29
1
0

没有更多内容

加载失败,请刷新页面

加载更多

asp.net core之NLog

NuGet添加 NLog.Web.AspNetCore。 <PackageReference Include="Microsoft.AspNetCore.App" /> 添加配置文件 新建一个文件nlog.config(建议全部小写,linux系统中要注意), 并右键点击其属性......

一介草民Coder
20分钟前
23
0
.NET中的struct和class有什么区别? - What's the difference between struct and class in .NET?

问题: .NET中的struct和class有什么区别? 解决方案: 参考一: https://stackoom.com/question/3OT/NET中的struct和class有什么区别 参考二: https://oldbug.net/q/3OT/What-s-the-differ...

富含淀粉
今天
23
0
android:layout_weight是什么意思? - What does android:layout_weight mean?

问题: I don't understand how to use this attribute. 我不明白如何使用这个属性。 Can anyone tell me more about it? 谁能告诉我更多关于它的事情? 解决方案: 参考一: https://stacko...

javail
今天
17
0
CSS背景不透明度[重复] - CSS Background Opacity [duplicate]

问题: This question already has an answer here: 这个问题已经在这里有了答案: How do I give text or an image a transparent background using CSS? 如何使用CSS为文本或图像提供透明背...

fyin1314
今天
31
0
node http 获取gb2312网页如何转为utf8

最初,我想当然认为是下述做法,但被证明是错误的 const http = require('http'), iconv = require('iconv-lite');const url = 'http://xxx';http.get(url, function(res) { var bo......

高延
今天
24
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部