[2019南京网络赛-A] The beautiful values of the palace

发表于 | 更新于 | 分类于 ， ，
本文字数： 15k

链接

\(\text{2019南京网络赛-A.The beautiful values of the palace}\)

题意

  有一个\(n\times n\)的螺旋数字矩阵，\(n\)一定是奇数，若边长为5则如下：

  这个矩阵内有\(m\)个点是有效的（即有一个值为对应螺旋矩阵该位置的值），其他位置都为0。现在有\(p\)次查询\((x1,y1,x2,y2)\)，询问\((x1,y1,)、(x2,y2)\)所围成的矩阵之间的所有数的数位和的和是多少。

  输入格式：共\(t\)组测试样例，每组样例，第一行三个数\(n,m,p\)，接下来\(m\)行，每行一组坐标\((x,y)\)，告诉\(m\)个有效点，之后\(p\)行，每行一次查询\((x1,y1,x2,y2)\)。

  数据范围：\((t\leq 5,n\leq 10^6),(m,p\leq 10^5)\).

  输出格式：每行输出一个查询结果。

分析

  螺旋矩阵\((x,y)\)位置的数的计算，这里就不解释了。

  看网上说这就是一个二维偏序问题，个人理解：逆序数的求解应该是算是一个一维偏序问题。对于二维偏序问题可以通过对\(x\)来排序，就是一个一维偏序问题了。

  设\(sum(x,y)\)表示以\((1,1)\)为左下角，以\((x,y)\)为右上角所包含所有数的数位和的和，对于查询\((x1,y1,x2,y2)\)即要求 \[sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1)\]

  我们就可以把这个查询表示成四个三元组（1为加，-1为减） \[(x2,y2,1),(x1-1,y2,-1),(x2,y1-1,-1),(x1-1,y1-1,1)\]

  之后我们将这些每个查询所表示的四个三元组以及\(m\)个有效点的插入在一起按照\(x\)来排序（即离线），我们用树状数组来维护\(sum(x,y)\)（由于\(x\)是升序排列，因此我们只需要使用一个一维数组维护\(1-y\)的数的数位和的和），我们遍历所有离线的操作，如果当前操作是插入\((x,y)\)，那么我们就在树状数组的\(y\)位置插入\((x,y)\)位置的数的数位和，对于查询操作细节见代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t, n, m, p, c[1000006], res[100005];

struct node{
    ll x, y, id, va;
    bool operator<(const node & a)const {
        if (a.x != x)return a.x > x;
        if (a.y != y)return a.y > y;
        return a.id > id;
    }
}ct[1000005];

ll QV(ll x,ll y){//求美丽值
    ll mi,ans=0;
    x=n-x+1;y=n-y+1;
    mi=min(x,min(y,min(n-x+1,n-y+1)));
    if(x<=y)
        ans=mi*(4*(n-1)-4*mi)+10*mi-4*n-3+x+y;
    else
        ans=mi*(4*n-4*mi)+2*mi+1-x-y;//模拟过程
    ll res=0;
    while(ans){
        res+=(ans%10);ans/=10;
    }
    return res;
}

int read(){
    int x = 0, f = 1;
    char c =getchar();
    while(c < '0' || c > '9') {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <='9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
void insert(int x, int val) {
    for (int i = x; i < n + 3; i += i & -i)
        c[i] += val;
}

ll sum(int x) {
    if (x == 0) return 0;
    ll ans = 0;
    for (int i = x; i > 0; i -= i & -i)
        ans += c[i];
    return ans;
}

int main() {
    t = read();
    while (t--) {
        memset(c, 0, sizeof(c));
        memset(ct, 0, sizeof(ct));
        memset(res, 0, sizeof(res));
        n = read(), m = read(), p = read();
        for (int i = 1; i <= m;i++)
            ct[i].x = read(), ct[i].y = read();
        int x1, x2, y1, y2, cnt = m;
        for (int i = 1; i <= p; i++) {
            x1 = read(), y1 = read(), x2 = read(), y2 = read();
            ct[++cnt].x = x2, ct[cnt].y = y2, ct[cnt].id = i, ct[cnt].va = 1;
            ct[++cnt].x = x1 - 1, ct[cnt].y = y1 - 1, ct[cnt].id = i, ct[cnt].va = 1;
            ct[++cnt].x = x1 - 1, ct[cnt].y = y2, ct[cnt].id = i, ct[cnt].va = -1;
            ct[++cnt].x = x2, ct[cnt].y = y1 - 1, ct[cnt].id = i, ct[cnt].va = -1;
        }
        sort(ct + 1, ct + 1 + cnt);
        for (int i = 1; i <= cnt; i++) {
            if (ct[i].id == 0) {
                int val = QV(ct[i].x, ct[i].y);
                insert(ct[i].y, val);
            }else {
	            //ct[i].va为1则是加，为-1则是减
                res[ct[i].id] += 1ll * ct[i].va * sum(ct[i].y);
            }
        }
        for (int i = 1; i <= p; i++)
            printf("%lld\n", res[i]);
    }
}