Rectangle Query

平面上有 $n$ 个点,你需要回答一些询问:
给定 $x_1,x_2,y_1,y_2 $,在满足 $x_1≤x≤x_2$ 且 $y_1≤y≤y_2$ 的所有点 $(x,y)$ 中,有多少个不同的横坐标($x$坐标)和不同的纵坐标($y$坐标)?

输入

第一行为一个整数$ online(0≤online≤1)$ ,下文中会用到该值。

第二行一个整数 $n(1≤n≤50000)$ ,表示点的个数。

接下来n行,每行两个整数 $x,y(0≤x,y≤500000)$ ,表示每个点的坐标。数据保证所有给出的点都是不同的。

接下来一行,一个整数 $q(1≤q≤50000)$ ,表示询问的个数。

每行四个整数 $x_1,y_1,x_2,y_2$ ,数据是加密的。你需要这样解密:

$x′_1=x_1+(lastx+lasty)×online$

$y′_1=y_1+(lastx+lasty)×online$

$x′_2=x_2+(lastx+lasty)×online$

$y′_2=y_2+(lastx+lasty)×online$

其中,$lastx$表示上一次询问中“有多少个不同的横坐标”的答案,$lasty$表示上一次询问中“有多少个不同的纵坐标”的答案。$lastx$和$lasty$初始为0。

解密后,$x′_1,y′_1,x′_2,y′_2$ 为真正的询问。数据保证 $0≤x′_1<x′_2≤500000,0≤y′_1<y′_2≤500000$

输出

输出$q$行,每行两个整数,用空格隔开,分别表示有多少个不同的横坐标和不同的纵坐标。

样例

输入

样例输入1
1
2
3
4
5
6
7
8
9
10
11
0
4
2 0
2 1
1 1
1 2
4
0 0 2 2
1 1 2 2
1 0 2 1
0 0 1 1
样例输入2
1
2
3
4
5
6
7
8
9
10
11
1
4
2 0
2 1
1 1
1 2
4
0 0 2 2
-4 -4 -3 -3
-3 -4 -2 -3
-4 -4 -3 -3

输出

样例输出1
1
2
3
4
2 3
2 2
2 2
1 1
样例输出2
1
2
3
4
2 3
2 2
2 2
1 1

HINT

【样例解释】

样例1和样例2解密后的询问是一样的。

第1次询问:不同的横坐标有2个${1, 2}$,纵坐标有$3$个${0, 1, 2}$

第2次询问:不同的横坐标有$2$个${1, 2}$,纵坐标有$2$个${1, 2}$

第3次询问:不同的横坐标有$2$个${1, 2}$,纵坐标有$2$个${0, 1}$

第4次询问:不同的横坐标有$1$个${1}$,纵坐标有1个${1}$

【数据范围与约定】

对于$10%$的数据, $n,q≤10000,online=1$

对于另外$20%$的数据,$n,q≤50000,online=1$ ,数据保证任意两个点的横坐标不同且任意两个点的纵坐标不同

对于另外$20%$的数据,$n,q≤50000,online=0$

对于所有数据, $n,q≤50000,0≤online≤1$

题解

模拟赛T3,一开始看到这道题感觉可以用KD树做,于是果断开始码,码到一半发现事情好像有些不对了。怎么去重呢?YY了半天没YY出来,于是弃疗打了个二十分暴力。
其实二十分的暴力用主席树打更轻松。。然而KD树码到一半不想删
正解分块
把坐标离散化。按x坐标从小到大排序,将这些点分为 $sqrt(n)$ 块,用$bitset$存每一块的点。那么我们就可以查询横坐标在$ [x1,x2]$ 的点的集合。再把y坐标按照上述过程做一次,可以得到纵坐标在 $[y1,y2]$ 的点的集合。两者取交集即为所求点集。如果任意两个点横坐标不同且任意两个点的纵坐标不同,这题到这里就做完了。

为了去重,我们用一些小技巧,对于每一个点,我们把该点的纵坐标值改为与它横坐标相同的、纵坐标比它小的、离它最近的点。那么,我们再求一次纵坐标在 $[0,y1)$ 的点的集合,与刚刚求出的答案集合取交集即可求出不同的横坐标的个数。纵坐标同理。

