bzoj

luogu

说明

因为扫喵线比较可爱,所以以下称扫描线为扫喵线。

你问我标题为什么不这样改,那是因为如果这样的话不太方便查自己题解啦

题解

首先考虑暴力

紫色类型的位置 (右边和下面都没有边框),我们有转移方程

$$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)

分类: 文章

quhengyi11

AFO 有缘再见

发表评论

电子邮件地址不会被公开。 必填项已用*标注