2020-2021 ACM-ICPC Brazil Subregional Programming Contest M. Machine Gun @ Wings            分类 ACM
发布于 星期四, 二月 18 日, 2021 年
更新于 星期二, 七月 20 日, 2021 年

题目

题意

在二维平面上给出 $n$ 个敌军的坐标 $A_i(x_i, y_i)$, 再进行q次强制在线询问:

每次询问将给出一个炮台坐标 $(x_m, y_m)$, 需找出所有能被坐标 $(x_m, y_m)$ 攻击到的敌军的下标. 这里定义炮台 $(x_m, y_m)$ 能攻击到的范围是 $y = y_m \pm \frac{x - x_m}{2}$ 所夹出来的右半部分, 包括边界.

接下来将这些下标按照升序排序, 记为$i_0, i_1, \dots i_k$

计算结果 $(\sum_{j=0}^{k-1} i_j \cdot 5782344^j) \mod 10^9 + 7$, 输出结果.

$1 \le x_i, y_i \le 10^9, 1 \le n, q, \le 10^5$

保证所有查询中被攻击到的敌军总数不超过 $10^6$, 保证$x_i > 0, x_m < 0$

题解

有两种考虑方式.

第一种

施鹏飞学长讲的:

注意到每个炮台所能攻击到的范围角度是固定的, 所以为了更好地刻画炮台 攻击的覆盖范围, 我们可以将炮台的攻击范围投影到$x=0$这条线上; 类似地, 将每个敌军以同样的角度都投影到$x=0$这条线上. 如果两条线段有交集, 那么 该炮台就可以攻击到这个敌军.

线段

问题就等价地转化为: 在数轴上给出 $n$ 个区间, 再进行 $q$ 次 查询, 每次查询给出一个区间, 询问 $n$ 个区间中有哪些区间与询问的区间相交.

形式化一下, 我们要找这样的区间: $l_i \le r_m, r_i \ge l_m$, 其中 $[l_m, r_m]$是询问区间.

第二种

将坐标进行伸缩变换:

  1. 把两条边的夹角改成直角: $y \to 2y$
  2. 把 $x$ 轴 $y$ 轴顺时针转 $\frac{\pi}{4}$: $(x, y) \to (x - y, x + y)$

总的来说, 把 $(x, y) \to (x - 2y, x + 2y)$.

也就是说, 令每个点的坐标为 $\begin{cases} x' = x - 2y \newline y' = x + 2y \end{cases}$

也就是得到下面这种东西:

坐标

然后找这样的点: $x_i' \ge x_m', y_i' \ge y_m'$

实际上两者没有本质区别, 最后得到的关系都是一样的, 只是思考方式的不同.

当然还有第三种方法, 就是直接推算满足什么样的条件的点会被炮塔打到. 得到的结果是一样的.

到这里就转换成了二维偏序问题. 先对一维排序, 然后再放到数据结构上排第二维.

这里需要的不是个数, 而是所有的点的下标. 所以考虑用线段树, 每个节点开一个 vector 按第二维的顺序存 第二维原下标(需要第二维排序, 需要原下标).

二分确定第一维的范围, 在线段树上区间查询第二维即可. 二维偏序就是这个套路.

复杂度 $O(n \log n + q \log^2 n)$

代码
const int P = 1e9 + 7;
const LL BASE = 5782344;

const int MAXN = 1e5+10;

int Plus(LL a, LL b) {
	return a + b >= P ? (a + b) % P : a + b;
}
int Mult(LL a, LL b) {
	return a * b >= P ? a * b % P : a * b;
}

struct Seg {
	LL l, r, id;
	bool operator < (const Seg &S) const {
		return r == S.r ? l == S.l ? id < S.id : l < S.l : r < S.r;
	}
} segs[MAXN];

int n, q;
LL p = 0;

Seg calc_seg(LL x, LL y, int id) {
	LL l = 2 * y - x, r = 2 * y + x;
	if (l > r)
		swap(l, r);
	return Seg{l, r, id};
}

struct SegTree {
	struct Node {
		int l, r, mid;
		vector<PLI> v;
	};
	vector<Node> tree;
	SegTree(int _n, Seg data[]) {
		tree.resize(_n << 2);
		build(data, 1, _n);
	}
	void push_up(int u) {
		vector<PLI> &lv = tree[LCH(u)].v, &rv = tree[RCH(u)].v, &v = tree[u].v;
		int i = 0, j = 0, len_l = lv.size(), len_r = rv.size();
		while (i < len_l && j < len_r) {
			if (lv[i] < rv[j])
				v.push_back(lv[i++]);
			else
				v.push_back(rv[j++]);
		}
		while (i < len_l)
			v.push_back(lv[i++]);
		while (j < len_r)
			v.push_back(rv[j++]);
	}
	void build(Seg data[], int l, int r, int u = 1) {
		tree[u] = Node{l, r, (l + r) >> 1};
		tree[u].v.clear();
		if (l == r)
			tree[u].v.push_back(make_pair(data[l].l, data[l].id));
		else {
			build(data, l, tree[u].mid, LCH(u));
			build(data, tree[u].mid + 1, r, RCH(u));
			push_up(u);
		}
	}
	void add_ans(set<LL> &res, LL r, int u) {
		for (auto x : tree[u].v) {
			if (x.first > r)
				break;
			else
				res.insert(x.second);
		}
	}
	void query(set<LL> &res, LL rr, int l, int r, int u = 1) {
		if (l == tree[u].l && r == tree[u].r)
			add_ans(res, rr, u);
		else {
			if (l > tree[u].mid)
				query(res, rr, l, r, RCH(u));
			else if (r <= tree[u].mid)
				query(res, rr, l, r, LCH(u));
			else {
				query(res, rr, l, tree[u].mid, LCH(u));
				query(res, rr, tree[u].mid + 1, r, RCH(u));
			}
		}
	}
};

int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++) {
		LL x, y;
		scanf("%lld%lld", &x, &y);
		segs[i] = calc_seg(x, y, i);
	}
	sort(segs + 1, segs + 1 + n);

	SegTree T(n, segs);
	while (q--) {
		LL a, b;
		scanf("%lld%lld", &a, &b);
		LL x = - 1 - Plus(p, a), y = Plus(p, b);
		Seg s = calc_seg(x, y, 0);
		int pos = lower_bound(segs + 1, segs + 1 + n, Seg{-INF, s.l, 0}) - segs;
		p = 0;
		if (pos <= n) {
			set<LL> res;
			res.clear();
			T.query(res, s.r, pos, n);
			LL power = 1;
			for (auto x : res) {
				p = Plus(p, Mult(power, x));
				power = Mult(power, BASE);
			}
		}
		printf("%lld\n", p);
	}
	return 0;
}

检查参数是不是没写LL

留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了
  15. 2021团体程序设计天体赛(CCCC) 个人二等奖
  16. 2021 西电 miniL CTF 优胜奖
  17. 2021 西电ACM校赛 第9名 金牌
  18. 2021 西电数模校赛 二等奖
  19. 2021 第15届IEEE 第48名
  20. 2021 CCPC 桂林站 打星

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch