hdu 4417 Super Mario 离线线段树
思路：将点按值从小到大排序，询问按h从小到大排序。
在建立线段树，按h的大小更新树并得到该次查询的结果！
代码如下：
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<iomanip> 5 #include<cmath> 6 #include<cstring> 7 #define MAX 100005 8 #define I(x) scanf("%d",&x) 9 #define lson step<<1 10 #define rson step<<1|1 11 using namespace std; 12 int ans[MAX]; 13 struct node 14 { 15 int x,y,h,id; 16 bool operator<(const node a)const{ 17 return h<a.h; 18 } 19 }q[MAX]; 20 struct point 21 { 22 int v,id; 23 bool operator<(const point a)const{ 24 return v<a.v; 25 } 26 }p[MAX]; 27 struct tree 28 { 29 int l,r,cnt; 30 }T[MAX<<2]; 31 void built(int step,int l,int r) 32 { 33 T[step].l=l; 34 T[step].r=r; 35 T[step].cnt=0; 36 if(l==r) return ; 37 int m=(l+r)>>1; 38 built(lson,l,m); 39 built(rson,m+1,r); 40 } 41 void update(int step,int pos) 42 { 43 T[step].cnt++; 44 if(T[step].l==T[step].r) return; 45 int m=(T[step].l+T[step].r)>>1; 46 if(pos<=m) update(lson,pos); 47 else update(rson,pos); 48 } 49 int query(int step,int l,int r) 50 { 51 if(T[step].l==l&&T[step].r==r) return T[step].cnt; 52 int m=(T[step].l+T[step].r)>>1; 53 if(r<=m) return query(lson,l,r); 54 else if(l>m) return query(rson,l,r); 55 else return query(lson,l,m)+query(rson,m+1,r); 56 } 57 int main() 58 { 59 int t,i,j,m,n,k,ca=0; 60 I(t); 61 while(t--){ 62 scanf("%d%d",&n,&m); 63 for(i=0;i<n;i++){ 64 I(p[i].v); 65 p[i].id=i+1; 66 } 67 for(i=0;i<m;i++){ 68 scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].h); 69 q[i].id=i; 70 } 71 built(1,1,n); 72 sort(p,p+n); 73 sort(q,q+m); 74 j=0; 75 for(i=0;i<m;i++){ 76 while(j<n&&p[j].v<=q[i].h){ 77 update(1,p[j].id); 78 j++; 79 } 80 ans[q[i].id]=query(1,q[i].x+1,q[i].y+1); 81 } 82 printf("Case %d: ",++ca); 83 for(i=0;i<m;i++) 84 printf("%d ",ans[i]); 85 } 86 return 0; 87 }
这个是划分树做的。
1 #include<iostream> 2 #include<cstdio> 3 #include<map> 4 #include<cstring> 5 #include<cmath> 6 #include<vector> 7 #include<algorithm> 8 #include<set> 9 #include<string> 10 #include<queue> 11 #define inf 1<<28 12 #define M 6000005 13 #define N 100005 14 #define maxn 300005 15 #define Min(a,b) ((a)<(b)?(a):(b)) 16 #define Max(a,b) ((a)>(b)?(a):(b)) 17 #define pb(a) push_back(a) 18 #define mem(a,b) memset(a,b,sizeof(a)) 19 #define LL long long 20 #define MOD 1000000007 21 #define lson step<<1 22 #define rson step<<1|1 23 using namespace std; 24 struct Node{ 25 int left,right; 26 int sum; 27 }L[N*4]; 28 int sa[N],num[20][N],cnt[20][N];//sa中是排序后的，num记录每一层的排序结果，cnt[deep][i]表示第deep层，前i个数中有多少个进入左子树 29 void Bulid(int step,int l,int r,int deep){ 30 L[step].left=l; 31 L[step].right=r; 32 if(l==r) 33 return; 34 int mid=(l+r)>>1; 35 int mid_val=sa[mid],lsum=mid-l+1;; 36 for(int i=l;i<=r;i++) 37 if(num[deep][i]<mid_val) 38 lsum--; //lsum表示左子树中还需要多少个中值 39 int L=l,R=mid+1; 40 for(int i=l;i<=r;i++){ 41 if(i==l) 42 cnt[deep][i]=0; 43 else 44 cnt[deep][i]=cnt[deep][i-1]; 45 if(num[deep][i]<mid_val||(num[deep][i]==mid_val&&lsum>0)){ //左子树 46 num[deep+1][L++]=num[deep][i]; 47 cnt[deep][i]++; 48 if(num[deep][i]==mid_val) 49 lsum--; 50 } 51 else 52 num[deep+1][R++]=num[deep][i]; 53 } 54 Bulid(2*step,l,mid,deep+1); 55 Bulid(2*step+1,mid+1,r,deep+1); 56 } 57 int Query(int step,int l,int r,int k,int deep){ 58 if(l==r) 59 return num[deep][l]; 60 int s1,s2; //s1为[L[step].left,l-1]中分到左子树的个数 61 if(L[step].left==l) 62 s1=0; 63 else 64 s1=cnt[deep][l-1]; 65 s2=cnt[deep][r]-s1; //s2为[l,r]中分到左子树的个数 66 int m=(L[step].left+L[step].right)/2; 67 if(k<=s2) //左子树的数量大于k,递归左子树 68 return Query(lson,L[step].left+s1,L[step].left+s1+s2-1,k,deep+1); 69 int b1=l-1-L[step].left+1-s1; //b1为[L[step].left,l-1]中分到右子树的个数 70 int b2=r-l+1-s2; //b2为[l,r]中分到右子树的个数 71 return Query(rson,m+1+b1,m+1+b1+b2-1,k-s2,deep+1); 72 } 73 int slove(int l,int r,int h){ 74 int ans=0,low=1,high=r-l+1,mid; 75 while(low<=high){ 76 mid=(low+high)/2; 77 int tmp=Query(1,l,r,mid,0); 78 if(tmp<=h){ans=mid;low=mid+1;} 79 else high=mid-1; 80 } 81 return ans; 82 } 83 int main(){ 84 int n,q,t,cas=0; 85 scanf("%d",&t); 86 while(t--){ 87 scanf("%d%d",&n,&q); 88 for(int i=1;i<=n;i++){ 89 scanf("%d",&sa[i]); 90 num[0][i]=sa[i]; 91 } 92 sort(sa+1,sa+1+n); 93 Bulid(1,1,n,0); 94 printf("Case %d: ",++cas); 95 while(q--){ 96 int l,r,h; 97 scanf("%d%d%d",&l,&r,&h); 98 l++;r++; 99 printf("%d ",slove(l,r,h)); 100 } 101 } 102 return 0; 103 }