首页 > 代码库 > 【块状链表】【权值分块】bzoj3065 带插入区间K小值
【块状链表】【权值分块】bzoj3065 带插入区间K小值
显然是块状链表的经典题。但是经典做法的复杂度是O(n*sqrt(n)*log(n)*sqrt(log(n)))的，出题人明确说了会卡掉。
于是我们考虑每个块内记录前n个块的权值分块。
查询的时候差分什么的，复杂度就是O(n*sqrt(n))的了。
插入的时候为了防止块过大，要考虑裂块(细节较多)。
感谢bzoj提供O2，我的STL块链才能通过(list+vector)。
#include<cstdio>#include<list>#include<vector>#include<cmath>#include<algorithm>using namespace std;#define X first#define Y secondint num[70001],l[270],Limit,ans,n,tmp[35001],x,y,val,m;char op[1];struct VAL_BLOCK{ int b[70001],sumv[270]; void insert(const int &x){++b[x]; ++sumv[num[x]];} void erase(const int &x){--b[x]; --sumv[num[x]];}}S;struct BLOCK{ vector<int>v; VAL_BLOCK T; BLOCK(){}};list<BLOCK>List;typedef list<BLOCK>::iterator LER;typedef vector<int>::iterator VER;typedef pair<LER,VER> Pair;Pair Find(const int &p){ int cnt=0; LER i=List.begin(); for(;i!=List.end();++i) { cnt+=(*i).v.size(); if(cnt>=p) { cnt-=(*i).v.size(); for(VER j=(*i).v.begin();j!=(*i).v.end();++j) if((++cnt)==p) return make_pair(i,j); } } --i; return make_pair(i,(*i).v.end());}void Insert(const int &p,const int &V){ Pair Bel=Find(p); (*Bel.X).v.insert(Bel.Y,V); for(LER i=Bel.X;i!=List.end();++i) (*i).T.insert(V); if((*Bel.X).v.size()>Limit) { LER Near=Bel.X; ++Near; int Last=(*Bel.X).v.back(); if((*Near).v.size()>Limit || Near==List.end()) { Near=List.insert(Near,BLOCK()); (*Near).T=(*Bel.X).T; } (*Near).v.insert((*Near).v.begin(),Last); (*Bel.X).T.erase(Last); (*Bel.X).v.pop_back(); }}void Update(const int &p,const int &V){ Pair Bel=Find(p); for(LER i=Bel.X;i!=List.end();++i) (*i).T.erase(*Bel.Y), (*i).T.insert(V); (*Bel.Y)=V;}int Kth(const int &L,const int &R,const int &K){ Pair P1=Find(L),P2=Find(R); int cnt=0,res; if(P1.X==P2.X) { for(VER i=P1.Y;i<=P2.Y;++i) S.insert(*i); for(int i=1;;++i) { cnt+=S.sumv[i]; if(cnt>=K) { cnt-=S.sumv[i]; for(int j=l[i];;++j) { cnt+=S.b[j]; if(cnt>=K) {res=j; goto OUT2;} } } } OUT2: for(VER i=P1.Y;i<=P2.Y;++i) S.erase(*i); return res; } for(VER i=P1.Y;i!=(*P1.X).v.end();++i) S.insert(*i); for(VER i=(*P2.X).v.begin();i<=P2.Y;++i) S.insert(*i); LER LB=P1.X,RB=P2.X; --RB; for(int i=1;;++i) { cnt+=((*RB).T.sumv[i]-(*LB).T.sumv[i]+S.sumv[i]); if(cnt>=K) { cnt-=((*RB).T.sumv[i]-(*LB).T.sumv[i]+S.sumv[i]); for(int j=l[i];;++j) { cnt+=((*RB).T.b[j]-(*LB).T.b[j]+S.b[j]); if(cnt>=K) {res=j; goto OUT;} } } } OUT: for(VER i=P1.Y;i!=(*P1.X).v.end();++i) S.erase(*i); for(VER i=(*P2.X).v.begin();i<=P2.Y;++i) S.erase(*i); return res;}void Val_Makeblock(){ int tot=1,sz=sqrt(70000); if(!sz) sz=1; for(;tot*sz<=70000;++tot) { l[tot]=(tot-1)*sz; int R=tot*sz-1; for(int i=l[tot];i<=R;++i) num[i]=tot; } l[tot]=(tot-1)*sz; for(int i=l[tot];i<=70000;++i) num[i]=tot;}void Makeblock(){ int sz=sqrt(n),tot=1; if(!sz) sz=1; Limit=sqrt(n+35000); for(;tot*sz<n;++tot) { LER End=List.insert(List.end(),BLOCK()); (*End).v.assign(tmp+(tot-1)*sz+1,tmp+tot*sz+1); } LER End=List.insert(List.end(),BLOCK()); (*End).v.assign(tmp+(tot-1)*sz+1,tmp+n+1);}void Init_Ts(){ LER i=List.begin(); for(VER j=(*i).v.begin();j!=(*i).v.end();++j) (*i).T.insert(*j); ++i; for(LER Front=List.begin();i!=List.end();++i,++Front) { (*i).T=(*Front).T; for(VER j=(*i).v.begin();j!=(*i).v.end();++j) (*i).T.insert(*j); }}int main(){ scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&tmp[i]); Makeblock(); Val_Makeblock(); Init_Ts(); scanf("%d",&m); for(;m;--m) { scanf("%s%d",op,&x); x^=ans; if(op[0]==‘Q‘) { scanf("%d%d",&y,&val); y^=ans; val^=ans; printf("%d\n",ans=Kth(x,y,val)); } else if(op[0]==‘M‘) { scanf("%d",&val); val^=ans; Update(x,val); } else { scanf("%d",&val); val^=ans; Insert(x,val); } } return 0;}【块状链表】【权值分块】bzoj3065 带插入区间K小值
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。