时间复杂度为 $O(n*sqrt(n)+\frac{nq}{64})$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 50050;
pii a[N];
bitset<N>ret;
inline void R(int &v) {
v = 0;
bool p = 0;
static char ch;
do {
ch = getchar();
if (ch == '-') p = 1;
} while (!isdigit(ch));
while (isdigit(ch)) {
v = (v + (v << 2) << 1) + (ch^'0');
ch = getchar();
}
if (p) v = -v;
}
inline void R(bool &v) {
v = 0;
bool p = 0;
static char ch;
do {
ch = getchar();
if (ch == '-') p = 1;
} while (!isdigit(ch));
while (isdigit(ch)) {
v = (v + (v << 2) << 1) + (ch^'0');
ch = getchar();
}
if (p) v = -v;
}
const int block = 225;
const int sz = 223;
int n;
struct gao {
int m, t, f[block];
bitset<N>sum[block];
pii val[N];
inline void init() {
sort(val, val + m);
for (int i = 0; i < n; i += sz) {
f[t] = val[i].first;
int j = min(i + sz, n);
if (t)sum[t] = sum[t - 1];
for (int k = i; k < j; ++k) {
sum[t].set(val[k].second);
}
++t;
}
}
inline bitset<N> get(int x) {
static bitset<N> ret;
ret.reset();
int p = upper_bound(f, f + t, x) - f - 1;
if (p == -1) return ret;
if (p) ret = sum[p - 1];
for (int i = p * sz; i < n; ++i) {
if (val[i].first <= x) ret.set(val[i].second);
else break;
}
return ret;
}
inline bitset<N> getinterval(const int &l, const int &r) {
static bitset<N> ret1, ret2;
ret1 = get(l - 1), ret2 = get(r);
ret1.flip();
return ret1 & ret2;
}
} G[4];
vector<pii>linex[N], liney[N];
#define x1 qaqaqaqaqaqaqaq
#define x2 qwqwqwqwqwqwqwq
#define y1 QAQAQAQAQAQAQAQ
#define y2 QWQWQWQWQWQWQWQ
int main () {
bool online ;
R(online);
R(n);
int x[50050], y[50050];
for (int i = 1; i <= n; ++i) {
R(a[i].first), R(a[i].second);
x[i] = a[i].first, y[i] = a[i].second;
}
sort(x + 1, x + n + 1), sort(y + 1, y + n + 1);
for (int i = 1; i <= n; ++i) {
a[i].first = lower_bound(x + 1, x + n + 1, a[i].first) - x;
a[i].second = lower_bound(y + 1, y + n + 1, a[i].second) - y;
}
for (int i = 1; i <= n; ++i) {
G[0].val[G[0].m++] = make_pair(a[i].first, i);
linex[a[i].first].push_back(make_pair(a[i].second, i));
G[1].val[G[1].m++] = make_pair(a[i].second, i);
liney[a[i].second].push_back(make_pair(a[i].first, i));
}
for (int i = 1; i <= n; ++i) {
sort(linex[i].begin(), linex[i].end());
if (linex[i].size()) G[2].val[G[2].m++] = make_pair(0, linex[i][0].second);
for (int j = 1; j < linex[i].size(); ++j) G[2].val[G[2].m++] = make_pair(linex[i][j - 1].first, linex[i][j].second);
sort(liney[i].begin(), liney[i].end());
if (liney[i].size()) G[3].val[G[3].m++] = make_pair(0, liney[i][0].second);
for (int j = 1; j < liney[i].size(); ++j) G[3].val[G[3].m++] = make_pair(liney[i][j - 1].first, liney[i][j].second);
}
for (int i = 0; i < 4; ++i) {
G[i].init();
}
int q;
R(q);
int x1, x2, y1, y2, lastx = 0, lasty = 0;
bitset<N> tempx, tempy;
for (int i = 1; i <= q; ++i) {
R(x1), R(y1), R(x2), R(y2);
x1 = x1 + (lasty + lastx) * online;
x2 = x2 + (lasty + lastx) * online;
y1 = y1 + (lasty + lastx) * online;
y2 = y2 + (lasty + lastx) * online;
x1 = lower_bound(x + 1, x + n + 1, x1) - x;
x2 = upper_bound(x + 1, x + n + 1, x2) - x - 1;
y1 = lower_bound(y + 1, y + n + 1, y1) - y;
y2 = upper_bound(y + 1, y + n + 1, y2) - y - 1;
ret = G[0].getinterval(x1, x2)&G[1].getinterval(y1, y2);
tempx = ret & G[2].get(y1 - 1);
tempy = ret & G[3].get(x1 - 1);
lastx = tempx.count();
lasty = tempy.count();
printf("%d %d\n", lastx, lasty);
}
}
文章目录
  1. 1. 输入
  2. 2. 输出
  3. 3. 样例
    1. 3.1. 输入
      1. 3.1.1. 样例输入1
      2. 3.1.2. 样例输入2
    2. 3.2. 输出
      1. 3.2.1. 样例输出1
      2. 3.2.2. 样例输出2
  4. 4. HINT
  5. 5. 题解
  6. 6. 代码