首页 > 其他分享 >P2202 题解

P2202 题解

时间:2023-07-03 12:44:28浏览次数:55  
标签:return val int 题解 pos P2202 Poi inf

前言

题目传送门!

更好的阅读体验?

提供一个平衡树做法,虽然和 std::set 一个道理就是了。(那你为啥不写 set!!!!)

前置知识

如何判断两个点对应的正方形相交?正方形的边长是 \(k\),中心距离四条边就是 \(\dfrac k2\) 了。中心要相隔严格小于两段 \(\dfrac k2\),显然只需满足:

\[|X_p-X_q|, |Y_p-Y_q|< k \]

类似地,重叠部分的面积就是 \((k - |X_p - X_q|) \times (k - |Y_p - Y_q|)\)。

思路

很容易想到对 \(x\) 这一维排序,然后写个指针扫一遍,把 \(a_r - a_l \ge k\) 的丢掉即可。

接着加入 \(a_r\)。与之重复面积最大的,必然是它在 \(\text{value}\) 意义上的前驱与后继。

很容易想到平衡树。(std::set:????)以 \(y\) 为第一关键字建立平衡树即可。

显然 \(O(n\log n)\)。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5;

int n, k;
struct Poi {int x, y;} a[N];
bool cmp(Poi p, Poi q) {return p.x < q.x;}
bool chk(Poi p, Poi q) {return abs(p.x - q.x) < k && abs(p.y - q.y) < k;}
long long ans;
void update(Poi p, Poi q)
{
	if (!chk(p, q)) return;
	if (ans) puts("-1"), exit(0); //有两个了,寄 
	ans = 1ll * (k - abs(p.x - q.x)) * (k - abs(p.y - q.y));
}
bool operator < (Poi p, Poi q) {if (p.y != q.y) return p.y < q.y; return p.x < q.x;}
bool operator == (Poi p, Poi q) {return p.x == q.x && p.y == q.y;}
bool operator <= (Poi p, Poi q) {return p < q || p == q;}

struct ScapegoatTree { //替罪羊树板子
	#define ls tr[pos].l
	#define rs tr[pos].r
	#define tmp (tr[ls].siz + (!tr[pos].del))
	
	const double T = 0.7; const int inf = 2147483647;
	struct Node {int l, r, tot, siz; Poi val; bool del; void clear() {l = r = del = 0, siz = tot = 1;}} tr[N];
	int root, stk[N], top, order[N], cnt;
	ScapegoatTree() {for (int i = N - 1; i; i--) stk[++top] = i;}
	void pushup(int pos) {tr[pos].siz = tr[ls].siz + tr[rs].siz + 1, tr[pos].tot = tr[ls].tot + tr[rs].tot + 1;}
	void inorder(int pos) {if (!pos) return; inorder(ls); tr[pos].del ? stk[++top] = pos : order[++cnt] = pos; inorder(rs);}
	void build(int l, int r, int &pos) {if (l > r) return pos = 0, void(); int mid = (l + r) >> 1; pos = order[mid]; if (l == r) return tr[pos].clear(); build(l, mid - 1, ls), build(mid + 1, r, rs); pushup(pos);}
	void rebuild(int &pos) {cnt = 0, inorder(pos); build(1, cnt, pos);}
	int getrnk(int pos, Poi val) {if (!pos) return 0; if (val <= tr[pos].val) return getrnk(ls, val); else return tmp + getrnk(rs, val);} int getrnk(Poi val) {return getrnk(root, val) + 1;}
	Poi getval(int pos, int k) {if (!pos) return (Poi){-inf, -inf}; if (!tr[pos].del && tmp == k) return tr[pos].val; if (k <= tmp) return getval(ls, k); else return getval(rs, k - tmp);} Poi getval(int k) {return getval(root, k);}
	void insert(int &pos, Poi val) {if (!pos) return pos = stk[top--], tr[pos].val = val, tr[pos].clear(); tr[pos].siz++, tr[pos].tot++; if (val <= tr[pos].val) insert(ls, val); else insert(rs, val); if (T * tr[pos].siz <= max(tr[ls].siz, tr[rs].siz)) rebuild(pos);} void insert(Poi val) {insert(root, val);}
	void delett(int &pos, int k) {tr[pos].siz--; if (!tr[pos].del && tmp == k) return tr[pos].del = true, void(); if (k <= tmp) delett(ls, k); else delett(rs, k - tmp);} void delett(Poi val) {delett(root, getrnk(val)); if (T * tr[root].tot >= tr[root].siz) rebuild(root);}
	Poi getpre(Poi val) {Poi t = getval(getrnk(val) - 1); return (t.x == -inf ? (Poi){-inf, -inf} : t);} Poi getsuf(Poi val) {Poi t = getval(getrnk((Poi){val.x + 1, val.y})); return (t.x == -inf ? (Poi){inf, inf} : t);}
	
