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 100005using 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;}