Codechef 14.9 QRECT CDQ分治+分治+线段树
题目大意：
给定一个二维平面，共有$Q$组询问，支持插入或者删除一个矩形，或者给定一个矩形，询问目前平面上有多少个矩形和这个矩形有至少一个交点。
数据范围$Q\leq{10^5}$。
算法讨论：
考虑离线处理，将询问转化为给定的这个矩形与平面上的多少个矩形没有交点。
将在平面上插入的每个矩形权值设为$1$，删除的每个矩形权值设为$-1$，这样就只有插入操作了，同时将问题转化为求平面上与这个矩形没有交点的矩形的权值和。
与一个矩形没有交点的矩形可以用全部矩形减去完全在这个矩形上方的，在这个矩形下方的，完全在这个矩形左方的，完全在这个矩形右方的所有矩形权值和。但是这样四个角会被减去两次，所以还要加回来一次。
将这些问题的贡献分开考虑，四个方向的贡献可以用一个一维按时间分治解决；四个角的贡献可以用一个二维的按时间分治解决。
于是总时间复杂度$O(Q\log ^2Q)$。
时空复杂度：
时间复杂度$O(Q\log ^2Q)$，空间复杂度$O(Q)$。
代码：
#include <cstdio>
#include <cstring>
#include <cctype>
#include <climits>
#include <iostream>
#include <algorithm>
using namespace std;
int getc() {
static const int L = 1 << 15;
static char buf[L], *S = buf, *T = buf;
if (S == T) {
T = (S = buf) + fread(buf, 1, L, stdin);
if (S == T)
return EOF;
}
return *S++;
}
int getint() {
static int c, x;
while (!isdigit(c = getc()));
x = c - '0';
while (isdigit(c = getc()))
x = (x << 1) + (x << 3) + c - '0';
return x;
}
char getch() {
static char c;
while ((c = getc()) != 'I' && c != 'D' && c != 'Q');
return c;
}
#define N 100010
struct SegmentTree {
int a[524288], t[524288], M, tclock;
int get(int x) {
if (t[x] != tclock) {
t[x] = tclock;
a[x] = 0;
}
return a[x];
}
void add(int x, int c) {
if (t[x] != tclock) {
t[x] = tclock;
a[x] = 0;
}
a[x] += c;
}
void init(int n) {
for (M = 1; M < n + 2; M <<= 1);
++tclock;
}
int query(int tl, int tr) {
static int ans;
ans = 0;
for (tl += M - 1, tr += M + 1; tl ^ tr ^ 1; tl >>= 1, tr >>= 1) {
if (~tl & 1)
ans += get(tl ^ 1);
if (tr & 1)
ans += get(tr ^ 1);
}
return ans;
}
void modify(int x, int c) {
for (x += M; x; x >>= 1)
add(x, c);
}
}Seg;
int dx[200010], dy[200010], idx, idy;
int findx(int x) {
return lower_bound(dx + 1, dx + idx + 1, x) - dx;
}
int findy(int y) {
return lower_bound(dy + 1, dy + idy + 1, y) - dy;
}
struct Rect {
int x1, x2, y1, y2;
void read() {
x1 = getint();
y1 = getint();
x2 = getint();
y2 = getint();
}
};
struct Note {
Rect x;
int w;
}S[100010];
int ans[100010], addid[100010];
#define mp make_pair
#define fi first
#define se second
pair<int, int> diary[100010];
void solve_1d(int l, int r, bool small, bool x) {
if (l == r)
return;
int mid = (l + r) >> 1;
solve_1d(l, mid, small, x);
solve_1d(mid + 1, r, small, x);
Seg.init(x ? idx : idy);
for (int i = l; i <= mid; ++i)
if (diary[i].se <= 0)
Seg.modify(diary[i].fi, diary[i].se == 0 ? 1 : -1);
for (int i = mid + 1; i <= r; ++i)
if (diary[i].se > 0) {
if (small)
ans[diary[i].se] -= Seg.query(1, diary[i].fi);
else
ans[diary[i].se] -= Seg.query(diary[i].fi, x ? idx : idy);
}
}
typedef pair<pair<int, int>, int> piii;
piii diary2[100010], temp[100010];
bool cmp_left(const piii &a, const piii &b) {
if (a.fi.fi != b.fi.fi)
return a.fi.fi < b.fi.fi;
return a.se < b.se;
}
bool cmp_right(const piii &a, const piii &b) {
if (a.fi.fi != b.fi.fi)
return a.fi.fi > b.fi.fi;
return a.se < b.se;
}
void solve_2d(int l, int r, bool left, bool down) {
if (l == r)
return;
int mid = (l + r) >> 1;
solve_2d(l, mid, left, down);
solve_2d(mid + 1, r, left, down);
Seg.init(idy);
int num = 0;
for (int i = l; i <= mid; ++i)
if (diary2[i].se <= 0)
temp[++num] = diary2[i];
for (int i = mid + 1; i <= r; ++i)
if (diary2[i].se > 0)
temp[++num] = diary2[i];
if (left)
sort(temp + 1, temp + num + 1, cmp_left);
else
sort(temp + 1, temp + num + 1, cmp_right);
for (int i = 1; i <= num; ++i) {
if (temp[i].se <= 0)
Seg.modify(temp[i].fi.se, temp[i].se == 0 ? 1 : -1);
else {
if (down)
ans[temp[i].se] += Seg.query(1, temp[i].fi.se);
else
ans[temp[i].se] += Seg.query(temp[i].fi.se, idy);
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("tt.in", "r", stdin);
freopen("tt.out", "w", stdout);
#endif
int q = getint();
int i, j, tot = 0, ask = 0, add = 0;
char ch;
for (i = 1 ; i <= q; ++i) {
ch = getch();
if (ch == 'I') {
S[i].w = 0;
S[i].x.read();
dx[++idx] = S[i].x.x1;
dx[++idx] = S[i].x.x2;
dy[++idy] = S[i].x.y1;
dy[++idy] = S[i].x.y2;
++tot;
addid[++add] = i;
}
else if (ch == 'Q') {
S[i].x.read();
dx[++idx] = S[i].x.x1 - 1;
dx[++idx] = S[i].x.x2 + 1;
dy[++idy] = S[i].x.y1 - 1;
dy[++idy] = S[i].x.y2 + 1;
ans[++ask] = tot;
S[i].w = ask;
}
else {
S[i].w = -1;
S[i].x = S[addid[getint()]].x;
--tot;
}
}
sort(dx + 1, dx + idx + 1);
idx = unique(dx + 1, dx + idx + 1) - dx - 1;
sort(dy + 1, dy + idy + 1);
idy = unique(dy + 1, dy + idy + 1) - dy - 1;
for (i = 1; i <= q; ++i) {
if (S[i].w > 0)
diary[i] = mp(findx(S[i].x.x1 - 1), S[i].w);
else
diary[i] = mp(findx(S[i].x.x2), S[i].w);
}
solve_1d(1, q, 1, 1);
for (i = 1; i <= q; ++i) {
if (S[i].w > 0)
diary[i] = mp(findy(S[i].x.y1 - 1), S[i].w);
else
diary[i] = mp(findy(S[i].x.y2), S[i].w);
}
solve_1d(1, q, 1, 0);
for (i = 1; i <= q; ++i) {
if (S[i].w > 0)
diary[i] = mp(findx(S[i].x.x2 + 1), S[i].w);
else
diary[i] = mp(findx(S[i].x.x1), S[i].w);
}
solve_1d(1, q, 0, 1);
for (i = 1; i <= q; ++i) {
if (S[i].w > 0)
diary[i] = mp(findy(S[i].x.y2 + 1), S[i].w);
else
diary[i] = mp(findy(S[i].x.y1), S[i].w);
}
solve_1d(1, q, 0, 0);
for (i = 1; i <= q; ++i) {
if (S[i].w > 0)
diary2[i] = mp(mp(findx(S[i].x.x1 - 1), findy(S[i].x.y2 + 1)), S[i].w);
else
diary2[i] = mp(mp(findx(S[i].x.x2), findy(S[i].x.y1)), S[i].w);
}
solve_2d(1, q, 1, 0);
for (i = 1; i <= q; ++i) {
if (S[i].w > 0)
diary2[i] = mp(mp(findx(S[i].x.x2 + 1), findy(S[i].x.y2 + 1)), S[i].w);
else
diary2[i] = mp(mp(findx(S[i].x.x1), findy(S[i].x.y1)), S[i].w);
}
solve_2d(1, q, 0, 0);
for (i = 1; i <= q; ++i) {
if (S[i].w > 0)
diary2[i] = mp(mp(findx(S[i].x.x1 - 1), findy(S[i].x.y1 - 1)), S[i].w);
else
diary2[i] = mp(mp(findx(S[i].x.x2), findy(S[i].x.y2)), S[i].w);
}
solve_2d(1, q, 1, 1);
for (i = 1; i <= q; ++i) {
if (S[i].w > 0)
diary2[i] = mp(mp(findx(S[i].x.x2 + 1), findy(S[i].x.y1 - 1)), S[i].w);
else
diary2[i] = mp(mp(findx(S[i].x.x1), findy(S[i].x.y2)), S[i].w);
}
solve_2d(1, q, 0, 1);
for (i = 1; i <= ask; ++i)
printf("%d\n", ans[i]);
return 0;
}
评论 (0)