欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU 4417(主席树基础题)

程序员文章站 2024-03-02 22:03:40
...

题目描述:

马里奥通往boss的道路为一条直线(长度为1<=n<=1e5),在每个整数点(0-n-1)上都有一块砖,每块砖的高度Hi(0<=Hi<=1e9)。

有m(1<=m<=1e5)个询问L R H表示:如果他能跳的最大高度为H(0<=H<=1e9),问在区间[L,R] 中(0<=L<=R<n),马里奥最多可以撞到多少个砖块。

题目分析:

这是一道主席树基础应用题。利用主席树可以查询区间[L,R]种第k小的数,如果这个第k小的数恰好满足k<=H,那么马里奥可以集中的砖块数就为k。

主席树入门:https://www.bilibili.com/video/av4619406/

代码:

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#define INF 0x3f3f3f3f//3f3f3f3f
#define ll long long
#define ull unsigned long long
const long long MOD = 1e9 + 7;
#define lowbit(a) ((a)&(-(a)))
using namespace std;
/******主席树模板******/
const int maxn=100005;
int cnt,root[maxn],a[maxn];
vector<int>v;
struct node{int l,r,sum;}T[40*maxn];
int getid(int i){return (lower_bound(v.begin(),v.end(),i)-v.begin()+1);}
///加入节点操作update(1,n,root[i],root[i-1],getid(a[i]));
void update(int l,int r,int &x,int y,int pos){
    T[++cnt]=T[y];x=cnt;T[x].sum++;
    if(l==r)return;
    int mid=(l+r)>>1;
    if(mid>=pos)update(l,mid,T[x].l,T[y].l,pos);
    else update(mid+1,r,T[x].r,T[y].r,pos);
}
///查询区间按vector优先级排序第k的数v[query(1,n,root[l-1],root[r],k)-1]
int query(int l,int r,int x,int y,int k){
    if(l==r)return l;
    int sum=T[T[y].l].sum-T[T[x].l].sum;
    int mid=(l+r)>>1;
    if(sum>=k)return query(l,mid,T[x].l,T[y].l,k);
    else return query(mid+1,r,T[x].r,T[y].r,k-sum);
}
/******主席树模板******/
int n,q,h,l,r;
int main(){
    int _;scanf("%d",&_);
    for(int t=1;t<=_;t++){
        printf("Case %d:\n",t);
        scanf("%d %d", &n,&q);
        v.clear();cnt=0;
        T[0].l=T[0].r=T[0].sum=0;
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            v.push_back(a[i]);
        }
        sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());
        for(int i=0;i<n;i++)update(1,n,root[i],root[i-1],getid(a[i]));
        for(int i=1;i<=q;i++){
            scanf("%d %d %d",&l,&r,&h);
            int al=0,ar=r-l+1,mid;///二分查找恰好小于等于h的数为答案,本弱鸡的二分写法。。。
            while(al+1<ar){
                mid=(al+ar)>>1;
                int d=v[query(1,n,root[l-1],root[r],mid)-1];
                if(d<=h){
                    al=mid;
                }else{
                    ar=mid-1;
                }
            }
            if(v[query(1,n,root[l-1],root[r],ar)-1]<=h)
                printf("%d\n",ar);
            else
                printf("%d\n",al);
        }
    }
    return 0;
}