題目鏈接：點擊查看

題目大意：給出一個數列，然后是m次查詢，每次查詢閉區間[l,r]內第K大的數

題目分析：裸的主席樹，暑假集訓第三周的時候就聽說過了這個數據結構，不過當時太懶了，而且那些主席樹的問題都能用線段樹離線處理，就沒花功夫來學，今天遇到的這個題，本來也想用線段樹離線處理，但是發現用vector會超時，看網上的題解是要用二分優化，但我不太理解為什么要那樣二分，所以就來學一學這個高級數據結構了，大概前前后后花了一天時間，看懂原理+背模板+理解細節，現在也剛停留在基礎部分吧。。還是需要多刷點題才能培養出舉一反三的能力，這里留一個B站視頻，我感覺講的挺好的：

av4619406

然后還有一個大佬的博客，也是當時看過之后一個小細節突然豁然開朗：

點擊查看

直接就上代碼了，現在就剩一個小細節不太明白了，先背過，以后說不定就理解了呢

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<cmath> #include<set> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;vector<int>v;struct Node {int l,r;int sum; }tree[N*20];int cnt,root[N];void init() {root[0]=0;tree[0].l=tree[0].r=tree[0].sum=0;cnt=1; }void update(int num,int &k,int l,int r) {tree[cnt++]=tree[k];k=cnt-1;tree[k].sum++;if(l==r)return;int mid=l+r>>1;if(num<=mid)update(num,tree[k].l,l,mid);elseupdate(num,tree[k].r,mid+1,r); }int a[N];int query(int i,int j,int k,int l,int r)//i：左端點根節點編號，j：右端點根節點編號，k：第k大的數，l,r:區間[l,r] {int d=tree[tree[j].l].sum-tree[tree[i].l].sum;//i和j代表的是根節點的編號，tree[i].l和tree[j].l代表的是根節點左子區間的編號 //tree[tree[j].l].sum和tree[tree[i].l].sum代表的是根節點左子區間的數目和，做差表示的是i到j這段區間內的左子區間的數目和(類比于前綴和) //這時d代表的是左子區間的數目和if(l==r)//遍歷到葉子節點，返回節點位置return l;int mid=l+r>>1;if(k<=d)//如果左子區間的數目和比要求的K大，那么第K大的數一定在左子區間，遍歷左子區間return query(tree[i].l,tree[j].l,k,l,mid);else//上述條件不成立，那么第K大的數一定在右子區間，遍歷右子區間return query(tree[i].r,tree[j].r,k-d,mid+1,r); }int main() { // freopen("input.txt","r",stdin);int n,m;while(scanf("%d%d",&n,&m)!=EOF){v.clear();for(int i=1;i<=n;i++){scanf("%d",a+i);v.push_back(a[i]);}init();sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());for(int i=1;i<=n;i++){root[i]=root[i-1];int num=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;update(num,root[i],1,n);}while(m--){int x,y,z;scanf("%d%d%d",&x,&y,&z);printf("%d\n",v[query(root[x-1],root[y],z,1,n)-1]);}}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ - 2104 K-th Number(主席树)的全部內容，希望文章能夠幫你解決所遇到的問題。

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