2019南京网络赛A 树状数组+思维

官方题解：

代码如下：

#include<bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair<int,int>
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 1e6 + 11;
int t, n, m, p;
struct uzi {
    int a, b;
    LL data;
    int sta;
    int pos;
    int g;
    bool operator <(const uzi &t)const {
        return a < t.a;
    }
} P[N], Q[N << 2];
int CP, CR;
int T[N];
LL ans[N];
void add(int p, int d) {
    for (int i = p; i <= N; i += (i & -i))T[i] += d;
}
LL query(int p) {
    LL res = 0;
    for (int i = p; i; i -= (i & -i))res += T[i];
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    for (cin >> t; t; t--) {
        cin >> n >> m >> p;
        CP = CR = 0;
        memset(T, 0, sizeof T);
        for (int i = 1; i <= m; i++) {
            int x, y;
            cin >> x >> y;
            int X = x, Y = y;
            x = x - n / 2 - 1;
            y = y - n / 2 - 1;
            int T = max(abs(x), abs(y));
            LL res;
            if (x >= y)res = 1ll * n * n - 4ll * T * T - 2ll * T - x - y;
            else res = 1ll * n * n - 4ll * T * T + 2ll * T + x + y;
            int tmp = 0;
            while (res) {
                tmp += res % 10;
                res /= 10;
            }
            res = tmp;
            P[++CP] = {X, Y, res, 0, i, 0};
        }
        for (int i = 1; i <= p; i++) {
            int a, b, c, d;
            cin >> a >> b >> c >> d;
            Q[++CR] = {a - 1, b - 1, 0, 1, i, 1};
            Q[++CR] = {c, d, 0, 1, i, 1};
            Q[++CR] = {a - 1, d, 0, 1, i, -1};
            Q[++CR] = {c, b - 1, 0, 1, i, -1};
        }
        sort(P + 1, P + 1 + CP);
        sort(Q + 1, Q + 1 + CR);
        int now = 1;
        for (int i = 1; i <= CR; i++) {
            while (now <= CP && P[now].a <= Q[i].a) {
                add(P[now].b, P[now].data);
                ++now;
            }
            ans[Q[i].pos] += Q[i].g * query(Q[i].b);
        }
        for (int i = 1; i <= p; i++)cout << ans[i] << '\n', ans[i] = 0;
    }
    return 0;
}