hdu 4417 Super Mario(離線樹狀數(shù)組|劃分樹)
來源：程序員人生 發(fā)布時間：2014-10-09 04:05:47 閱讀次數(shù)：2697次
Super Mario
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2584 Accepted Submission(s): 1252
Problem Description
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
Source
2012 ACM/ICPC Asia Regional Hangzhou Online
Recommend
liuyiding | We have carefully selected several similar problems for you: 5041 5040 5039 5038 5037
題意：
給你一個長度為n(1e5)的數(shù)列。然后m(1e5)個詢問。l,r,h
詢問數(shù)列[l.r]中有多少個數(shù)字是不大于h的。
思路:
比較容易想到的是如果我們知道h是數(shù)列[l,r]里的第幾大數(shù)。就能知道該區(qū)間有多少數(shù)不大于它了。區(qū)間第k大數(shù)明顯是劃分樹的強項。但是我們不知道h是第幾大數(shù)。所以就可以二分。然后問題就解決了。時間復(fù)雜度。O(n*log(n)^2)。還能接受。
詳細見代碼：
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;
int seg[20][maxn],lnum[20][maxn],sa[maxn];
int n,m;
void btree(int L,int R,int d)
{
int i,ls,rs,lm,mid;
if(L==R)
return ;
mid=(L+R)>>1;
ls=L,rs=mid+1;
lm=mid-L+1;
for(i=L;i<=R;i++)
if(seg[d][i]<sa[mid])
lm--;
for(i=L;i<=R;i++)
{
lnum[d][i]=(i==L)?0:lnum[d][i-1];
if(seg[d][i]==sa[mid])
{
if(lm>0)
{
lm--;
lnum[d][i]++;
seg[d+1][ls++]=seg[d][i];
}
else
seg[d+1][rs++]=seg[d][i];
}
else if(seg[d][i]<sa[mid])
{
lnum[d][i]++;
seg[d+1][ls++]=seg[d][i];
}
else
seg[d+1][rs++]=seg[d][i];
}
btree(L,mid,d+1);
btree(mid+1,R,d+1);
}
int qu(int L,int R,int l,int r,int d,int k)
{
int ss,s,bb,b,mid;
if(L==R)
return seg[d][L];
ss=(l==L)?0:lnum[d][l-1];
s=lnum[d][r]-ss;
mid=(L+R)>>1;
if(s>=k)
return qu(L,mid,L+ss,L+ss+s-1,d+1,k);
else
{
bb=l-L-ss;
b=r-l+1-s;
return qu(mid+1,R,mid+bb+1,mid+bb+b,d+1,k-s);
}
}
void init()
{
int i;
for(i=1;i<=n;i++)
{
scanf("%d",&seg[0][i]);
sa[i]=seg[0][i];
}
sort(sa+1,sa+n+1);
btree(1,n,0);
}
int bin(int L,int R,int h)
{
int low=1,hi=R-L+1,mid,ans=0;
while(low<=hi)
{
mid=(low+hi)>>1;
if(qu(1,n,L,R,0,mid)<=h)
ans=mid,low=mid+1;
else
hi=mid-1;
}
return ans;
}
int main()
{
int L,R,h,t,cas=1;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
init();
printf("Case %d:
",cas++);
while(m--)
{
scanf("%d%d%d",&L,&R,&h);
L++,R++;
printf("%d
",bin(L,R,h));
}
}
return 0;
}
還有一個更巧妙的方法就是離線樹狀數(shù)組。有時候離線真的能使原本復(fù)雜的問題簡單很多。試想如果對于每個詢問l,r,h我們只把值不大于h的數(shù)字插到樹狀數(shù)組對應(yīng)位置。然后每次詢問[l,r]中有多少個數(shù)被插進來了就行了。所以我們把數(shù)列按h排序。把詢問也按h排序。然后對于每個詢問先把h不大于詢問的h的數(shù)列插進樹狀數(shù)組就行了。這樣時間復(fù)雜度只有O(n*log(n))代碼量也減了好多。
詳細見代碼：
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;
int C[maxn],ans[maxn],n,m;
struct qnode
{
int l,r,h,id;
inline bool operator <(const qnode &tt) const
{
return h<tt.h;
}
} qu[maxn];
struct node
{
int p,h;
inline bool operator <(const node &tt) const
{
return h<tt.h;
}
} bk[maxn];
void update(int x,int d)
{
for(int i=x;i<=n;i+=i&-i)
C[i]+=d;
}
int getsum(int x)
{
int sum=0;
for(int i=x;i>0;i-=i&-i)
sum+=C[i];
return sum;
}
int main()
{
int t,cas=1,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
C[n]=0;
for(i=0;i<n;i++)
{
C[i]=0,bk[i].p=i+1;
scanf("%d",&bk[i].h);
}
for(i=0;i<m;i++)
{
scanf("%d%d%d",&qu[i].l,&qu[i].r,&qu[i].h);
qu[i].l++,qu[i].r++,qu[i].id=i;
}
sort(bk,bk+n);
sort(qu,qu+m);
for(i=j=0;i<m;i++)
{
for(;j<n&&bk[j].h<=qu[i].h;j++)
update(bk[j].p,1);
ans[qu[i].id]=getsum(qu[i].r)-getsum(qu[i].l-1);
}
printf("Case %d:
",cas++);
for(i=0;i<m;i++)
printf("%d
",ans[i]);
}
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進行捐贈
