Mario is world-famous plumber. His “burly” figure and amazing jumping ability reminded in our memory. Now the poor princess is in trouble again and Mario needs to save his lover. We regard the road to the boss’s castle as a line (the length is n), on every integer point i there is a brick on height hi. Now the question is how many bricks in [L, R] Mario can hit if the maximal height he can jump is H.
Input
The first line follows an integer T, the number of test data.
For each test data:
The first line contains two integers n, m (1 <= n <=10^5, 1 <= m <= 10^5), n is the length of the road, m is the number of queries.
Next line contains n integers, the height of each brick, the range is [0, 1000000000].
Next m lines, each line contains three integers L, R,H.( 0 <= L <= R < n 0 <= H <= 1000000000.)
Output
For each case, output "Case X: " (X is the case number starting from 1) followed by m lines, each line contains an integer. The ith integer is the number of bricks Mario can hit for the ith query.
Sample Input
1
10 10
0 5 2 7 5 4 3 8 7 7
2 8 6
3 5 0
1 3 1
1 9 4
0 1 0
3 5 5
5 5 1
4 6 3
1 5 7
5 7 3
Sample Output
Case 1:
4
0
0
3
1
2
0
1
5
1
求l到r中小于k的數字個數。
對于這種l到r的八九不離十是線段樹或者主席樹，根據題目而定。
這個題目就是利用主席樹，由于數據量比較大，所以需要離散化一下。關于離散化和不離散化對于主席樹的影響，離散化之后，我們在插入數據的時候，是根據數據在數組中的相對位置，就是lower_bound之后的數。但是不離散化，我們就可以直接按著權值插入數據。權值線段樹也是醬紫。我在做主席樹或者權值線段樹的時候，有時就分不清該是用位置還是權值，就很懵逼。感覺這樣判斷還是比較正確的，不對的話希望大佬可以指正。
代碼如下：

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #define ll long long using namespace std;const int maxx=1e5+100; struct node{int l;int r;int v; }p[maxx*40]; int a[maxx],b[maxx],root[maxx]; int n,m,num;int build(int l,int r) {int cur=num++;p[cur].v=0;if(l==r) return cur;int mid=l+r>>1;p[cur].l=build(l,mid);p[cur].r=build(mid+1,r);return cur; } int update(int rot,int l,int r,int k) {int cur=num++;p[cur]=p[rot];p[cur].v++;if(l==r) return cur;int mid=l+r>>1;if(k<=mid) p[cur].l=update(p[rot].l,l,mid,k);else p[cur].r=update(p[rot].r,mid+1,r,k);return cur; } int query(int lrot,int rrot,int l,int r,int k) {if(l==r) return p[rrot].v-p[lrot].v;//到達葉子節(jié)點之后，就直接做差就行。int mid=l+r>>1;if(k<=mid) return query(p[lrot].l,p[rrot].l,l,mid,k);else {int ans=p[p[rrot].l].v-p[p[lrot].l].v;ans+=query(p[lrot].r,p[rrot].r,mid+1,r,k);return ans;} } int main() {int t,pos,l,r,k,kk=0;scanf("%d",&t);while(t--){num=1;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];sort(b+1,b+1+n);int len=unique(b+1,b+1+n)-b-1;//離散化root[0]=build(1,len);for(int i=1;i<=n;i++){pos=lower_bound(b+1,b+1+len,a[i])-b;root[i]=update(root[i-1],1,len,pos);}printf("Case %d:\n",++kk);while(m--){scanf("%d%d%d",&l,&r,&k);l++;r++;pos=upper_bound(b+1,b+1+len,k)-b-1;if(pos==0) puts("0");else printf("%d\n",query(root[l-1],root[r],1,len,pos));}}return 0; }

過來更新一波。這個題也可以不用主席樹，也可以用線段樹+離線去做。
我們把所有的查詢按著k值大小排序，記錄之前的位置。也要把原序列按權值大小排序，記錄之前的位置。然后遍歷去遍歷數組。當當前值小于當前的k時，就按著原來的位置插入線段樹，否則就直接按著區(qū)間找出答案。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e5+100; struct Node{int h,pos;bool operator <(const Node &a)const{return a.h>h;} }a[maxx]; struct Node1{int l,r,h,id;bool operator <(const Node1 &a)const{return a.h>h;} }b[maxx]; struct node{int l;int r;int sum; }p[maxx<<2]; int ans[maxx]; int n,m;inline void pushup(int cur) {p[cur].sum=p[cur<<1].sum+p[cur<<1|1].sum; } inline void build(int l,int r,int cur) {p[cur].l=l;p[cur].r=r;p[cur].sum=0;if(l==r) return ;int mid=l+r>>1;build(l,mid,cur<<1);build(mid+1,r,cur<<1|1); } inline void update(int pos,int v,int cur) {int L=p[cur].l;int R=p[cur].r;if(L==R){p[cur].sum+=v;return ;}int mid=L+R>>1;if(pos<=mid) update(pos,v,cur<<1);else update(pos,v,cur<<1|1);pushup(cur); } inline int query(int l,int r,int cur) {int L=p[cur].l;int R=p[cur].r;if(l<=L&&R<=r) return p[cur].sum;int mid=L+R>>1;if(r<=mid) return query(l,r,cur<<1);else if(l>mid) return query(l,r,cur<<1|1);else return query(l,mid,cur<<1)+query(mid+1,r,cur<<1|1); } int main() {int t,k=0;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);build(1,n,1);for(int i=1;i<=n;i++) scanf("%d",&a[i].h),a[i].pos=i;for(int i=1;i<=m;i++) scanf("%d%d%d",&b[i].l,&b[i].r,&b[i].h),b[i].l++,b[i].r++,b[i].id=i;sort(a+1,a+1+n);sort(b+1,b+1+m);for(int i=1,j=1;i<=m;i++){while(a[j].h<=b[i].h&&j<=n) update(a[j++].pos,1,1);ans[b[i].id]=query(b[i].l,b[i].r,1);}printf("Case %d:\n",++k);for(int i=1;i<=m;i++) printf("%d\n",ans[i]);} }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的Super Mario HDU - 4417（主席树解决区间数字小于k的个数||线段树+离线）的全部內容，希望文章能夠幫你解決所遇到的問題。

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