标签：tree   记录   离散化   i++   也有   struct   结构   const   进一步   

新家

题目链接

首先这个没有修改只有询问，可以把年份当时间轴，按年份顺序模拟，这样我们就把年份这一维去掉了。

首先 \(-1\) 比较好判断，单独记录一下目前存在几种商店就行，数组就行。

然后我们需要数据结构，支持：

1. 插入和删除商店
2. 查询不方便指数

考虑从 2 入手，对于一个查询二元组 \((l, y)\)，对于每个类型 \(i\)，我们假设距离 \(l\) 最近的这个类型的商店的坐标是 \(x_i\)，答案是 \(\displaystyle \max_{i=1}^k(|x_t - l|)\)，显然可以分类讨论为 ① \(l ，距离为 \(x_t - l\) ② \(x_t ，距离为 \(l - x_t\)。

那么我们就可以去掉绝对值，即在 \(l\) 左/右边是最优决策，问题拆为 \(\max(\max(l - x_t), \max(x_t‘ - l))\)。 注意这个 \(x_t‘\) 是在 \(l\) 右侧的 \(x\)。由于每个询问 \(l\) 是确定的，所以对于前一部分，即最大化 \(x_t\)；对于后半部分，即最小化 \(x‘_t\)。

考虑在插入和删除商店时对每个位置最优决策的影响。

...然后发现这个最优性操作插入的时候无法确定答案，我自闭了...

无耻去看题解...

自己没想到二分答案emm。

我们考虑二分答案 \(m\)，那么如果 \(ans > m\) ，等价于 \([l - m + 1, l + m - 1]\) 存在的不同类型商店数 \(，即在 \([l + m, \infty]\) 存在一个商店同类型的前驱的位置 $ \le l - m$，即他们的前驱最小值位置 \(\le l - m\)。这个前驱可以用 \(\text{set}\) 进行维护，区间最小值用线段树维护，离散化一下，这样就能 \(O(n \log 10^8 \log n)\) 了。

为了保证可行性的正确，所以我们还要在 \([n + 1, n + k]\) 分别插入位置为 \(\infty\)，颜色为 \(1\) 到 \(k\) 的 \(k\) 种颜色，这样才能保证查后缀时，所有颜色都进行了统计。

代码

调了 5h ...

#include 
#include 
#include 
#include 

using namespace std;

char buf[1  ‘9‘ || s = ‘0‘ && s ::iterator SIT;

const int N = 300005, INF = 1e9;

int n, k, q, pos[N * 2], tot, ans[N], cnt[N], num, len;

struct Shop{
	int x, y, t, w, id;
	bool operator  c[N];

struct Prob{
	int l, t, id;
	bool operator > 1;
	build(p > 1;
	if (x > 1, res = INF;
	if (x = e[i].l - mid;
}

int main() {
	read(n); read(k); read(q);
	build(1, 1, n + k);
	for (int i = 1; i = 0) ins(j);
			else del(j);
			++j;
		}
		if (num > 1;
			if (check(mid, i)) r = mid;
			else l = mid + 1;
		}
		ans[e[i].id] = r;
	}
	for (int i = 1; i 

还可以进一步优化，考虑在线段树上二分，设那个不合法位置为 \(y\)，记 \([y, \infty)\) 中最小的前驱为 \(pre\)，即求最大的 \(y\) 满足 \(y + pre \le 2x\)，答案就是 \(y - l\)，那么在线段树上维护 \(pre\) 的最小值，显然 \(pre + y\) 是一个递增的形式，所以如果令 \(1\) 代表满足该式子， \(0\) 代表不符合，组成的序列一定是 \(1111100000\) 状物的，具有单调性，这样我们把最大的 \(1\) 找出来，答案就在 \(1\) 这个位置。

假设当前枚举到线段树上的 \([l, r]\)。

• 如果 \(x\) 在 \([l, mid]\)，判断一下 \(mid + 1\) 有没有满足上述不等式的，有就去右边，否则去左边
• 如果 \(x\) 在 \([mid + 1, r]\)，直接去右边查即可。

这样就能 \(O(n \log n)\) 了。

代码

细节太多了，我自闭了，调了七个多小时。你谷 Rank 1 可还行。

• 离散化后，假设 \(d_i\) 代表 \(i\) 的坐标，上面一步要查 \(d_{mid} + 1\) 而非 \(d_{mid + 1}\)！因为整数域上，\((d_{mid}, d_{mid+1})\) 也有可能的答案，如果这中间有满足不合法式子，那么一定要去右边，因为这样才能摆脱 \(pre_{mid}\) 的影响，这个毒瘤死了，我查了三个小时。

#include 
#include 
#include 
#include 

using namespace std;

char buf[1 ‘9‘ || s = ‘0‘ && s ::iterator SIT;

const int N = 300005, INF = 1e9;

int n, k, q, pos[N * 2], tot, ans[N], cnt[N], num, len;

struct Shop{
	int x, y, t, w, id;
	bool operator  c[N];

struct Prob{
	int l, t, id;
	bool operator > 1;
	build(p > 1;
	if (x > 1, res = 2 * INF;
    if (x > 1;
	if (x > d[mid].x) return query(p = 0) ins(j);
			else del(j);
			++j;
		}
		if (num 

选圆圈

选圆圈

不会 KD-Tree 草。

铁人两项

咕咕咕

APIO2018 题解

标签：tree   记录   离散化   i++   也有   struct   结构   const   进一步   

原文地址：https://www.cnblogs.com/dmoransky/p/13493673.html