如题所述，只是试一下Markdown
所以我就不发题面了=_=
不如当一个萌萌哒链接菌吧=_=
毕竟我懒=_=
题目传送门
Solution
卧槽。【总领全文，奠定感情基调】
首先我们可以进行坐标变换。
如果两个向量构成一组基底，
我们可以把平面内每个的坐标 $(x_i,y_i)$ 变换成 $(a_i,b_i)$，
使得：
$$a_i \times x_1 + b_i \times x_2 = x_i$$
$$a_i \times y_1 + b_i \times y_2 = y_i$$
于是我们可以求得 $a_i$ 和 $b_i$：
$$a_i = \frac{x_i \times y_2 - y_i \times x_2}{x_1 \times y_2 - x_2 \times y_1}$$
$$b_i = \frac{x_i \times y_1 - y_i \times x_1}{x_1 \times y_2 - x_2 \times y_1}$$
然后我们发现这些坐标都是分数，
而且最重要的是：分母都是一样的。
于是我们可以令所有的坐标都乘以这个分母（要保证乘的是正的数字）。
于是我们就可以离散化这些点的坐标，使得坐标范围变成一个$ (1, 1) - (n, m) $的矩阵。
于是再给点以 $b_i$ 为第一关键字，$a_i$ 为第二关键字排序，
并按照这个顺序处理那些点。
这样我们后面的点的 $b$ 坐标就一定大于等于前面的点的 $b$ 坐标，
就可以不用管这一维了，只用管 $a$ 坐标了。
于是我们假设处理到第 $i$ 个灯泡，
令 $t$ 为以 $(1, 1)$ 为左下角，$(a_i, b_i)$ 为右上角的矩阵中 $Ans[]$ 第 $K[i]$ 小的值。
那么 $Ans[i] = min(i, t)$。
特别的，如果那个矩阵中没有$K[i]$多灯泡，$Ans[i] = i$。
于是怎么维护呢？
【插入操作】
我们以时间为 $Ans[]$ 第一关键字建立线段树，套上以 $a$ 坐标为第二关键字的平衡树。
每次插入都会在 $O(\log n)$ 个线段树结点所套的平衡树中进行时间为 $O(\log n)$ 的插入操作，
于是插入操作的时间复杂度是 $O(\log^2 n)$ 的。
【查询操作】
怎么查询以 $(1, 1)$ 为左下角，$(a_i, b_i)$ 为右上角的矩阵中 $Ans[]$ 第 $K[i]$ 小的值呢？
我们可以二分答案。
具体做法就是从线段树根结点开始，先看左儿子所套的平衡树里边 $a$ 坐标小于等于 $a_i$ 的结点个数。
设有 $u$ 个，那么就说明 $Ans[]$ 在 $[l, mid]$ 区间内的，
并且在以 $(1, 1)$ 为左下角，$(a_i, b_i)$ 为右上角的矩阵中的点有 $u$ 个。
如果 $u \ge K[i]$，说明答案应该在 $[l, mid]$ 之间，然后递归处理。
否则答案就应该在 $[mid + 1, r]$ 之间，然后递归处理。
直到 $l = r$ 的时候，便可确定 $Ans[i] = min(i, l)$。
然后我们可以加上一个小优化：
如果递归处理到 $[l, r]$ 的区间，并且有 $l \ge i$，
那么直接返回 $i$，
因为 $Ans[i] = min(i, l)$，
如果可能的最小值都不比 $i$ 小了，那么就没有做下去的必要了。
查询操作中，我们要访问 $O(\log n)$ 个线段树结点，在每个线段树节点中，都要 $O(\log n)$ 地查找相关点的个数。
所以查询操作的时间复杂度也是 $O(\log^2 n)$ 的。
然后有 $O(n)$ 个灯泡，所以总时间复杂度是 $O(n \log^2 n)$ 的。
每个灯泡的信息会被插入到 $O(\log n)$ 个线段树所套的平衡树里，
所以空间复杂度是 $O(n \log n)$ 的。
如果写矩形树（其实就是二维线段树TAT这只不过是我生造的名字）的话空间复杂度就是 $O(n \log^2 n)$ 的，承受不了。
所以才要写这种蛋疼的东西。。。
卧槽。【承上启下，推动情节发展】
等等。
我们好像忽略了一点：
如果灯的照射范围是一条线该怎么办。。。
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊。。。
其实也比较好处理。
我们把另一个向量弄成垂直于当前的这条向量。
可以令 ：$x_2 = -y_1$，$y_2 = x_1$
然后也可以求出点的 $a$ 坐标和 $b$ 坐标，
只不过在查询的时候，我们找的就不是矩阵中点的个数，
而是某一条线段里边的点的个数了。
稍微处理一下就可以了。。。=_=
具体实现可以看我的代码。
卧槽。【总结全文，升华文章主旨】
毕竟 $Gromah$ 太弱，只会做水题。
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
#define N 200000 + 5
#define M 524288 + 5
#define SIZE 5000000 + 5
#define ls(x) x << 1
#define rs(x) x << 1 | 1
int n, tot, Ord[N], Root[M], Ans[N], K[N];
LL x_1, y_1, x_2, y_2, X[N], Y[N], _X[N], _Y[N];
struct Data
{
int l, r, fa, size, num, fix;
}h[SIZE];
inline void update(int x)
{
h[x].size = h[h[x].l].size + h[h[x].r].size + h[x].fix;
}
inline void zig(int x)
{
int y = h[x].fa, z = h[y].fa;
if (y == h[z].l) h[z].l = x;
if (y == h[z].r) h[z].r = x;
h[x].fa = z, h[y].fa = x;
h[y].l = h[x].r, h[h[x].r].fa = y, h[x].r = y;
update(y), update(x);
}
inline void zag(int x)
{
int y = h[x].fa, z = h[y].fa;
if (y == h[z].l) h[z].l = x;
if (y == h[z].r) h[z].r = x;
h[x].fa = z, h[y].fa = x;
h[y].r = h[x].l, h[h[x].l].fa = y, h[x].l = y;
update(y), update(x);
}
inline void Splay(int &root, int x)
{
while (h[x].fa)
{
int y = h[x].fa, z = h[y].fa;
if (x == h[y].l)
{
if (y == h[z].l) zig(y);
zig(x);
}
else
{
if (y == h[z].r) zag(y);
zag(x);
}
}
root = x;
}
inline void Insert(int &root, int u)
{
if (!root)
{
root = ++ tot;
h[tot].size = h[tot].fix = 1, h[tot].num = u;
return ;
}
int z, p = root;
while (p)
{
z = p;
h[z].size ++;
if (u == h[z].num)
{
h[z].fix ++;
return ;
}
if (u > h[z].num)
p = h[z].r;
else p = h[z].l;
}
h[++ tot].fix = 1;
h[tot].size = 1;
h[tot].num = u;
h[tot].fa = z;
if (u > h[z].num)
h[z].r = tot;
else h[z].l = tot;
Splay(root, tot);
}
inline int Find(int x, int k, bool op)
{
int res = 0;
while (1)
{
if (!x)
{
if (op) return 0;
break ;
}
if (k == h[x].num)
{
if (op) return h[x].fix;
res += h[h[x].l].size + h[x].fix;
break ;
}
else if (k > h[x].num)
{
res += h[h[x].l].size + h[x].fix;
x = h[x].r;
}
else x = h[x].l;
}
return res;
}
inline int Query(int x, int l, int r, int k, int lim, int Lim, bool op)
{
if (l >= Lim) return Lim;
if (l == r) return l;
int mid = l + r >> 1;
int t = Find(Root[ls(x)], lim, op);
if (k <= t)
return Query(ls(x), l, mid, k, lim, Lim, op);
else return Query(rs(x), mid + 1, r, k - t, lim, Lim, op);
}
inline void Modify(int x, int l, int r, int t, int k)
{
Insert(Root[x], k);
if (l == r) return ;
int mid = l + r >> 1;
if (t <= mid)
Modify(ls(x), l, mid, t, k);
else Modify(rs(x), mid + 1, r, t, k);
}
inline int getint()
{
char ch = '\n';
for (; ch != '-' && (ch > '9' || ch < '0'); ch = getchar()) ;
int f = ch == '-' ? -1 : 1;
int res = ch == '-' ? 0 : ch - '0';
for (ch = getchar(); ch >= '0' && ch <= '9'; ch = getchar())
res = (res << 3) + (res << 1) + ch - '0';
return res * f;
}
inline bool cmp(int u, int v)
{
return X[u] < X[v] || (X[u] == X[v] && Y[u] < Y[v]);
}
inline void Solve(bool op)
{
if (op) x_2 = -y_1, y_2 = x_1;
int f = (x_2 * y_1 - x_1 * y_2 > 0) ? 1 : -1;
for (int i = 1; i <= n; i ++)
{
LL u = getint(), v = getint();
_X[i] = X[i] = (x_2 * v - y_2 * u) * f;
_Y[i] = Y[i] = (y_1 * u - x_1 * v) * f;
}
sort(_X + 1, _X + n + 1);
sort(_Y + 1, _Y + n + 1);
int sx = unique(_X + 1, _X + n + 1) - _X;
int sy = unique(_Y + 1, _Y + n + 1) - _Y;
for (int i = 1; i <= n; i ++)
{
int u = lower_bound(_X + 1, _X + sx, X[i]) - _X;
int v = lower_bound(_Y + 1, _Y + sy, Y[i]) - _Y;
X[i] = u, Y[i] = v;
Ord[i] = i, K[i] = getint();
}
sort(Ord + 1, Ord + n + 1, cmp);
for (int i = 1; i <= n; i ++)
{
int _i = Ord[i];
if (Find(Root[1], Y[_i], op) < K[_i]) Ans[_i] = _i;
else Ans[_i] = Query(1, 1, n, K[_i], Y[_i], _i, op);
Modify(1, 1, n, Ans[_i], Y[_i]);
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("3833.in", "r", stdin);
freopen("3833.out", "w", stdout);
#endif
n = getint();
x_1 = getint(), y_1 = getint();
x_2 = getint(), y_2 = getint();
Solve(x_1 * y_2 == x_2 * y_1);
for (int i = 1; i <= n; i ++)
printf("%d%c", Ans[i], " \n"[i == n]);
return 0;
}
鄂公网安备 42010202000505 号