P2163 [SHOI2007]園丁的煩惱

題目描述

很久很久以前，在遙遠的大陸上有一個美麗的國家。統治著這個美麗國家的國王是一個園藝愛好者，在他的皇家花園里種植著各種奇花異草。

有一天國王漫步在花園里，若有所思，他問一個園丁道： “最近我在思索一個問題，如果我們把花壇擺成六個六角形，那么……”

“那么本質上它是一個深度優先搜索，陛下”，園丁深深地向國王鞠了一躬。

“嗯……我聽說有一種怪物叫九頭蛇，它非常貪吃蘋果樹……”

“是的，顯然這是一道經典的動態規劃題，早在N元4002年我們就已經發現了其中的奧秘了，陛下”。

“該死的，你究竟是什么來頭？”

“陛下息怒，干我們的這行經常莫名其妙地被問到和OI有關的題目，我也是為了預防萬一啊！” 王者的尊嚴受到了傷害，這是不可容忍的。

看來一般的難題是難不倒這位園丁的，國王最后打算用車輪戰來消耗他的實力： “年輕人，在我的花園里的每一棵樹可以用一個整數坐標來表示，一會兒，我的騎士們會來輪番詢問你某一個矩陣內有多少樹，如果你不能立即答對，你就準備走人吧！”說完，國王氣呼呼地先走了。

這下輪到園丁傻眼了，他沒有準備過這樣的問題。所幸的是，作為“全國園丁保護聯盟”的會長——你，可以成為他的最后一根救命稻草。

輸入格式

第一行有兩個整數n，m（0≤n≤500000，1≤m≤500000）。n代表皇家花園的樹木的總數，m代表騎士們詢問的次數。

文件接下來的n行，每行都有兩個整數xi，yi，代表第i棵樹的坐標（0≤xi，yi≤10000000）。

文件的最后m行，每行都有四個整數aj，bj，cj，dj，表示第j次詢問，其中所問的矩形以（aj，bj）為左下坐標，以（cj，dj）為右上坐標。

輸出格式

共輸出m行，每行一個整數，即回答國王以（aj，bj）和（cj，dj）為界的矩形里有多少棵樹。

輸入輸出樣例

輸入 #1復制

3 1 0 0 0 1 1 0 0 0 1 1

輸出 #1復制

3

思路：

三維偏序解決二維平面中矩形包括多少個點數問題。

維度：

{

? x軸

? y軸

? 操作類型

}

我們把初始給定的n個點轉為向坐標系中加點的操作

m個詢問轉為詢問問題。

那么按照x，y升序排序，想x和y都相等時，加點的操作優先。

通過二維前綴和性質，把詢問分解為四個（0,0）節點為左下角子詢問積累貢獻求得。

排序后，利用樹樁數組來維護答案。

代碼：

#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 = 3000010; 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; } int my=0; void add(int x, ll val) {while (x < my) {tree[x] += val;x += lowbit(x);} } pii a[maxn]; pii b[maxn]; pii c[maxn]; int n, m; std::vector<int> vx,vy; struct node {int op;int x, y;int k;int id;node() {}node(int opp, int xx, int yy, int kk, int idd){op = opp;x = xx;y = yy;k = kk;id = idd;} } info[maxn]; int ans[maxn]; bool cmp(node aa, node bb) {if (aa.x != bb.x) {return aa.x < bb.x;} else if (aa.op != bb.op) {return aa.op < bb.op;} else {return aa.y < bb.y;} } int main() {//freopen("D:\\code\\text\\input.txt","r",stdin);//freopen("D:\\code\\text\\output.txt","w",stdout);gbtb;cin >> n >> m;repd(i, 1, n) {cin >> a[i].fi >> a[i].se;vx.push_back(a[i].fi);vy.push_back(a[i].se);}repd(i, 1, m) {cin >> b[i].fi >> b[i].se >> c[i].fi >> c[i].se;vx.push_back(b[i].fi);vy.push_back(b[i].se);vx.push_back(c[i].fi);vy.push_back(c[i].se);vy.push_back(b[i].se - 1);vx.push_back(b[i].fi - 1);}sort(ALL(vx));sort(ALL(vy));vx.erase(unique(ALL(vx)),vx.end());vy.erase(unique(ALL(vy)),vy.end());my=sz(vy)+10;int cnt = 0;int dx, dy;repd(i, 1, n) {++cnt;dx = lower_bound(ALL(vx), a[i].fi) - vx.begin() + 1;dy = lower_bound(ALL(vy), a[i].se) - vy.begin() + 1;info[cnt] = node(0, dx, dy, 0, 0);}repd(i, 1, m) {++cnt;dx = lower_bound(ALL(vx), c[i].fi) - vx.begin() + 1;dy = lower_bound(ALL(vy), c[i].se) - vy.begin() + 1;info[cnt] = node(1, dx, dy, 1, i);++cnt;dx = lower_bound(ALL(vx), c[i].fi) - vx.begin() + 1;dy = lower_bound(ALL(vy), b[i].se - 1) - vy.begin() + 1;info[cnt] = node(1, dx, dy, -1, i);++cnt;dx = lower_bound(ALL(vx), b[i].fi - 1) - vx.begin() + 1;dy = lower_bound(ALL(vy), c[i].se) - vy.begin() + 1;info[cnt] = node(1, dx, dy, -1, i);++cnt;dx = lower_bound(ALL(vx), b[i].fi-1) - vx.begin() + 1;dy = lower_bound(ALL(vy), b[i].se-1) - vy.begin() + 1;info[cnt] = node(1, dx, dy, 1, i);}sort(info + 1, info + 1 + cnt, cmp);repd(i, 1, cnt) {if (!info[i].op) {add(info[i].y, 1);} else {ans[info[i].id] += info[i].k * ask(info[i].y);}}repd(i, 1, m) {printf("%d\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/11594591.html

總結

以上是生活随笔為你收集整理的洛谷 P2163 [SHOI2007]园丁的烦恼 （离线sort，树状数组，解决三维偏序问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

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