題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5213

莫隊(duì)算法是離線處理一類(lèi)區(qū)間不修改查詢(xún)類(lèi)問(wèn)題的算法。就是如果你知道了[L,R]的答案。你可以在O(1)的時(shí)間下得到[L,R-1]和[L,R+1]和[L-1,R]和[L+1,R]的答案的話。就可以使用莫隊(duì)算法。

對(duì)于莫隊(duì)算法我感覺(jué)就是暴力。只是預(yù)先知道了所有的詢(xún)問(wèn)。可以合理的組織計(jì)算每個(gè)詢(xún)問(wèn)的順序以此來(lái)降低復(fù)雜度。要知道我們算完[L,R]的答案后現(xiàn)在要算[L',R']的答案。由于可以在O(1)的時(shí)間下得到[L,R-1]和[L,R+1]和[L-1,R]和[L+1,R]的答案.所以計(jì)算[L',R']的答案花的時(shí)間為|L-L'|+|R-R'|。如果把詢(xún)問(wèn)[L,R]看做平面上的點(diǎn)a(L,R).詢(xún)問(wèn)[L',R']看做點(diǎn)b(L',R')的話。那么時(shí)間開(kāi)銷(xiāo)就為兩點(diǎn)的曼哈頓距離。所以對(duì)于每個(gè)詢(xún)問(wèn)看做一個(gè)點(diǎn)。我們要按一定順序計(jì)算每個(gè)值。那開(kāi)銷(xiāo)就為曼哈頓距離的和。要計(jì)算到每個(gè)點(diǎn)。那么路徑至少是一棵樹(shù)。所以問(wèn)題就變成了求二維平面的最小曼哈頓距離生成樹(shù)。

關(guān)于二維平面最小曼哈頓距離生成樹(shù)。感興趣的可以參考點(diǎn)擊打開(kāi)鏈接

這樣只要順著樹(shù)邊計(jì)算一次就ok了。可以證明時(shí)間復(fù)雜度為n*sqrt(n)這個(gè)我不會(huì)證明。

但是這種方法編程復(fù)雜度稍微高了一點(diǎn)。所以有一個(gè)比較優(yōu)雅的替代品。那就是先對(duì)序列分塊。然后對(duì)于所有詢(xún)問(wèn)按照L所在塊的大小排序。如果一樣再按照R排序。然后按照排序后的順序計(jì)算。為什么這樣計(jì)算就可以降低復(fù)雜度呢。

一、i與i+1在同一塊內(nèi)，r單調(diào)遞增，所以r是O(n)的。由于有n^0.5塊,所以這一部分時(shí)間復(fù)雜度是n^1.5。
二、i與i+1跨越一塊，r最多變化n，由于有n^0.5塊，所以這一部分時(shí)間復(fù)雜度是n^1.5
三、i與i+1在同一塊內(nèi)時(shí)變化不超過(guò)n^0.5，跨越一塊也不會(huì)超過(guò)2*n^0.5，不妨看作是n^0.5。由于有n個(gè)數(shù)，所以時(shí)間復(fù)雜度是n^1.5
于是就變成了O(n^1.5)了。

參考博客：http://blog.csdn.net/bossup/article/details/39236275

解題思路：因?yàn)橐蟮拇鸢笣M(mǎn)足區(qū)間的可加性，我們令f(l,r)表示 l到r這個(gè)區(qū)間滿(mǎn)足條件的ans,令F(l1,r1,l2,r2)為在這兩個(gè)區(qū)間內(nèi)選取的數(shù)滿(mǎn)足條件的ans，則根據(jù)容斥定理，F(l1,r1,l2,r2)=f(l1,r2)-f(r1+1,r2)-f(l1,l2-1)+f(r1+1,l2-1)。這樣就把兩個(gè)不相關(guān)的區(qū)間合并成一個(gè)可以用莫隊(duì)算法處理的區(qū)間。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;const int maxn = 30005; int n,m,k,block,a[maxn],cnt[maxn],res[maxn]; struct Query {int l,r,id,f;bool operator < (const Query rhs) const{if(l / block == rhs.l / block)return r < rhs.r;return l / block < rhs.l / block;} }q[maxn<<2];void solve() {block = sqrt(n + 0.5);sort(q,q+(m<<2));int ans = 0,l = 1,r = 0;for(int i = 0; i < (m<<2); i++){while(r > q[i].r){cnt[a[r]]--;if(k - a[r] >= 1 && k - a[r] <= n) ans -= cnt[k-a[r]];r--;}while(r < q[i].r){r++;if(k - a[r] >= 1 && k - a[r] <= n) ans += cnt[k-a[r]];cnt[a[r]]++;}while(l < q[i].l){cnt[a[l]]--;if(k - a[l] >= 1 && k - a[l] <= n) ans -= cnt[k-a[l]];l++;}while(l > q[i].l){l--;if(k - a[l] >= 1 && k - a[l] <= n) ans += cnt[k-a[l]];cnt[a[l]]++;}res[q[i].id] += ans * q[i].f;} }int main() {int l1,l2,r1,r2;while(scanf("%d",&n)!=EOF){scanf("%d",&k);for(int i = 1; i <= n; i++){cnt[i] = 0;scanf("%d",&a[i]);}scanf("%d",&m);for(int i = 0; i < m; i++){scanf("%d%d%d%d",&l1,&r1,&l2,&r2);res[i] = 0;q[(i<<2)].l=l1,q[(i<<2)].r=r2,q[(i<<2)].id=i,q[(i<<2)].f=1; q[(i<<2)+1].l=l1,q[(i<<2)+1].r=l2-1,q[(i<<2)+1].id=i,q[(i<<2)+1].f=-1; q[(i<<2)+2].l=r1+1,q[(i<<2)+2].r=r2,q[(i<<2)+2].id=i,q[(i<<2)+2].f=-1; q[(i<<2)+3].l=r1+1,q[(i<<2)+3].r=l2-1,q[(i<<2)+3].id=i,q[(i<<2)+3].f=1; }solve();for(int i = 0; i < m; i++)printf("%d\n",res[i]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 5213(容斥原理+莫队算法)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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