首页 > 代码库 > POJ2104 K-th Number [分块做法]
POJ2104 K-th Number [分块做法]
传送：主席树做法http://www.cnblogs.com/candy99/p/6160704.html
做那倒带修改的主席树时就发现分块可以做，然后就试了试
思想和教主的魔法差不多，只不过那个是求>=v的有几个
既然一个数v的名次可以求，我们二分这个数就行了啊
然而......
首先，你二分到的这个数不一定在区间里出现过
比如 1 2 5 8 9
4和5的名次都是3
于是，我修改了某个区间名次的定义：
“如果一个数的名次是x，但是区间中没有次数，那么他的名次为x-1”
实现上只需要find里return l-t+(b[l]==v) 等于说明出现过
然而
该死不写了鬼知道怎么回事用主席树就行了
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;const int N=1e5+500;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}int n,Q,a[N],bl,m,b[N],pos[N];int mp[N];void reset(int x){ int l=(x-1)*bl+1,r=min(x*bl,n); for(int i=l;i<=r;i++) b[i]=a[i]; sort(b+l,b+r+1);}int flag;int find(int x,int v){ int l=(x-1)*bl+1,r=min(x*bl,n),t=l; while(l<=r){ int mid=(l+r)>>1; if(b[mid]<v) l=mid+1; else r=mid-1; } if(b[l]==v) flag=1; return l-t+1;//!}int rank(int l,int r,int v){ int ans=0; flag=0; if(pos[l]==pos[r]){ for(int i=l;i<=r;i++) if(a[i]<=v) ans++,flag=flag||a[i]==v; }else{ int t=pos[l]*bl; for(int i=l;i<=t;i++) if(a[i]<=v) ans++,flag=flag||a[i]==v; for(int i=(pos[r]-1)*bl+1;i<=r;i++) if(a[i]<=v) ans++,flag=flag||a[i]==v; for(int i=pos[l]+1;i<pos[r];i++) ans+=find(i,v); } if(!flag) ans--; return ans;}int query(int ql,int qr,int k){ int l=1,r=n; while(l<=r){ int mid=(l+r)>>1; int t=rank(ql,qr,mp[mid]); if(t<k) l=mid+1; else r=mid-1; } return l;}int main(){ freopen("in.txt","r",stdin); freopen("1.out","w",stdout); n=read();Q=read(); bl=sqrt(n); m=n/bl;if(n%bl) m++; for(int i=1;i<=n;i++) a[i]=mp[i]=read(),pos[i]=(i-1)/bl+1; for(int i=1;i<=m;i++) reset(i); sort(mp+1,mp+1+n); while(Q--){ int i=read(),j=read(),k=read(); printf("%d\n",mp[query(i,j,k)]); }}
#include <map>#include <set>#include <stack>#include <queue>#include <cmath>#include <string>#include <vector>#include <cstdio>#include <cctype>#include <cstring>#include <sstream>#include <cstdlib>#include <iostream>#include <algorithm>#pragma comment(linker,"/STACK:102400000,102400000")using namespace std;#define MAX 100005#define MAXN 1000005#define maxnode 15#define sigma_size 30#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define lrt rt<<1#define rrt rt<<1|1#define middle int m=(r+l)>>1#define LL long long#define ull unsigned long long#define mem(x,v) memset(x,v,sizeof(x))#define lowbit(x) (x&-x)#define pii pair<int,int>#define bits(a) __builtin_popcount(a)#define mk make_pair#define limit 10000//const int prime = 999983;const int INF = 0x3f3f3f3f;const LL INFF = 0x3f3f;const double pi = acos(-1.0);const double inf = 1e18;const double eps = 1e-8;const LL mod = 1e9+7;const ull mx = 133333331;/*****************************************************/inline void RI(int &x) { char c; while((c=getchar())<‘0‘ || c>‘9‘); x=c-‘0‘; while((c=getchar())>=‘0‘ && c<=‘9‘) x=(x<<3)+(x<<1)+c-‘0‘; }/*****************************************************/int a[MAX];int b[MAX];int c[MAX];int tmp;bool judge(int x,int l,int r,int k){ int a1=l/tmp; int a2=r/tmp; int sum=0;//for(int i=l;i<=r;i++) printf("%d ",a[i]);puts(""); if(a1==a2){ for(int i=l;i<=r;i++) if(a[i]<=c[x]) sum++; if(sum>=k) return true; return false; } for(int i=a1+1;i<a2;i++){ sum+=upper_bound(b+i*tmp,b+(i+1)*tmp,c[x])-b-i*tmp; } for(int i=l;i<(a1+1)*tmp;i++) if(a[i]<=c[x]) sum++; for(int i=a2*tmp;i<=r;i++) if(a[i]<=c[x]) sum++; //printf("ra %d %d %d %d\n",l,r,c[x],sum); if(sum>=k) return true; return false;}int main(){ freopen("in.txt","r",stdin); freopen("2.out","w",stdout); int n,m; scanf("%d%d",&n,&m); tmp=sqrt(n); for(int i=0;i<n;i++){ scanf("%d",&a[i]); b[i]=a[i]; c[i]=a[i]; } sort(c,c+n); for(int i=0;i*tmp<n;i++){ if((i+1)*tmp<=n) sort(b+i*tmp,b+(i+1)*tmp); else sort(b+i*tmp,b+n); } while(m--){ int l,r,k; scanf("%d%d%d",&l,&r,&k); int ll=0,rr=n-1; while(ll<=rr){ int mid=(ll+rr)>>1; if(judge(mid,l-1,r-1,k)) rr=mid-1; else ll=mid+1; } printf("%d\n",c[ll]); } return 0;}
POJ2104 K-th Number [分块做法]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。