The beautiful values of the palace（找规律+离散化）

T: 1500ms

M: 524288K

judge:计蒜客

source:The Preliminary Contest for ICPC Asia Nanjing 2019

Description

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

The beautiful values of the palace（找规律+离散化）

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 m m m 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 123213 123213 123213,the beautiful values of the palace located on it is 1 + 2 + 3 + 2 + 1 + 3 = 12 ) ( 666 − > 18 ) ( 456 − > 15 ) 1+2+3+2+1+3=12) (666 -> 18) (456 ->15) 1+2+3+2+1+3=12)(666−>18)(456−>15)

Next, we ask p p p times to the sum of the beautiful values of the palace in the matrix where the lower left grid ( x 1 , y 1 ) (x_1,y_1) (x1,y1), the upper right square ( x 2 , y 2 ) (x_2,y_2) (x2,y2).

Input

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

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

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

The pp lines follow, each line contains four integers : the lower left grid ( x 1 , y 1 ) (x_1,y_1) (x1,y1) the upper right square ( x 2 , y 2 ) (x_2,y_2) (x2,y2)

Output

Next, p 1 + p 2 . . . + p T p_1+p_2...+p_T p1+p2...+pT lines: Represent the answer in turn ( n ≤ 1 0 6 ) ( m , p ≤ 1 0 5 ) (n \le 10^6)(m , p \le 10^5) (n≤106)(m,p≤105)

样例输入

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

样例输出

5

18

23

17

题意

给你一个宽度为奇数的正方形，每个块都有一定的权值，把权值的每一位加起来得到每一个块的“美丽值”。现在告诉你正方形中有一些块上面建造的有宫殿，然后问你在某一个矩形区域内所有宫殿的“美丽值”的总和。

不会做，遂搜了一下题解，看完拍案叫绝！忍不住写一篇博客纪念……

先找出规律可以 O ( 1 ) O(1) O(1)求出某一个块的权值：

先求出目标块在哪一圈层，然后判断在所在圈的哪一侧边，分类计算即可。

代码：

LL getval(LL x, LL y, LL n) {
	LL t = min(min(x, y), min(n - x + 1, n - y + 1));
	LL ta = 4 * (t - 1) * (n - t + 1);
	if (x == n - t + 1) ta += n - t - y + 2;//在所在圈层的右侧边
	else if (x == t) ta += 2 * n - 5 * t + y + 3;//左侧边
	else if (y == t) ta += 2 * n - 3 * t - x + 3;//下侧边
	else ta += 3 * n - 7 * t + x + 4;//上侧边
	return ta;
}

因为数据太大，离散化不能用二维数组，可以把所有的点和要查询的前缀和按x值排序，然后从头到尾遍历一遍，如果遇到点就压入树状数组，如果是前缀和就用树状数组求出前缀和。这样就可以用时间来区分x，用树状数组来区分y。

代码

#include <bits/stdc++.h>
#define maxn 1000005
#define lowbit(x) ((x)&(-x))
#define _for(i, a) for(LL i = 0; i < (a); i++)
#define _rep(i, a, b) for(LL i = (a); i <= (b); i++)
typedef long long LL;
using namespace std;

struct poi {
	LL x, y, flag, pos, val;
	poi() {}
	poi(LL x, LL y, LL flag, LL pos, LL val) :x(x), y(y), flag(flag), pos(pos), val(val) {}
	bool operator < (poi t) {
		if (x != t.x) return x < t.x;
		if (y != t.y) return y < t.y;
		return pos < t.pos;
	}
};

LL getval(LL x, LL y, LL n) {
	LL t = min(min(x, y), min(n - x + 1, n - y + 1));
	LL ta = 4 * (t - 1) * (n - t + 1);
	if (x == n - t + 1) ta += n - t - y + 2;//在所在圈层的右侧边
	else if (x == t) ta += 2 * n - 5 * t + y + 3;//左侧边
	else if (y == t) ta += 2 * n - 3 * t - x + 3;//下侧边
	else ta += 3 * n - 7 * t + x + 4;//上侧边
	return ta;
}

LL T[maxn * 2];

LL getnum(LL x, LL n) {
	LL ans = 0;
	while (x > 0) {
		ans += T[x];
		x -= lowbit(x);
	}
	return ans;
}

void upd(LL x, LL y, LL n) {
	while (x <= n) {
		T[x] += y;
		x += lowbit(x);
	}
}

LL n, m, p;
LL cnt = 0;
poi a[maxn * 2];
LL ans[maxn];

void init() {
	//初始化
	memset(T, 0, sizeof(T));
	memset(ans, 0, sizeof(ans));
	cnt = 0;
}

int main() {
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

	LL T;
	cin >> T;
	while (T--) {
		init();

		cin >> n >> m >> p;
		_for(i, m) {
			//求出点的美丽值 并把点压入队列
			LL x, y;
			cin >> x >> y;
			LL tt = getval(x, y, n), _tem = 0;
			while (tt) {//求出美丽值
				_tem += tt % 10;
				tt /= 10;
			}
			a[cnt++] = poi(x, y, 0, i, _tem);
		}
		_rep(i, m, m + p - 1) {
			//把区间拆解为4个前缀和，一块压入队列，用flag区分是加还是减
			LL x1, y1, x2, y2;
			cin >> x1 >> y1 >> x2 >> y2;
			a[cnt++] = poi(x1 - 1, y1 - 1, 1, i, 0);
			a[cnt++] = poi(x2, y1 - 1, -1, i, 0);
			a[cnt++] = poi(x1 - 1, y2, -1, i, 0);
			a[cnt++] = poi(x2, y2, 1, i, 0);
		}
		sort(a, a + cnt);

		//以时间来区分x，以树状数组来区分y
		_for(i, cnt) {
			if (a[i].pos < m) {
				//说明是点，不是区间
				upd(a[i].y, a[i].val, n);
			}
			else {
				//是区间，要我们求前缀和
				ans[a[i].pos - m] += getnum(a[i].y, n) * a[i].flag;
			}
		}
		_for(i, p) {
			cout << ans[i] << "\n";
		}
	}
	return 0;
}

The beautiful values of the palace（找规律+离散化）