The Preliminary Contest for ICPC Asia Nanjing 2019 A. The beautiful values of the palace

Description:

Here is a square matrix of $n * n$ , each lattice has its value ( $n$ must be odd), and the center value is $n * n$ . Its spiral decline along the center of the square matrix (the way of spiral decline is shown in the following figure:)

img

img

The grid in the lower left corner is (1,1) and the grid in the upper right corner is (n , n)

Now I can choose mm squares to build palaces, The beauty of each palace is equal to the digital sum of the value of the land which it is located. Such as (the land value is 123213123213,the beautiful values of the palace located on it is $1+2+3+2+1+3=12$) ($666$ -> $18$ ) ( $456$ -> $15$ )

Next, we ask $p$ times to the sum of the beautiful values of the palace in the matrix where the lower left grid( $x_1,y_1$ ), the upper right square ( $x_2,y_2$ ).

Input:

The first line has only one number $T$ .Representing $T$ -group of test data $(T\le 5)$

The next line is three number: $n \ m \ p$

The mm lines follow, each line contains two integers the square of the palace $(x, y )$

The pp lines follow, each line contains four integers : the lower left grid $(x_1,y_1)$ the upper right square $(x_2,y_2)$

Output:

Next, $p_1+p_2...+p_T$ lines: Represent the answer in turn $(n \le 10^6)(m , p \le 10^5)$

Sample Input:

1
3 4 4
1 1
2 2
3 3
2 3
1 1 1 1
2 2 3 3
1 1 3 3
1 2 2 3

Sample Output:

5
18
23
17

题目链接

螺旋矩阵 $m$ 个坐标 $(x,y)$ 上的点有效,$q$ 次询问,每次询问一个子矩阵内有效点数位和

坐标 $(x,y)$ 与螺旋矩阵数字相关的对应关系本博客不做讨论(这部分不是我写的

考虑如何求 $10^6 \times 10^6$ 矩阵其 $10^5$ 次子矩阵和的询问

做法是把所有询问进行离线,按照扫描线的思想从左向右扫描,用线段树维护矩阵的列前缀和处理所有询问

AC代码:

#include <bits/stdc++.h>
const int maxn = 1e6 + 5;
struct SegTree {
    int n;
    long long tree[maxn * 4];
    void Pull(int o) {
        tree[o] = tree[o * 2] + tree[o * 2 + 1];
    }
    void Build(int o, int l, int r) {
        tree[o] = 0;
        if (l == r) return;
        int m = (l + r) / 2;
        Build(o * 2, l, m);
        Build(o * 2 + 1, m + 1, r);
        Pull(o);
    }
    void Init(int _n) {
        n = _n;
        Build(1, 1, n);
    }
    void Modify(int o, int l, int r, int idx, int v) {
        if (l == r) {
            tree[o] += v;
            return;
        }
        int m = (l + r) / 2;
        if (idx <= m) Modify(o * 2, l, m, idx, v);
        else Modify(o * 2 + 1, m + 1, r, idx, v);
        Pull(o);
    }
    void Modify(int idx, long long v) {
        Modify(1, 1, n, idx, v);
    }
    long long Query(int o, int l, int r, int ll, int rr) {
        if (ll <= l && rr >= r) return tree[o];
        int m = (l + r) / 2;
        long long ret = 0;
        if (ll <= m) ret += Query(o * 2, l, m, ll, rr);
        if (rr > m) ret += Query(o * 2 + 1, m + 1, r, ll, rr);
        return ret;
    }
    long long Query(int ll, int rr) {
        return Query(1, 1, n, ll, rr);
    }
};
long long Gao(int x, int y, int n) {
    --x, --y;
    int p = std::min({x, y, n - x - 1, n - y - 1}), q = n - p - 1;
    long long base = (long long)(n) * n - (long long)(n - 2 * p) * (long long)(n - 2 * p) + 1;
    if (x == q) return base + (q - y);
    base += n - 2 * p - 1;
    if (y == p) return base + (q - x);
    base += n - 2 * p - 1;
    if (x == p) return base + (y - p);
    base += n - 2 * p - 1;
    return base + (x - p);
}
int Get(long long x) {
    int ret = 0;
    while (x) {
        ret += x % 10;
        x /= 10;
    }
    return ret;
}
SegTree T;
struct query { int l, r, id; };
std::vector<std::pair<int, int>> ele[maxn];
std::vector<query> sub[maxn], add[maxn];
long long ans[maxn];
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    for (int cas = 1; cas <= t; ++cas) {
        int n, m, q;
        std::cin >> n >> m >> q;
        for (int i = 0; i < maxn; ++i) ele[i].clear();
        for (int i = 1, x, y; i <= m; ++i) {
            std::cin >> x >> y;
            ele[x].push_back({y, Get(Gao(x, y, n))});
        }
        for (int i = 0; i < maxn; ++i) sub[i].clear(), add[i].clear();
        for (int i = 1, x1, y1, x2, y2; i <= q; ++i) {
            std::cin >> x1 >> y1 >> x2 >> y2;
            sub[x1 - 1].push_back((query){y1, y2, i});
            add[x2].push_back((query){y1, y2, i});
        }
        T.Init(maxn - 1);
        for (int i = 1; i <= q; ++i) ans[i] = 0;
        for (int i = 0; i < maxn; ++i) {
            for (auto &v : ele[i]) T.Modify(v.first, v.second);
            for (auto &v : sub[i]) ans[v.id] -= T.Query(v.l, v.r);
            for (auto &v : add[i]) ans[v.id] += T.Query(v.l, v.r);
        }
        for (int i = 1; i <= q; ++i) std::cout << ans[i] << '\n';
    }
    return 0;
}
Last modification:September 3rd, 2019 at 01:30 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment