ICPC南京网络赛A.The beautiful values of the palace

发表于 | 阅读数

题意:给一个蛇形矩阵规律求给定矩形内的值总和

我们可以先把中心点当作1这样好找规律

首先我们先确定这个数是在$x$还是在$y$上连续那段。

如果$|\Delta x|>|\Delta y|$就在$x$行

同理可推出

然后就是裸的二维数点或者CDQ二维偏序

代码 
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
typedef long long ll;
ll tr[N], ans[N];
int cnt, li[N], n, m, cntl;
ll calc(int x, int y)
{
    ll xx = x - n / 2 - 1;
    ll yy = y - n / 2 - 1;
    if (abs(xx) > abs(yy))
    {
        if (xx < 0)
            return -xx * (-4 * xx - 1) + 1 - yy;
        else
            return xx * (4 * xx + 3) + 1 + yy;
    }
    else
    {
        if (xx == yy && xx > 0)
            return (xx * 2 + 1) * (2 * xx + 1);
        if (yy < 0)
            return -yy * (-4 * yy + 1) + 1 + xx;
        else
            return yy * (4 * yy - 3) + 1 - xx;
    }
}
int get(int x, int y)
{
    ll ans = 1ll * n * n - calc(x, y) + 1;
    int res = 0;
    while (ans)
    {
        res += ans % 10;
        ans /= 10;
    }
    return res;
}
struct node
{
    int x, y, id;
    ll flag;
} q[N], a[N];
bool cmp(node c, node d)
{
    return c.x < d.x;
}
int lowbit(int x)
{
    return (-x) & x;
}
void update(int x, ll w)
{
    while (x <= cntl)
    {
        tr[x] += w;
        x += lowbit(x);
    }
}

ll quary(ll x)
{
    ll sum = 0;
    while (x)
    {
        sum += tr[x];
        x -= lowbit(x);
    }
    return sum;
}

void add(int x, int y, int id, int flag)
{
    q[++cnt].x = x;
    q[cnt].y = y;
    q[cnt].id = id;
    q[cnt].flag = flag;
    li[++cntl] = y;
}
int k, T;
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        cnt = 0;
        cntl = 0;
        memset(a, 0, sizeof(a));
        memset(q, 0, sizeof(q));
        memset(li, 0, sizeof(li));
        memset(ans, 0, sizeof(ans));
        memset(tr, 0, sizeof(tr));
        scanf("%d%d%d", &n, &k, &m);
        for (int i = 1; i <= k; i++)
            scanf("%d%d", &a[i].x, &a[i].y), a[i].flag = get(a[i].x, a[i].y), li[++cntl] = a[i].y;
        for (int i = 1; i <= m; i++)
        {
            int x1, x2, y1, y2;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            add(x1 - 1, y1 - 1, i, 1);
            add(x2, y2, i, 1);
            add(x1 - 1, y2, i, -1);
            add(x2, y1 - 1, i, -1);
        }
        sort(li + 1, li + 1 + cntl);
        cntl = unique(li + 1, li + cntl + 1) - li - 1;

        for (int i = 1; i <= 4 * m; i++)
            q[i].y = lower_bound(li + 1, li + cntl + 1, q[i].y) - li;
        for (int i = 1; i <= k; i++)
            a[i].y = lower_bound(li + 1, li + cntl + 1, a[i].y) - li;
        sort(1 + q, q + 1 + 4 * m, cmp);
        sort(1 + a, 1 + a + k, cmp);

        int num = 1;

        for (int i = 1; i <= 4 * m; i++)
        {
            //cout<<q[i].y<<endl;
            while (num <= k && a[num].x <= q[i].x)
                update(a[num].y, a[num].flag), num++;
            //cout<<quary(q[i].y) <<" "<<q[i].flag<<endl;
            ans[q[i].id] += 1ll * quary(q[i].y) * q[i].flag;
        }
        for (int i = 1; i <= m; i++)
            printf("%lld\n", ans[i]);
    }
}