hdu-4417 求区间不大于h的单位数
划分树模板+二分单位数(第k大的数)
#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> using namespace std; const int MAXN = 100010; int tree[30][MAXN];//表示每层每个位置的值 int sorted[MAXN];//已经排序的数 int toleft[30][MAXN];//toleft[p][i]表示第i层从1到i有多少个数分入左边 //long long sum[20][MAXN]; void build(int l,int r,int dep){ if(l==r) return ; /*if(l==r){ sum[dep][l]=tree[dep][l]; return ; }*/ int mid = (l+r)/2; int same = mid-l+1;//表示等于中间值而且被分入左边的个数 for(int i=l;i<=r;i++) if(tree[dep][i]<sorted[mid]) same--; /*for(int i=l;i<=r;i++){ if(tree[dep][i]<sorted[mid]) same--; sum[dep][i]=tree[dep][i]; if(i>l) sum[dep][i]+=sum[dep][i-1]; }*/ int lpos=l; int rpos=mid+1; for(int i=l;i<=r;i++){ if(tree[dep][i]<sorted[mid])//比中间的数小，分入左边 tree[dep+1][lpos++]=tree[dep][i]; else if(tree[dep][i]==sorted[mid] && same>0){ tree[dep+1][lpos++]=tree[dep][i]; same--; } else{//比中间值大，分入右边 tree[dep+1][rpos++]=tree[dep][i]; } toleft[dep][i]=toleft[dep][l-1]+lpos-l;//从1到i放左边的个数 } build(l,mid,dep+1); build(mid+1,r,dep+1); } //long long ans; //查询区间第k大的数，[L,R]是大区间，[l,r]是要查询的小区间 int query(int L,int R,int l,int r,int dep,int k){ if(l==r) return tree[dep][l]; int mid=(L+R)/2; int cnt=toleft[dep][r]-toleft[dep][l-1]; /*int ss=toleft[dep][l-1]-toleft[dep][L-1]; int ee=l-L-ss; int s =toleft[dep][r]-toleft[dep][l-1]; int e =r-l+1-s;*/ if(cnt>=k){ /*if(e>0){ if(ee>0) ans+=sum[dep+1][mid+e+ee] - sum[dep+1][mid+ee]; else ans+=sum[dep+1][mid+e]; }*/ //L+要查询的区间前被放在左边的个数 int newl=L+toleft[dep][l-1]-toleft[dep][L-1]; //左端点加上查询区间会被放在左边的个数 int newr=newl+cnt-1; return query(L,mid,newl,newr,dep+1,k); } else{ /*if(s>0){ if(ss>0) ans-=sum[dep+1][L+s+ss-1] - sum[dep+1][L+ss-1]; else ans-=sum[dep+1][L+s-1]; }*/ int newr=r+toleft[dep][R]-toleft[dep][r]; int newl=newr-(r-l-cnt); return query(mid+1,R,newl,newr,dep+1,k-cnt); } } int solve(int n,int s,int t,int h){ int l=1,r=t-s+1,mid,ans=0; while(l<=r){ mid=(l+r)/2; int tmp=query(1,n,s,t,0,mid); if(tmp<=h){ ans=mid; l=mid+1; } else{ r=mid-1; } } return ans; } int main(){ //freopen("in.txt","r",stdin); int T; int n,m; int s,t,k,h; scanf("%d",&T); int C=T; while(T--) { printf("Case %d:\n",C-T); scanf("%d%d",&n,&m); memset(tree,0,sizeof(tree)); for(int i=1;i<=n;i++){ scanf("%d",&tree[0][i]); sorted[i]=tree[0][i]; } sort(sorted+1,sorted+n+1); build(1,n,0); while(m--){ scanf("%d%d%d",&s,&t,&h); s++,t++; printf("%d\n",solve(n,s,t,h)); } } return 0; }
hdu-2665 求区间第K大的数
View Code
#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> using namespace std; const int MAXN = 100010; int tree[30][MAXN];//表示每层每个位置的值 int sorted[MAXN];//已经排序的数 int toleft[30][MAXN];//toleft[p][i]表示第i层从1到i有多少个数分入左边 void build(int l,int r,int dep){ if(l==r) return ; int mid = (l+r)/2; int same = mid-l+1;//表示等于中间值而且被分入左边的个数 for(int i=l;i<=r;i++) if(tree[dep][i]<sorted[mid]) same--; int lpos=l; int rpos=mid+1; for(int i=l;i<=r;i++){ if(tree[dep][i]<sorted[mid])//比中间的数小，分入左边 tree[dep+1][lpos++]=tree[dep][i]; else if(tree[dep][i]==sorted[mid] && same>0){ tree[dep+1][lpos++]=tree[dep][i]; same--; } else{//比中间值大，分入右边 tree[dep+1][rpos++]=tree[dep][i]; } toleft[dep][i]=toleft[dep][l-1]+lpos-l;//从1到i放左边的个数 } build(l,mid,dep+1); build(mid+1,r,dep+1); } //查询区间第k大的数，[L,R]是大区间，[l,r]是要查询的小区间 int query(int L,int R,int l,int r,int dep,int k){ if(l==r) return tree[dep][l]; int mid=(L+R)/2; int cnt=toleft[dep][r]-toleft[dep][l-1]; if(cnt>=k){ //L+要查询的区间前被放在左边的个数 int newl=L+toleft[dep][l-1]-toleft[dep][L-1]; //左端点加上查询区间会被放在左边的个数 int newr=newl+cnt-1; return query(L,mid,newl,newr,dep+1,k); } else{ int newr=r+toleft[dep][R]-toleft[dep][r]; int newl=newr-(r-l-cnt); return query(mid+1,R,newl,newr,dep+1,k-cnt); } } int main(){ int T; int n,m; int s,t,k; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); memset(tree,0,sizeof(tree)); for(int i=1;i<=n;i++){ scanf("%d",&tree[0][i]); sorted[i]=tree[0][i]; } sort(sorted+1,sorted+n+1); build(1,n,0); while(m--){ scanf("%d%d%d",&s,&t,&k); printf("%d\n",query(1,n,s,t,0,k)); } } return 0; }
hdu-4251 求区间中间值[k=(t-s)/2+1]
View Code
#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> using namespace std; const int MAXN = 100010; int tree[30][MAXN];//表示每层每个位置的值 int sorted[MAXN];//已经排序的数 int toleft[30][MAXN];//toleft[p][i]表示第i层从1到i有多少个数分入左边 void build(int l,int r,int dep){ if(l==r) return ; int mid = (l+r)/2; int same = mid-l+1;//表示等于中间值而且被分入左边的个数 for(int i=l;i<=r;i++) if(tree[dep][i]<sorted[mid]) same--; int lpos=l; int rpos=mid+1; for(int i=l;i<=r;i++){ if(tree[dep][i]<sorted[mid])//比中间的数小，分入左边 tree[dep+1][lpos++]=tree[dep][i]; else if(tree[dep][i]==sorted[mid] && same>0){ tree[dep+1][lpos++]=tree[dep][i]; same--; } else{//比中间值大，分入右边 tree[dep+1][rpos++]=tree[dep][i]; } toleft[dep][i]=toleft[dep][l-1]+lpos-l;//从1到i放左边的个数 } build(l,mid,dep+1); build(mid+1,r,dep+1); } //查询区间第k大的数，[L,R]是大区间，[l,r]是要查询的小区间 int query(int L,int R,int l,int r,int dep,int k){ if(l==r) return tree[dep][l]; int mid=(L+R)/2; int cnt=toleft[dep][r]-toleft[dep][l-1]; if(cnt>=k){ //L+要查询的区间前被放在左边的个数 int newl=L+toleft[dep][l-1]-toleft[dep][L-1]; //左端点加上查询区间会被放在左边的个数 int newr=newl+cnt-1; return query(L,mid,newl,newr,dep+1,k); } else{ int newr=r+toleft[dep][R]-toleft[dep][r]; int newl=newr-(r-l-cnt); return query(mid+1,R,newl,newr,dep+1,k-cnt); } } int main(){ int T; int n,m; int s,t,k; int C=0; while(scanf("%d",&n)!=EOF){ printf("Case %d:\n",++C); memset(tree,0,sizeof(tree)); for(int i=1;i<=n;i++){ scanf("%d",&tree[0][i]); sorted[i]=tree[0][i]; } sort(sorted+1,sorted+n+1); build(1,n,0); scanf("%d",&m); while(m--){ scanf("%d%d",&s,&t); k=(t-s)/2+1; printf("%d\n",query(1,n,s,t,0,k)); } } return 0; }
hdu-3473 求区间中间值与区间其他值的差的绝对值之和。
需要理解并修改模板。
View Code
#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> using namespace std; const int MAXN = 100010; int tree[20][MAXN];//表示每层每个位置的值 int sorted[MAXN];//已经排序的数 int toleft[20][MAXN];//toleft[p][i]表示第i层从1到i有多少个数分入左边 long long sum[20][MAXN]; void build(int l,int r,int dep){ //if(l==r) return ; if(l==r){ sum[dep][l]=tree[dep][l]; return ; } int mid = (l+r)/2; int same = mid-l+1;//表示等于中间值而且被分入左边的个数 /*for(int i=l;i<=r;i++) if(tree[dep][i]<sorted[mid]) same--;*/ for(int i=l;i<=r;i++){ if(tree[dep][i]<sorted[mid]) same--; sum[dep][i]=tree[dep][i]; if(i>l) sum[dep][i]+=sum[dep][i-1]; } int lpos=l; int rpos=mid+1; for(int i=l;i<=r;i++){ if(tree[dep][i]<sorted[mid])//比中间的数小，分入左边 tree[dep+1][lpos++]=tree[dep][i]; else if(tree[dep][i]==sorted[mid] && same>0){ tree[dep+1][lpos++]=tree[dep][i]; same--; } else{//比中间值大，分入右边 tree[dep+1][rpos++]=tree[dep][i]; } toleft[dep][i]=toleft[dep][l-1]+lpos-l;//从1到i放左边的个数 } build(l,mid,dep+1); build(mid+1,r,dep+1); } long long ans; //查询区间第k大的数，[L,R]是大区间，[l,r]是要查询的小区间 int query(int L,int R,int l,int r,int dep,int k){ if(l==r) return tree[dep][l]; int mid=(L+R)/2; int cnt=toleft[dep][r]-toleft[dep][l-1]; int ss=toleft[dep][l-1]-toleft[dep][L-1]; int ee=l-L-ss; int s =toleft[dep][r]-toleft[dep][l-1]; int e =r-l+1-s; if(cnt>=k){ if(e>0){ if(ee>0) ans+=sum[dep+1][mid+e+ee] - sum[dep+1][mid+ee]; else ans+=sum[dep+1][mid+e]; } //L+要查询的区间前被放在左边的个数 int newl=L+toleft[dep][l-1]-toleft[dep][L-1]; //左端点加上查询区间会被放在左边的个数 int newr=newl+cnt-1; return query(L,mid,newl,newr,dep+1,k); } else{ if(s>0){ if(ss>0) ans-=sum[dep+1][L+s+ss-1] - sum[dep+1][L+ss-1]; else ans-=sum[dep+1][L+s-1]; } int newr=r+toleft[dep][R]-toleft[dep][r]; int newl=newr-(r-l-cnt); return query(mid+1,R,newl,newr,dep+1,k-cnt); } } int main(){ int T; int n,m; int s,t,k; scanf("%d",&T); int C=T; while(T--) { printf("Case #%d:\n",C-T); scanf("%d",&n); memset(tree,0,sizeof(tree)); for(int i=1;i<=n;i++){ scanf("%d",&tree[0][i]); sorted[i]=tree[0][i]; } sort(sorted+1,sorted+n+1); build(1,n,0); scanf("%d",&m); while(m--){ scanf("%d%d",&s,&t); s++,t++; k=(t-s)/2+1; ans=0; int mid=query(1,n,s,t,0,k); /*long long sum=0; for(int i=s;i<=t;i++){ sum+=abs(tree[0][i]-mid); }*/ if((t-s+1)%2==0){ ans-=mid; } printf("%I64d\n",ans); } printf("\n"); } return 0; }