说明
因为扫喵线比较可爱，所以以下称扫描线为扫喵线。
你问我标题为什么不这样改，那是因为如果这样的话不太方便查自己题解啦
题解
首先考虑暴力
紫色类型的位置 (右边和下面都没有边框)，我们有转移方程
$$f[i][j]=f[i][j + 1] + f[i+1][j] – f[i + 1][j + 1]$$
黄色类型的位置 (只有下面有边框)，我们有
$$f[i][j]=f[i][j+1]$$
蓝色类型的位置 (只有右边有边框)，我们有
$$f[i][j]=f[i + 1][j]$$
红色类型的位置就有点复杂了 (右下角有方框)，首先它肯定是由 $f[i+1][j]$和 $f[i][j+1]$贡献来的，但是你会发现多算了一些东西。
黄色区域是 $f[i][j+1]$的贡献，蓝色区域是 $f[i+1][j]$的贡献，绿色区域是它们贡献的交集。
所以我们还要减去绿色部分的答案，具体来将就是记当前位置右下角边框为 $[(x1,y1),(x2,y2)]$，那么还要减去 $f[x2+1][y2+1]$
时间复杂度 $O(n^2)$
如何快速进行维护呢？
我们可以采用扫喵线+线段树的维护方法，具体来讲，从右往左扫喵，并且用线段树维护相关答案信息。
最直接的想法就是，维护每个点的答案，在扫喵线左移的同时用线段树维护各种东西。
但是考虑一下最普通的转移
$$f[i][j]=f[i][j + 1] + f[i+1][j] – f[i + 1][j + 1]$$
你会发现如果你移动了扫喵线的话，相当于只将 $f[i][j+1]$的贡献给了 $f[i][j]$，但是 $f[i+1][j]$此时是多少是不确定的，所以无法进行有效的转移
我们通过观察式子，可以发现一些神奇的事情
$$f[i][j]-f[i+1][j]=f[i][j+1]-f[i+1][j+1]$$
也就是说我们在每个点维护答案的差分的话，线段树上的这种转移的点就不用进行修改，并且当前点的答案就是当前位置到当前边框边界的和
类似的还有上面的蓝色类型点
$$f[i][j]-f[i+1][j]=0$$
因为蓝色类型的点右边是边框，所以显然线段树这个位置原本就是 $0$
黄色类型的点就变成了
$$f[i][j]-0=f[i][j+1]-0$$
当然这里前提是 $(i,j+1)$这个位置也是黄色类型的点，如果不是，就相当于原本线段树第 $j+1$个位置维护的是 $f[i][j+1]-f[i+1][j+1]$，因此我们要将转移后的点的信息再加上 $f[i+1][j+1]$即可。
现在最棘手的就是红色类型的点怎么转移。
容易知道，我们维护差分信息的话，对于一个红色类型点 $(i,j)$，我们有
$$f[i][j]-f[i+1][j]=f[i][j+1]-0$$
对比标准的
$$f[i][j]=f[i+1][j]+f[i][j+1]-f[x2+1][y2+1]$$
我们还需要将当前差分信息减去 $f[x2+1][y2+1]$，这个在每次转移边框的时候维护一下其实就行了
或许前面的内容比较抽象，我们来图解一下如何转移
橙色的是扫喵线，现在在边框的右边界，我们要记录一下 $rd[i]$所在位置的答案，表示的是边框 $i$的右下角的贡献，并且还要将边框左上角的上面那个格子所代表的数 $-f[i][j+1]$，通过在线段树上 $query$一下就可以实现，并且边框边界还需要区间赋值为 $0$，因为它们的答案差分显然是 $0$
当扫喵线到达边框左边界的时候，我们需要将红色位置在线段树上减去 $rd[i]$，原因在前面已经说过了，并且照例要将边框所在区间赋值为 $0$
如何维护当前上下边框的边界呢？一个 $set$维护一下就行了啦
代码里有一些可以调试的东西，$a$数组模拟了线段树里的情况，方便调试。
#include<bits/stdc++.h>
#define N 1000005
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define Re register
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mp std::make_pair
#define Judge_Online
struct tree{
int sum;
bool fl;
}t[N << 2];
struct flower_cow{
int x, y, id;
friend bool operator < (flower_cow a, flower_cow b) {return a.y < b.y;}
}f[N], c[N];
struct block{
int l, r, y, id, opt;
friend bool operator < (block a, block b) {return a.y < b.y || a.y == b.y && a.opt < b.opt;}
}b[N << 1];
int tot, rd[N], T, n, m, xmax, ymax, ans[N];
inline void pushdown (int u)
{
if (t[u].fl)
{
t[ls].sum = t[rs].sum = 0;
t[ls].fl = t[rs].fl = 1;
t[u].fl = 0;
}
}
int a[N];
inline int query (int u, int l, int r, int L, int R)
{
#ifndef Judge_Online
if (u == 1)
{
printf("Now : \n");
fo (i, 0, xmax) printf("%d ", a[i]);
puts("");
}
#endif
if (l <= L && R <= r) return t[u].sum;
pushdown(u);
int mid = L + R >> 1, ret = 0;
if (l <= mid) ret += query(ls, l, r, L, mid);
if (mid < r) ret += query(rs, l, r, mid + 1, R);
return ret;
}
inline void clean (int l, int r)
{
fo (i, l, r) a[i] = 0;
printf("clean[%d, %d] : \n", l, r);
fo (i, 0, xmax) printf("%d ", a[i]); puts("");
}
inline void addpoint (int p, int val, int opt)
{
opt ? a[p] = val : a[p] += val;
printf("add(%d) = %d\n", p, val);
fo (i, 0, xmax) printf("%d ", a[i]); puts("");
}
inline void modify0 (int u, int l, int r, int L, int R)
{
#ifndef Judge_Online
if (u == 1) clean(l, r);
#endif
if (l <= L && R <= r) {t[u].fl = 1; t[u].sum = 0; return;}
pushdown(u);
int mid = L + R >> 1;
if (l <= mid) modify0(ls, l, r, L, mid);
if (mid < r) modify0(rs, l, r, mid + 1, R);
t[u].sum = t[ls].sum + t[rs].sum;
}
inline void add (int u, int pos, int val, int L, int R, int opt)
{
#ifndef Judge_Online
if (u == 1) addpoint(pos, val, opt);
#endif
if (L == R) {opt ? t[u].sum = val : t[u].sum += val; return;}
pushdown(u);
int mid = L + R >> 1;
if (pos <= mid) add(ls, pos, val, L, mid, opt);
else add(rs, pos, val, mid + 1, R, opt);
t[u].sum = t[ls].sum + t[rs].sum;
}
std::set<int> s;
std::map<std::pair<int, int>, int> p;
int main ()
{
scanf("%d", &T);
fo (i, 1, T)
{
int x1, y1, x2, y2;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
b[++tot] = (block) {x1, x2, y1 - 1, i, -1};
b[++tot] = (block) {x1, x2, y2, i, 1};
p[mp(x1 - 1, y1 - 1)] = i;
ymax = std::max(ymax, y2); xmax = std::max(xmax, x2);
}
scanf("%d", &m); fo (i, 1, m) {scanf("%d %d", &f[i].x, &f[i].y); ymax = std::max(ymax, f[i].y); xmax = std::max(xmax, f[i].x);}
scanf("%d", &n); fo (i, 1, n) {scanf("%d %d", &c[i].x, &c[i].y); ymax = std::max(ymax, c[i].y); xmax = std::max(xmax, c[i].x); c[i].id = i;}
std::sort(b + 1, b + tot + 1); std::sort(f + 1, f + m + 1); std::sort(c + 1, c + n + 1);
s.insert(0); s.insert(xmax + 2); int on = n;
T = tot;
fd (y, ymax, 1)
{
while (y == b[T].y)
{
if (b[T].opt == 1)
{
int r = *s.upper_bound(b[T].r + 1) - 1;
rd[b[T].id] = query(1, b[T].r + 1, r, 1, xmax);
r = *s.upper_bound(b[T].l - 1) - 1;
int nans = query(1, b[T].l - 1, r, 1, xmax);
add(1, b[T].l - 1, nans, 1, xmax, 1);
s.insert(b[T].l); s.insert(b[T].r + 1);
}
else
{
s.erase(b[T].l); s.erase(b[T].r + 1);
add(1, b[T].l - 1, -rd[b[T].id], 1, xmax, 0);
}
modify0(1, b[T].l, b[T].r, 1, xmax);
--T;
}
while (y == f[m].y)
{
int l = *(--s.upper_bound(f[m].x));
add(1, f[m].x, 1, 1, xmax, 0);
// add(1, l, -1, 1, xmax, 0);
--m;
}
while (y == c[n].y)
{
int r = *s.upper_bound(c[n].x) - 1, now;
ans[c[n].id] = query(1, c[n].x, r, 1, xmax);
--n;
}
}
fo (i, 1, on) {printf("%d\n", ans[i]);}
return 0;
}
话说这个东西似乎在 luogu 不管用了
#ifndef Online_Judge
#endif
我以为我记错了就把 Judge_Online 也试了一遍结果还是答案出锅
算了反正自己加一下也没什么麻烦的呢
(如果 xzy 大佬还在的话肯定会喷死我的毒瘤压行 233333)
0 条评论