首页 > 代码库 > 【莫队算法】【权值分块】poj2104 K-th Number / poj2761 Feed the dogs
【莫队算法】【权值分块】poj2104 K-th Number / poj2761 Feed the dogs
先用莫队算法保证在询问之间转移的复杂度，每次转移都需要进行O(sqrt(m))次插入和删除，权值分块的插入/删除是O(1)的。
然后询问的时候用权值分块查询区间k小值，每次是O(sqrt(n))的。
所以总共的复杂度是O(m*(sqrt(n)+sqrt(m)))的。
常数极小。
别的按权值维护的数据结构无法做到O(1)地插入删除。
poj2104 的输出优化 别忘了处理负数。
完爆主席树，这份代码目前在 poj2761 上 Rank1。
| Rank | Run ID | User | Memory | Time | Language | Code Length | Submit Time |
|---|---|---|---|---|---|---|---|
| 1 | 13702017(2) | lizitong | 4056K | 579MS | G++ | 2455B | 2014-12-10 13:00:22 |
#include<cstdio>#include<algorithm>#include<cmath>using namespace std;int Num,CH[12],f,c;inline void R(int &x){ c=0;f=1; for(;c<‘0‘||c>‘9‘;c=getchar())if(c==‘-‘)f=-1; for(x=0;c>=‘0‘&&c<=‘9‘;c=getchar())(x*=10)+=(c-‘0‘); x*=f;}inline void P(int x){ if(x<10)putchar(x+‘0‘); else{P(x/10);putchar(x%10+‘0‘);}}struct Point{int v,p;}t[100001];struct Ask{int l,r,k,p;}Q[5001];int n,m,a[100001],ma[100001],en,num[100001],num2[100001];int l[330],r[330],sumv[330],b[100001],sum=1,anss[5001];bool operator < (const Point &a,const Point &b){return a.v<b.v;}bool operator < (const Ask &a,const Ask &b){return num2[a.l]!=num2[b.l] ? num2[a.l]<num2[b.l] : a.r<b.r;}void Mo_Make_Block(){ int sum=1,sz=sqrt(n); if(!sz) sz=1; for(;sum*sz<n;++sum) { int r=sum*sz; for(int i=(sum-1)*sz+1;i<=r;++i) num2[i]=sum; } for(int i=(sum-1)*sz+1;i<=n;++i) num2[i]=sum;}void Val_Make_Block(){ int sz=sqrt(en); if(!sz) sz=1; for(;sum*sz<en;++sum) { l[sum]=r[sum-1]+1; r[sum]=sum*sz; for(int i=l[sum];i<=r[sum];++i) num[i]=sum; } l[sum]=r[sum-1]+1; r[sum]=en; for(int i=l[sum];i<=r[sum];++i) num[i]=sum;}void Insert(const int &x){++b[x]; ++sumv[num[x]];}void Delete(const int &x){--b[x]; --sumv[num[x]];}int Kth(const int &x){ int cnt=0; for(int i=1;;i++) { cnt+=sumv[i]; if(cnt>=x) { cnt-=sumv[i]; for(int j=l[i];;j++) {cnt+=b[j]; if(cnt>=x) return j;} } }}int main(){ R(n); R(m); for(int i=1;i<=n;++i) {R(t[i].v); t[i].p=i;} sort(t+1,t+n+1); ma[a[t[1].p]=++en]=t[1].v; for(int i=2;i<=n;++i) { if(t[i].v!=t[i-1].v) ++en; ma[a[t[i].p]=en]=t[i].v; } Val_Make_Block(); for(int i=1;i<=m;++i) { R(Q[i].l); R(Q[i].r); R(Q[i].k); Q[i].p=i; } Mo_Make_Block(); sort(Q+1,Q+m+1); for(int i=Q[1].l;i<=Q[1].r;++i) Insert(a[i]); anss[Q[1].p]=ma[Kth(Q[1].k)]; for(int i=2;i<=m;++i) { if(Q[i].l<Q[i-1].l) for(int j=Q[i-1].l-1;j>=Q[i].l;--j) Insert(a[j]); else for(int j=Q[i-1].l;j<Q[i].l;++j) Delete(a[j]); if(Q[i].r<Q[i-1].r) for(int j=Q[i-1].r;j>Q[i].r;--j) Delete(a[j]); else for(int j=Q[i-1].r+1;j<=Q[i].r;++j) Insert(a[j]); anss[Q[i].p]=ma[Kth(Q[i].k)]; } for(int i=1;i<=m;++i) P(anss[i]),puts(""); return 0;}
【莫队算法】【权值分块】poj2104 K-th Number / poj2761 Feed the dogs
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。