解題思路：這道題要求某區(qū)間內(nèi)比h小的個(gè)數(shù)，其實(shí)這里可以類似于樹狀數(shù)組求逆序數(shù)那樣。關(guān)鍵是如何轉(zhuǎn)換成樹狀數(shù)組的模型，這才是本題的難點(diǎn)。

我們首先分析，如果知道h在該區(qū)間的哪個(gè)位置，那么剩下的就很好做了。我們還可以發(fā)現(xiàn)，如果找到了當(dāng)前的比h小的所有點(diǎn)（大于的點(diǎn)我們先忽略掉），那么我們就可以用樹狀數(shù)組求它的[l,r]區(qū)間的和。這樣就跟樹狀數(shù)組有了一點(diǎn)聯(lián)系，但是還不夠，因?yàn)槲覀儼l(fā)現(xiàn)，h的大小會(huì)影響我們所要找的區(qū)間。什么意思呢？就是我們先找到的是h1，再找h2，但h1>h2，就會(huì)出現(xiàn)這樣的問題：h1所對(duì)應(yīng)的區(qū)間找到了，但再找h2時(shí)，它對(duì)應(yīng)的區(qū)間中可能會(huì)有比h2大的數(shù)，這樣就不符合條件了。所以說這里有一個(gè)離線算法，就是先把所有的詢問存下來，再按照h的大小進(jìn)行從小到大排序，然后根據(jù)h的大小，從小到大地一個(gè)個(gè)插入所有區(qū)間內(nèi)的數(shù)，這樣就符合條件了。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;const int maxn = 1e5+5; struct Query {int l,r,h;int id;bool operator < (Query a){return h < a.h;} }q[maxn]; struct Node {int num;int id;bool operator < (Node a){return num < a.num;} }a[maxn]; int n,m; int tree[maxn<<2],ans[maxn];int lowbit(int x) {return x & (-x); }void update(int x,int d) {for(int i = x; i <= n; i += lowbit(i))tree[i] += d; }int getsum(int x) {int sum = 0;for(int i = x; i > 0; i -= lowbit(i))sum += tree[i];return sum; }int main() {int t,cas = 1;cin >> t;while(t--){cin >> n >> m;for(int i = 1; i <= n; i++){cin >> a[i].num;a[i].id = i;}for(int i = 1; i <= m; i++){cin >> q[i].l >> q[i].r >> q[i].h;q[i].l++, q[i].r++;q[i].id = i;}sort(a+1,a+1+n);sort(q+1,q+1+m);memset(tree,0,sizeof(tree));int idx = 1;for(int i = 1; i <= m; i++){while(q[i].h >= a[idx].num && idx <= n){update(a[idx].id,1);idx++;}ans[q[i].id] = getsum(q[i].r) - getsum(q[i].l-1);}printf("Case %d:\n",cas++);for(int i = 1; i <= m; i++)printf("%d\n",ans[i]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 4417(树状数组+离线算法)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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