Super Mario
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 771 Accepted Submission(s): 423
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
題意：
輸入cas
n m
輸入n個數
輸入m組 每組表示一個范圍內l r 中小於num的數的個數
注意從l是0開始的
思路 ：區間內找數 很容易聯想到劃分樹 劃分樹是用來求一個區間內的第k大的數
那麼我們可以找出第1第2第3.。。。。。。大數的值 和num進行比較
用二分法很容易找到第幾大的數小於且等於num
下面的幾乎就是個模板 二分法居然也搞了我一下 坑爹
[cpp]
#include<stdio.h>
#include<algorithm>
using namespace std;
#define M 100005
int tree[40][M],sorted[M];
int toLeft[40][M];
void build(int level,int left,int right){
if(left==right)return ;
int mid=(left+right)>>1;
int i;
int suppose;//假設在中位數sorted[mid]左邊的數都全部小於sorted[mid]
suppose=mid-left+1;
for(i=left;i<=right;i++){
if(tree[level][i]<sorted[mid]){
suppose--;
}
}
//如果suppose==1，則說明數組中值為sorted[mid]只有一個數。比如序列：1 3 4 5 6，sorted[mid]=4
/*如果suppose>1，則說明數組中左半邊值為sorted[mid]的不止一個數,為mid-suppose。比如序列：1 4 4 4 6，sorted[mid]=4
*/
int lpos=left,rpos=mid+1;
for(i=left;i<=right;i++){
if(i==left)
{//這裡是預處理，相當與初始化
toLeft[level][i]=0;
}
else
{
toLeft[level][i]=toLeft[level][i-1];
}
if(tree[level][i]<sorted[mid]){//劃分到中位數左邊
toLeft[level][i]++;
tree[level+1][lpos++]=tree[level][i];
}else if(tree[level][i]>sorted[mid]){//劃分到中位數右邊
tree[level+1][rpos++]=tree[level][i];
}else{//這裡，suppose大於0的數劃分到中位數的左邊
if(suppose!=0){//這裡的處理太巧妙了！帥氣！
suppose--;
toLeft[level][i]++;
tree[level+1][lpos++]=tree[level][i];
}else{//表示
tree[level+1][rpos++]=tree[level][i];
}
}
}
build(level+1,left,mid);
build(level+1,mid+1,right);
}
//在[left,right]數據中查詢[qleft,qright]中第k大的數據
int query(int level,int left,int right,int qleft,int qright,int k){
if( qleft==qright)
return tree[level][qleft];
int s;//代表[left,qleft)之間有多個個元素被分到左邊
int ss;//[qleft, qright]內將被劃分到左子樹的元素數目
int mid=(left+right)>>1;
if(left==qleft){
s=0;
ss=toLeft[level][qright];
}else{
s=toLeft[level][qleft-1];
ss=toLeft[level][qright]-s;
}
int newl,newr;
if(k<=ss){//查詢左邊
newl=left+s;
newr=left+s+ss-1;
return query(level+1,left,mid,newl,newr,k);
}else{//查詢右邊
newl=mid-left+1+qleft-s;
newr=mid-left+1+qright-s-ss;
return query(level+1,mid+1,right,newl, newr,k - ss);
}
}
int main()
{
int n,m,cas,ca=0;
scanf("%d",&cas);
while(cas--)
{
printf("Case %d:\n",++ca);
scanf("%d %d",&n,&m);
int i;
for(i=1;i<=n;i++){
scanf("%d",&tree[0][i]);
sorted[i]=tree[0][i];
}
sort(sorted+1,sorted+n+1);
build(0,1,n);
int ql,qr,num,ans=0;
for(i=0;i<m;i++)
{
scanf("%d %d %d",&ql,&qr,&num);
ql++;qr++;//注意這裡哦 題意是按從0開始的
int mid,left=1,right=qr-ql+1,ans=0;
mid=(left+right)/2;
while(left<=right)//別少了等於號
{
mid=(left+right)/2;
if(query(0,1,n,ql,qr,mid)>num) right=mid-1;
else {ans=mid;left=mid+1;}//我一開始寫的二分法居然不知道是哪裡出錯了一個勁RE
}
printf("%d\n",ans);
}
} return 0;
}
