題目鏈接：點擊查看

題目大意：給出由 n 個數的數列，再給出 m 次查詢，每次查詢需要輸出 [ l , r ] 內小于等于 h 的數有多少個

題目分析：大晚上睡不著覺隨便做做題，發現這個題目原來可以用主席樹來做，又發現這個題目去年暑假竟然沒寫博客，于是補上一發

線段樹離線的做法就是對數列和詢問的高度排序，遍歷每個詢問，雙指針將小于等于當前詢問高度的位置都扔到線段樹中，記錄當前詢問的區間內有多少個數即可

主席樹在線做法，有兩種，先說一下網上最常見的，就是遍歷每個位置作為下標，對于下標維護可持久化線段樹，每個權值線段樹維護的是高度信息，記錄一下每個高度出現了多少次，答案顯然就是第 R 個版本中 [ 1 , h ] 的個數減去第 L - 1 個版本中 [ 1 , h ] 的個數了

再說一下我自己的做法，我是對于高度維護了可持久化線段樹，每個權值線段樹維護的是區間信息，記錄一下 [ 1 , h ] 內的所有數在區間上的分布情況，這樣答案就是第 h 個版本的權值線段樹中 [ l , r ] 中有多少個數了

兩種主席樹的做法時空復雜度相同且都是需要進行離散化的，但我個人感覺自己的做法更好理解一些，更能體現了：主席樹是可持久化線段樹，其中每個版本的主席樹單獨拿出來都是一個權值線段樹

代碼：

主席樹：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;struct Node {int l,r;int sum; }tree[N*20];int cnt,root[N];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 query(int k,int l,int r,int L,int R)//[l,r]:目標區間,[L,R]:當前區間 {if(R<l||L>r)return 0;if(L>=l&&R<=r)return tree[k].sum;int mid=L+R>>1;return query(tree[k].l,l,r,L,mid)+query(tree[k].r,l,r,mid+1,R); }map<int,vector<int>>mp;vector<int>node;int get_id(int x) {return upper_bound(node.begin(),node.end(),x)-node.begin(); }void discreate() {sort(node.begin(),node.end());node.erase(unique(node.begin(),node.end()),node.end()); }void init() {mp.clear();node.clear();root[0]=0;tree[0].l=tree[0].r=tree[0].sum=0;cnt=1; }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;int kase=0;while(w--){init();int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){int h;scanf("%d",&h);mp[h].push_back(i);node.push_back(h);}discreate();for(int i=1;i<=node.size();i++)//按照高度建主席樹，每個高度的前綴和的權值線段樹代表的是[1,h]內的高度在[1,n]上的分布情況 {root[i]=root[i-1];for(int pos:mp[node[i-1]])update(pos,root[i],1,n);}printf("Case %d:\n",++kase);while(m--){int l,r,h;scanf("%d%d%d",&l,&r,&h);l++,r++;printf("%d\n",query(root[get_id(h)],l,r,1,n));}}return 0; }

離線+線段樹：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;struct Tree {int l,r,sum; }tree[N<<2];struct Node {int hei,pos;bool operator<(Node a)const{return hei<a.hei;} }a[N];struct node {int hei,l,r,id;bool operator<(node a)const{return hei<a.hei;} }b[N];int ans[N];void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;tree[k].sum=0;if(l==r)return;int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r); }void update(int k,int pos) {if(tree[k].l==tree[k].r){tree[k].sum=1;return;}int mid=(tree[k].l+tree[k].r)>>1;if(mid>=pos)update(k<<1,pos);elseupdate(k<<1|1,pos);tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; }int query(int k,int l,int r) {if(tree[k].r<l||tree[k].l>r)return 0;if(tree[k].l>=l&&tree[k].r<=r)return tree[k].sum;return query(k<<1,l,r)+query(k<<1|1,l,r); }int main() { // freopen("input.txt","r",stdin);int w;cin>>w;int kase=0;while(w--){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i].hei);a[i].pos=i;}for(int i=1;i<=m;i++){scanf("%d%d%d",&b[i].l,&b[i].r,&b[i].hei);b[i].l++;b[i].r++;b[i].id=i;}build(1,1,n);sort(a+1,a+1+n);sort(b+1,b+1+m);int pos=1;for(int i=1;i<=m;i++){int h=b[i].hei;while(a[pos].hei<=h){update(1,a[pos].pos);pos++;}ans[b[i].id]=query(1,b[i].l,b[i].r);}printf("Case %d:\n",++kase);for(int i=1;i<=m;i++)cout<<ans[i]<<endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 4417 Super Mario(主席树/线段树+离线)的全部內容，希望文章能夠幫你解決所遇到的問題。

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