hdu 4417 Super Mario(離線樹狀數組|劃分樹)

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)的數列。然後m(1e5)個詢問。l,r,h 詢問數列[l.r]中有多少個數字是不大於h的。 思路: 比較容易想到的是如果我們知道h是數列[l,r]裡的第幾大數。就能知道該區間有多少數不大於它了。區間第k大數明顯是劃分樹的強項。但是我們不知道h是第幾大數。所以就可以二分。然後問題就解決了。時間復雜度。O(n*log(n)^2)。還能接受。 詳細見代碼：

#include
#include
#include
#include
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]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]>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:\n",cas++);
        while(m--)
        {
            scanf("%d%d%d",&L,&R,&h);
            L++,R++;
            printf("%d\n",bin(L,R,h));
        }
    }
    return 0;
}

還有一個更巧妙的方法就是離線樹狀數組。有時候離線真的能使原本復雜的問題簡單很多。試想如果對於每個詢問l,r,h我們只把值不大於h的數字插到樹狀數組對應位置。然後每次詢問[l,r]中有多少個數被插進來了就行了。所以我們把數列按h排序。把詢問也按h排序。然後對於每個詢問先把h不大於詢問的h的數列插進樹狀數組就行了。這樣時間復雜度只有O(n*log(n))代碼量也減了好多。 詳細見代碼：

#include
#include
#include
#include
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 h0;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