題目描述

摩爾瓦多的移動電話公司摩基亞（Mokia）設計出了一種新的用戶定位系統。和其他的定位系統一樣，它能夠迅速回答任何形如“用戶C的位置在哪？”的問題，精確到毫米。但其真正高科技之處在于，它能夠回答形如“給定區域內有多少名用戶？”的問題。

在定位系統中，世界被認為是一個W×W的正方形區域，由1×1的方格組成。每個方格都有一個坐標(x,y)，1<=x,y<=W。坐標的編號從1開始。對于一個4×4的正方形，就有1<=x<=4,1<=y<=4（如圖）：

請幫助Mokia公司編寫一個程序來計算在某個矩形區域內有多少名用戶。

輸入格式

有三種命令，意義如下：

命令 參數 意義

• 0 W 初始化一個全零矩陣。本命令僅開始時出現一次。
• 1 x y A 向方格(x,y)中添加A個用戶。A是正整數。
• 2 X1 Y1 X2 Y2 查詢X1<=x<=X2，Y1<=y<=Y2所規定的矩形中的用戶數量
• 3 無參數 結束程序。本命令僅結束時出現一次。

輸出格式

對所有命令2，輸出一個一行整數，即當前詢問矩形內的用戶數量。

輸入輸出樣例

輸入 #1復制

0 4 1 2 3 3 2 1 1 3 3 1 2 2 2 2 2 2 3 4 3

輸出 #1復制

3 5

說明/提示

對于所有數據：

1<=W<=2000000
1<=X1<=X2<=W
1<=Y1<=Y2<=W
1<=x,y<=W
0<A<=10000
命令1不超過160000個。
命令2不超過10000個。

思路：

經典的CDQ解決帶修改的三維偏序問題。

第一維time，默認有序。

第二維x坐標，用歸并排序結局。

第三維y坐標，用樹狀數組維護動態前綴和。

#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 ***/ int op; int n; const int maxL = 3000010; ll tree[maxL]; 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 < maxL) {tree[x] += val;x += lowbit(x);} }struct node {int t;int op;int x, y;int k;int val;node() {}node(int tt, int oo, int xx, int yy, int kk, int vv){t = tt;op = oo;x = xx;y = yy;k = kk;val = vv;}bool operator<= (const node &bb )const{if (x != bb.x) {return x < bb.x;} else {return y <= bb.y;}} }; node a[maxn]; node b[maxn]; ll ans[maxn]; int tot; int anstot;void cdq(int l, int r) {if (l == r) {return ;}int mid = (l + r) >> 1;cdq(l, mid);cdq(mid + 1, r);int ql = l;int qr = mid + 1;repd(i, l, r) {if (qr > r || (ql <= mid && a[ql] <= a[qr])) {if (a[ql].op == 1) {add(a[ql].y, a[ql].val);}b[i] = a[ql++];} else {if (a[qr].op == 2) {ans[a[qr].val] += a[qr].k * ask(a[qr].y);}b[i] = a[qr++];}}ql = l;qr = mid + 1;repd(i, l, r) {if (qr > r || (ql <= mid && a[ql] <= a[qr])) {if (a[ql].op == 1) {add(a[ql].y, -a[ql].val);}ql++;} else {qr++;}}repd(i, l, r) {a[i] = b[i];} } int main() {//freopen("D:\\code\\text\\input.txt","r",stdin);//freopen("D:\\code\\text\\output.txt","w",stdout);while (~scanf("%d", &op)) {if (op == 0) {scanf("%d", &n);} else if (op == 1) {int x, y, c;du3(x, y, c);x++;y++;tot++;a[tot] = node(tot, 1, x, y, 0, c);} else if (op == 2) {int x1, y1, x2, y2;du2(x1, y1); du2(x2, y2);x1++;y1++;x2++;y2++;tot++;a[tot] = node(tot, 2, x1 - 1, y1 - 1, 1, ++anstot);tot++;a[tot] = node(tot, 2, x1 - 1, y2, -1, anstot);tot++;a[tot] = node(tot, 2, x2, y1 - 1, -1, anstot);tot++;a[tot] = node(tot, 2, x2, y2, 1, anstot);} else {break;}}cdq(1, tot);repd(i, 1, anstot) {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';}} }

轉載于:https://www.cnblogs.com/qieqiemin/p/11613573.html

總結

以上是生活随笔為你收集整理的P4390 [BOI2007]Mokia 摩基亚 (CDQ解决三维偏序问题)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。