	#undef ls
	#undef rs
} T;
int main()
{
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].x, &a[i].y);
	sort(a + 1, a + n + 1, cmp);
	for (int l = 1, r = 1; r <= n; r++)
	{
		while (l < r && a[r].x - a[l].x >= k) T.delett(a[l++]);
		Poi pre = T.getpre(a[r]), suf = T.getsuf(a[r]);
		if (pre.x != -T.inf) update(a[r], pre);
		if (suf.y != T.inf) update(a[r], suf);
		T.insert(a[r]);
	}
	cout << ans << '\n';
	return 0;
}

希望能帮助到大家!

标签:return,val,int,题解,pos,P2202,Poi,inf
From: https://www.cnblogs.com/liangbowen/p/17522453.html

相关文章

  • 【CF1621G】Weighted Increasing Subsequences 题解(优化树状数组)
    CF传送门|LG传送门。优化树状数组+反向处理。Solution发现直接做不好下手。难点主要在求出所有的上升子序列并计算它们分别的贡献。所以需要反向考虑每个单点在什么情况下产生贡献。一个单点会产生多少贡献。一个单点产生贡献的条件很容易得到。一个是在一个上升子序......
  • 题解 ARC163C【Harmonic Mean】
    没想出来什么优美的解法,来个乱搞。特判平凡情况\(n\le2\),其中\(n=1\)显然有\(1=\frac{1}{1}\),\(n=2\)无解。众所周知\(1=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots+\frac{1}{2^k}+\frac{1}{2^k}\)。注意到公式中除了\(\frac{1}{2^k}\)有重复外,其余项均无重复。容易......
  • AtCoder ABC307D 题解
    AtCoderABC307DMismatchedParentheses题解思路分析First——配对括号序列首先,每个右括号肯定是要与其左边最近的左括号配对。因此,我们便可以使用一个栈来进行存放左括号的下标。当有右括号时,便可以弹出栈顶元素,但是栈为空时,便无法配对。拿样例1举个例子:8a(b(d))c......
  • 洛谷 P1081 题解
    P1081[NOIP2012提高组]开车旅行题解Link洛谷题目链接Solution首先考虑这道题的暴力做法,对于第一问,枚举每个起始点,暴力计算每个点之后最近和第二近的位置,计算答案,最后取最大值。对于第二问,对每个询问独立模拟即可。复杂度较高,无法通过此题。第一个优化:考虑到对于固定的当......
  • docker启动RabbitMQ以及常见问题解决
    docker启动MQ容器下载docker镜像dockersearchrabbitmqdockerpullrabbitmqdockerrun-d--hostnamemy-rabbit--namerabbit-p15672:15672-p5672:5672rabbitmq:latest启动容器后浏览器无法访问dockerexec-it3b124f0c9712/bin/bashrabbitmq-pluginsenab......
  • CF842E Nikita and game 题解
    题意一棵树初始只有一个编号为1的根结点。\(n\)次操作,每次新增一个点作为\(p_i\)的子结点,询问更新后有多少点可以作为树直径的端点。\(n\le3\times10^5\)。题解以下\(dist(x,y)\)表示点\(x\)与点\(y\)在树上的距离。不难发现若干条直径必然叠合于至少一点,任选这......
  • Codeforces Round 881 Div2 A-F1题解
    codeforcesround881div2题解马上要秋招了,自己本事全丢了,感觉如果这样的话今年就估计要饿死了。先打div3,7月份得开始收心了A.SashaandArrayColoring题意,可以分任意组,每组的贡献是max-min,问最大贡献显然是贪心,从大到小配对一下就行,不想放代码了’B.LongLong给出一......
  • JSON中,java.lang.NoClassDefFoundError: net/sf/ezmorph/Morpher问题解决
    使用JSON,在SERVLET或者STRUTS的ACTION中取得数据时,如果会出现异常:java.lang.NoClassDefFoundError:net/sf/ezmorph/Morpher是因为需要的类没有找到,一般,是因为少导入了JAR包,使用JSON时,除了要导入JSON网站上面下载的json-lib-2.2-jdk15.jar包之外,还必须有其它几个依赖包:commons-bean......
  • dpkg-reconfigure命令找不到问题解决
    作者: adminhttps://cloudbool.com/archive/dpkg-reconfigure-command-not-found.html今天在SSH远程连接到服务器时,遇到了dpkg-reconfigure命令找不到的问题,觉得很是奇怪,花了点时间研究下,这里做个记录,以备后用。前情提要我远程的服务器系统是自行使用DebiannetinstISO镜......
  • [ABC306] C/D 题解
    C.Centers 参考算法统计,排序\(\rmSyx\)给你\(3\timesN\)个数,其中\(\rmSyx\)可以保证:\(1\simN\)之间的所有数都出现了\(3\)次,请你将\(1\simN\)之间的数每个出现在第\(2\)个位置的下标进行排序,并从小到大输出原数。用\(\rmmap\)记录数出现的次数,......