2019ICPC南京網(wǎng)絡(luò)賽A題

The beautiful values of the palace

https://nanti.jisuanke.com/t/41298

Here is a square matrix of n * nn?n, each lattice has its value (nn must be odd), and the center value is n * nn?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 mm 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 123213123213,the beautiful values of the palace located on it is 1+2+3+2+1+3=121+2+3+2+1+3=12) (666666 -> 1818) (456456 ->1515)

Next, we ask pp times to the sum of the beautiful values of the palace in the matrix where the lower left grid(x_1,y_1x1,y1), the upper right square (x_2,y_2x2,y2).

Input

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

The next line is three number: n ?m ?pn m p

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

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

Output

Next, p_1+p_2...+p_Tp1+p2...+*p**T* lines: Represent the answer in turn(n \le 10^6)(m , p \le 10^5)(n≤106)(m,p≤105)

樣例輸入復(fù)制

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

樣例輸出復(fù)制

5 18 23 17

思路：

三維偏序的題目

首先根據(jù)推公式可以把每一個(gè)點(diǎn)在螺旋矩陣中對(duì)應(yīng)的數(shù)值求出。

然后我們把m個(gè)點(diǎn)當(dāng)做成m個(gè)加點(diǎn)操作，

p個(gè)詢問，每一個(gè)詢問分解為4個(gè)子詢問，對(duì)同一個(gè)答案計(jì)算貢獻(xiàn)。

因?yàn)楦鶕?jù)容斥原理，我們可以把求二維前綴和分解為4個(gè)以左下角點(diǎn)為（0，0）的4個(gè)前綴和來處理。，

然后對(duì)x，y進(jìn)行排序，

坐標(biāo)相同時(shí)，一定要加點(diǎn)的操作排在詢問前面。

然后用樹樁數(shù)組來維護(hù)偏序問題即可。

代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define sz(a) int(a.size()) #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl #define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c)) #define du2(a,b) scanf("%d %d",&(a),&(b)) #define du1(a) scanf("%d",&(a)); using namespace std; typedef long long ll; 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) {a %= MOD; if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;} void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}} void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}inline void getInt(int *p); const int maxn = 1000010; const int inf = 0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ll tree[maxn]; int lowbit(int x) {return -x & x; } ll ask(int x) {ll res = 0ll;while (x) {res += tree[x];x -= lowbit(x);}return res; } void add(int x, ll val) {while (x < maxn) {tree[x] += val;x += lowbit(x);} } ll re_val(ll x) {ll sum = 0;while (x > 0) {sum += x % 10;x /= 10;}return sum; } long long index(long long y, long long x, long long n) {long long mid = (n + 1) / 2;long long p = max(abs(x - mid), abs(y - mid));long long ans = n * n - (1 + p) * p * 4;long long sx = mid + p, sy = mid + p;if (x == sx && y == sy) {return ans;} else {if (y == sy || x == sx - 2 * p) {return ans + abs(x - sx) + abs(y - sy);} else {return ans + 8 * p - abs(x - sx) - abs(y - sy);}} } int tot; struct node {int type;int id;ll k;ll x, y;ll val;node() {}node(int tt, int idd, ll kk, ll xx, ll yy, ll vv){id = idd;type = tt;k = kk;x = xx;y = yy;val = vv;} } a[maxn]; bool cmp(node aa, node bb) {if (aa.y != bb.y) {return aa.y < bb.y;} else if (aa.x != bb.x) {return aa.x < bb.x;} else {return aa.type < bb.type;} } ll ans[maxn]; void solve() {repd(i, 1, tot) {if (a[i].type) {ans[a[i].id] += a[i].k * ask(a[i].x);} else {add(a[i].x, a[i].val);}} } int main() {//freopen("D:\\code\\text\\input.txt","r",stdin);//freopen("D:\\code\\text\\output.txt","w",stdout);int t;du1(t);while (t--) {int n, m, p;du3(n, m, p);MS0(tree);tot = 0;repd(i, 1, m) {int x, y;du2(x, y);ll val = re_val(index(x, y, n));a[++tot] = node(0, 0, 1ll, x, y , val);}repd(i, 1, p) {ans[i] = 0ll;int lx, ly, rx, ry;du3(lx, ly, rx); du1(ry);a[++tot] = node(1, i, 1ll, rx, ry , 0);a[++tot] = node(1, i, 1ll, lx - 1, ly - 1 , 0);a[++tot] = node(1, i, -1ll, rx, ly - 1 , 0);a[++tot] = node(1, i, -1ll, lx - 1, ry , 0);}sort(a + 1, a + 1 + tot, cmp);solve();repd(i, 1, p) {printf("%lld\n", ans[i] );}}return 0; }inline void getInt(int *p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}} else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

轉(zhuǎn)載于:https://www.cnblogs.com/qieqiemin/p/11580810.html

總結(jié)

以上是生活随笔為你收集整理的2019ICPC南京网络赛A题 The beautiful values of the palace(三维偏序)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。