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 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;
}