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;
}
上一篇: flask_sqlalchemy的session线程安全
下一篇: SQLAlchemy的简单使用