本文主要是介绍hdu 4417 Super Mario（划分树或树状数组），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给你n个数，m个查询，对于一个查询问在[a,b]范围内小于c的数有多少个。
有两种做法：1 树状数组离线处理，将输入的n个数按大小排序，也将查询按他们查询的数的大小排序。从小到大到这n个数放进数状数组里，当小于一个查询的c的所有的数都在放进数状数组里面的时候，查询[a,b]范围内有多少个数。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N=1e5+5;
struct node
{int valu,ind;node(){}node(int a,int b){valu=a;ind=b;}bool operator<(const node &b)const{return valu<b.valu;}
};
struct Query
{int st,ed,valu,ind;Query(){}Query(int a,int b,int c,int d){st=a;ed=b;valu=c;ind=d;}bool operator<(const Query &b)const{return valu<b.valu;}
};
struct BIT
{int a[N];int lowbit(int x){return x&(-x);}void clear() {memset(a,0,sizeof(a));}void updata(int pos){for(int i=pos;i>0;i-=lowbit(i))a[i]+=1;}int query(int st,int ed){int sum=0;for(int i=st;i<N;i+=lowbit(i))sum+=a[i];for(int i=ed+1;i<N;i+=lowbit(i))sum-=a[i];return sum;}
}bit;int res[N];
vector<node> data;
vector<Query> op;int main()
{int t,t_cnt=0;scanf("%d",&t);while(t--){op.clear(); data.clear(); bit.clear();int n,m,a,b,c;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a);data.push_back(node(a,i));}for(int i=0;i<m;i++){scanf("%d%d%d",&a,&b,&c);op.push_back(Query(a+1,b+1,c,i));}sort(data.begin(),data.end());sort(op.begin(),op.end());int ind=0;for(int i=0;i<(int)data.size();i++){while(ind<(int)op.size()&&op[ind].valu<data[i].valu) {res[op[ind].ind]=bit.query(op[ind].st,op[ind].ed);ind++;}bit.updata(data[i].ind);}for(int i=ind;i<(int)op.size();i++)res[op[i].ind]=bit.query(op[i].st,op[i].ed);printf("Case %d:\n",++t_cnt);for(int i=0;i<m;i++)printf("%d\n",res[i]);}return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MID(a,b) (a+((b-a)>>1))
const int N=1e5+5;
struct P_Tree
{int n,order[N];int valu[20][N],num[20][N];void init(int len){n=len;for(int i=0;i<20;i++) valu[i][0]=0,num[i][0]=0;for(int i=1;i<=n;i++){scanf("%d",&order[i]);valu[0][i]=order[i];}sort(order+1,order+1+n);build(1,n,0);}void build(int lft,int rht,int ind){if(lft==rht) return;int mid=MID(lft,rht);int ln=lft,rn=mid+1,same=mid-lft+1;for(int i=lft;i<=rht;i++)if(valu[ind][i]<order[mid]) same--;for(int i=lft;i<=rht;i++){int flag=0;if((valu[ind][i]<order[mid])||(valu[ind][i]==order[mid]&&same)){flag=1;valu[ind+1][ln++]=valu[ind][i];if(valu[ind][i]==order[mid]) same--;}else valu[ind+1][rn++]=valu[ind][i];num[ind][i]=num[ind][i-1]+flag;}build(lft,mid,ind+1);build(mid+1,rht,ind+1);}int query(int st,int ed,int k,int lft,int rht,int ind){if(k==0) return -1;if(ed-st+1<k) return (1<<30);if(lft==rht) return valu[ind][lft];int mid=MID(lft,rht);int lx=num[ind][st-1]-num[ind][lft-1];int ly=num[ind][ed]-num[ind][st-1];int rx=st-1-lft+1-lx;int ry=ed-st+1-ly;if(ly>=k) return query(lft+lx,lft+lx+ly-1,k,lft,mid,ind+1);else{st=mid+1+rx;ed=mid+1+rx+ry-1;return query(st,ed,k-ly,mid+1,rht,ind+1);}}
}tree;
int main()
{int t,t_cnt=0;scanf("%d",&t);while(t--){int n,m;scanf("%d%d",&n,&m);tree.init(n);printf("Case %d:\n",++t_cnt);for(int i=0;i<m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);a++; b++;int lft=0,rht=b-a+2;while(lft<rht){int mid=MID(lft,rht);int ele=tree.query(a,b,mid,1,n,0);if(ele<=c) lft=mid+1;else rht=mid;}printf("%d\n",lft-1);}}
}
这篇关于hdu 4417 Super Mario（划分树或树状数组）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
