HDU 4417 Super Mario(区划树+二分)

HDU 4417 Super Mario(划分树+二分)

题目大意：

(L,R,H)   L,R之间比H小的数有多少个

借用网上搭牛模板。

我们二分K 。然后用划分树找到第K大的。

看和这个数的关系。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#define ll long long
#define eps 1e-5
#define oo 1000000007
#define pi acos(-1.0)
#define MAXN 100005
using namespace std;
int tree[21][MAXN],Num[21][MAXN],sorted[MAXN];
void build(int s,int e,int t)
{
       if (s==e) return;
       int i,x,y,mid=s+e>>1,m=mid-s+1;
       x=s,y=mid+1;
       for (i=s;i<=e;i++)
          if (sorted[i]<sorted[mid]) m--;
       for (i=s;i<=e;i++)
       {
              Num[t][i]=Num[t][i-1];
              if (tree[t][i]==sorted[mid])
              {
                     if (m) tree[t+1][x++]=tree[t][i],Num[t][i]++,m--;
                       else tree[t+1][y++]=tree[t][i];
              }else
              if (tree[t][i]<sorted[mid]) tree[t+1][x++]=tree[t][i],Num[t][i]++;
                 else tree[t+1][y++]=tree[t][i];
       }
       build(s,mid,t+1),build(mid+1,e,t+1);
}
int query(int t,int s,int e,int l,int r,int k)
{
       if (l==r) return tree[t][l];
       int ltoL,LtoR,mid=s+e>>1;
       ltoL=Num[t][l-1]-Num[t][s-1],LtoR=Num[t][r]-Num[t][l-1];
       if (LtoR>=k) return query(t+1,s,mid,s+ltoL,s+ltoL+LtoR-1,k);
       int b=l-s-ltoL,bb=r-l+1-LtoR;
       return query(t+1,mid+1,e,mid+b+1,mid+b+bb,k-LtoR);
}
void init(int n)
{
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&tree[0][i]);
        sorted[i]=tree[0][i];
    }
    memset(Num,0,sizeof(Num));
    sort(sorted+1,sorted+1+n);
    build(1,n,0);
}

int main()
{
    int n,m;
    int CASE=1;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        printf("Case %d:\n",CASE++);
        init(n);
        while(m--)
        {
            int L,R,H;
            scanf("%d%d%d",&L,&R,&H);
            L++,R++;
            int l=0,r=R-L+2;
            while(r-l>1)
            {
                int mid=(l+r)>>1;
                if(query(0,1,n,L,R,mid)<=H)l=mid;
                else r=mid;
            }
            printf("%d\n",l);
        }
    }
    return 0;
}

1楼cc_again昨天 23:22

牛叉。加油