题解：P14264 [ROI 2015 Day1] 珍珠刺绣

· · 题解

这不是一个诈骗题，这是一道 思维题。

首先，需要注意题目描述中的 图是一棵树。可以思考连通块数量可以如何转换。一棵树显然为一个连通块，我们发现：

1=n-(n-1)

作为拉马努金兼欧拉，我们可以观察到这个性质可以扩展，即对于任意一个 无环图 G，设点数为 V，边数为 E，连通块数量 为 C，则有：

C=V-E

所以对于每个矩阵中对于连通块数量的询问，我们只需计算边数与点数即可。

两者本质一致，于是得到了一道 二维前缀和 模板题。但是由于空间复杂度超标，所以转换为 二维数点，具体实现自己参见数据结构专题。

对于边界处理，即有些边可能有一半在区域里，以横向边距离，我们考虑记录边右边的点，算答案的时候只需将左边界右移一格进行处理即可。

警示后人：x1、y1 为关键字，数组不能开小。

完结撒花，欢迎点赞。

#pragma GCC optimize("Ofast", 3)

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define x1 ioeuryieu
#define y1 dlfihwepu

ll read() {
    char c;
    bool isf = 0;
    while (!isdigit(c = getchar())) isf = (c == '-');
    ll res = (c ^ 48);
    while (isdigit(c = getchar())) res = (res << 3) + (res << 1) + (c ^ 48);
    return isf ? -res : res;
}

void write(ll x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x >= 10)
        write(x / 10);
    putchar('0' + x % 10);
}

void openf(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const ll N = 150005;

struct bit {
    ll tr[N << 2];
    void add(ll x, ll k) {
        for (; x < N; x += x & -x) {
            tr[x] += k;
        }
    }
    ll ask(ll x, ll res = 0) {
        for (; x > 0; x -= x & -x) {
            res += tr[x];
        }
        return res;
    }
} E[2], V;

struct query {
    ll x, y, f, id;
} que[N << 4];

bool cmp(query q1, query q2) {
    if (q1.x != q2.x) {
        return q1.x < q2.x;
    } else if (q1.y != q2.y) {
        return q1.y < q2.y;
    }
    return q1.f > q2.f;
}

ll a, b, n, q, tot, ans[N];
map<pair<ll, ll>, ll > f;

void solve() {
    cin >> a >> b >> n >> q;
    for (ll i = 1; i < n; i++) {
        char c;
        ll x, y;
        cin >> c >> x >> y;
        if (c == 'v') {
            if (!f[{ x, y }]) {
                tot++;
                que[tot] = { x, y, 4, 0 };
                f[{ x, y }] = 1;
            }
            if (!f[{ x, y + 1 }]) {
                tot++;
                que[tot] = { x, y + 1, 4, 0 };
                f[{ x, y + 1 }] = 1;
            }
            tot++;
            que[tot] = { x, y + 1, 6, 0 };
        } else {
            if (!f[{ x, y }]) {
                tot++;
                que[tot] = { x, y, 4, 0 };
                f[{ x, y }] = 1;
            }
            if (!f[{ x + 1, y }]) {
                tot++;
                que[tot] = { x + 1, y, 4, 0 };
                f[{ x + 1, y }] = 1;
            }
            tot++;
            que[tot] = { x + 1, y, 5, 0 };
        }
    }
    for (ll i = 1; i <= q; i++) {
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        tot++;
        que[tot] = { x2, y2, 1, i };
        tot++;
        que[tot] = { x2, y1 - 1, -1, i };
        tot++;
        que[tot] = { x1 - 1, y2, -1, i };
        tot++;
        que[tot] = { x1 - 1, y1 - 1, 1, i };
        x1++;
        tot++;
        que[tot] = { x2, y2, -2, i };
        tot++;
        que[tot] = { x2, y1 - 1, 2, i };
        tot++;
        que[tot] = { x1 - 1, y2, 2, i };
        tot++;
        que[tot] = { x1 - 1, y1 - 1, -2, i };
        x1--, y1++;
        tot++;
        que[tot] = { x2, y2, -3, i };
        tot++;
        que[tot] = { x2, y1 - 1, 3, i };
        tot++;
        que[tot] = { x1 - 1, y2, 3, i };
        tot++;
        que[tot] = { x1 - 1, y1 - 1, -3, i };
    }
    stable_sort(que + 1, que + tot + 1, cmp);
    for (ll i = 1; i <= tot; i++) {
        query qu = que[i];
        if (qu.f == 6) {
            E[1].add(qu.y, 1);
        } else if (qu.f == 5) {
            E[0].add(qu.y, 1);
        } else if (qu.f == 4) {
            V.add(qu.y, 1);
        } else if (abs(qu.f) == 1) {
            ans[qu.id] += qu.f * V.ask(qu.y);
        } else if (abs(qu.f) == 2) {
            ans[qu.id] += qu.f / 2 * E[0].ask(qu.y);
        } else if (abs(qu.f) == 3) {
            ans[qu.id] += qu.f / 3 * E[1].ask(qu.y);
        }
    }
    for (ll i = 1; i <= q; i++) {
        cout << ans[i] << '\n';
    }
}

int main() {
    solve();
    return 0;
}