弱省胡策Round6 A
大意:首先注意到就是求出一个最大的循环串集合,使得集合中的任意两个循环串在模$a$意义下相等或者模$b$意义下相等.
思路:首先找出哪些循环串是模$a$相等的,哪些循环串是模$b$相等的,然后找出模$a$相等的最大集合,再找出模$b$相等的最大集合,取个最大值.
利用反证法易证这样是对的.
利用hash很容易实现,时间$O(n)$.
#include#include #include #include #include using namespace std; typedef long long ll; typedef pair pii; #define N 1000010 int A[N<<1],B[N<<1]; struct Hash_system{ static const int mod1=1000000007; static const int mod2=1000000009; static const int seed1=200019; static const int seed2=13131; int f1[N<<1],f2[N<<1],pow1[N<<1],pow2[N<<1]; inline void init(){ int i; for(pow1[0]=1,i=1;i<=2000000;++i) pow1[i]=(ll)pow1[i-1]*seed1%mod1; for(pow2[0]=1,i=1;i<=2000000;++i) pow2[i]=(ll)pow2[i-1]*seed2%mod2; } inline void input(int A[],int n){ f1[n+1]=f2[n+1]=0; for(int i=n;i>=1;--i){ f1[i]=((ll)f1[i+1]*seed1+A[i])%mod1; f2[i]=((ll)f2[i+1]*seed2+A[i])%mod2; } } pii gethash(int l,int r){ int h1=(f1[l]-(ll)f1[r+1]*pow1[r-l+1]%mod1+mod1)%mod1; int h2=(f2[l]-(ll)f2[r+1]*pow2[r-l+1]%mod2+mod2)%mod2; return make_pair(h1,h2); } }H; pii seq[N]; int main(){ int T; cin>>T; int i,j; H.init(); while(T--){ int n,a,b; cin>>n>>a>>b; for(i=1;i<=n;++i) scanf("%d",&A;[i]); for(i=n+1;i<2*n;++i) A[i]=A[i-n]; int ans=0; for(i=1;i<2*n;++i) B[i]=A[i]%a; H.input(B,2*n-1); for(i=1;i<=n;++i) seq[i]=H.gethash(i,i+n-1); sort(seq+1,seq+n); for(i=1;i<=n;){ for(j=i;j!=n&&seq;[j]==seq[j+1];++j); ans=max(ans,j-i+1); i=j+1; } for(i=1;i<2*n;++i) B[i]=A[i]%b; H.input(B,2*n-1); for(i=1;i<=n;++i) seq[i]=H.gethash(i,i+n-1); sort(seq+1,seq+n); for(i=1;i<=n;){ for(j=i;j!=n&&seq;[j]==seq[j+1];++j); ans=max(ans,j-i+1); i=j+1; } cout<<(ans==1?0:ans)<
弱省胡策Round6 B
思路:首先将树树链剖分,则任何一颗联通的子树都必定可以用一条链上的一段作为主链来表示,主链上的每个点会向下连出一些子链,我们仅需考虑子链的最大前缀和,若其$>0$,则加到这个点的点权中.然后再搞出这个链的最大子段和更新答案.
维护一个全局堆记录所有重链的最大子段和.
考虑修改,只需要修改这个点的权值,更新链的最大子段和,在堆中修改,然后更新父亲重链的点权,并以此类推就行了.
时间复杂度$O(log^2n)$.
我的代码在ch上不明所以的RE,本地可以AC.
#include#include #include #include #include #include using namespace std; multiset s; #define N 100010 #define l(x) S[x].l #define r(x) S[x].r struct Ans{ int lm,rm,sum,mx; inline void add(int x){ lm+=x; rm+=x; sum+=x; mx+=x; } }; struct Node{ int l,r; Ans v; }S[N<<1]; Ans merge(const Ans&l;,const Ans&r;){ Ans re; re.lm=max(l.lm,l.sum+max(0,r.lm)); re.rm=max(r.rm,r.sum+max(0,l.rm)); re.sum=l.sum+r.sum; re.mx=max(max(l.mx,r.mx),l.rm+r.lm); return re; } int cnt; inline int build(int tl,int tr){ int q=++cnt; if(tl==tr) return q; int mid=(tl+tr)>>1; l(q)=build(tl,mid); r(q)=build(mid+1,tr); return q; } inline void up(int x){ S[x].v=merge(S[l(x)].v,S[r(x)].v); } inline void add(int q,int tl,int tr,int ins,int v){ if(tl==tr){ S[q].v.add(v); return; } int mid=(tl+tr)>>1; if(ins<=mid) add(l(q),tl,mid,ins,v); else add(r(q),mid+1,tr,ins,v); up(q); } inline Ans Query(int q,int tl,int tr,int dl,int dr){ if(dl<=tl&&tr;<=dr) return S[q].v; int mid=(tl+tr)>>1; if(dr<=mid) return Query(l(q),tl,mid,dl,dr); else if(dl>mid) return Query(r(q),mid+1,tr,dl,dr); else return merge(Query(l(q),tl,mid,dl,mid),Query(r(q),mid+1,tr,mid+1,dr)); } int head[N],next[N<<1],end[N<<1]; inline void addedge(int a,int b){ static int q=1; end[q]=b; next[q]=head[a]; head[a]=q++; } inline void make(int a,int b){ addedge(a,b); addedge(b,a); } int v[N],_v[N]; int siz[N],son[N],id,p_id[N],id_p[N],dep[N],top[N],pa[N]; inline void dfs(int x,int fa){ siz[x]=1; int Max_siz=0; for(int j=head[x];j;j=next[j]){ if(end[j]!=fa){ dep[end[j]]=dep[x]+1; pa[end[j]]=x; dfs(end[j],x); siz[x]+=siz[end[j]]; if(siz[end[j]]>Max_siz){ Max_siz=siz[end[j]]; son[x]=end[j]; } } } } int lab[N],num=1,_begin[N],_end[N]; inline void create(int x,int Top){ top[x]=Top; p_id[x]=++id; id_p[id]=x; lab[id]=num; if(son[x]) create(son[x],Top); else ++num; for(int j=head[x];j;j=next[j]) if(end[j]!=pa[x]&&end;[j]!=son[x]) create(end[j],end[j]); } int n,m; inline void Modify(int x,int y){ Ans tmp=Query(1,1,n,_begin[p_id[x]],_end[p_id[x]]); int lastlm=tmp.lm,lastmx=tmp.mx,_lastlm,_lastmx; int nowlm,nowmx; add(1,1,n,p_id[x],-v[x]+y); v[x]=y; while(1){ tmp=Query(1,1,n,_begin[p_id[x]],_end[p_id[x]]); nowlm=tmp.lm,nowmx=tmp.mx; s.erase(s.find(lastmx)),s.insert(nowmx); if(pa[top[x]]){ tmp=Query(1,1,n,_begin[p_id[pa[top[x]]]],_end[p_id[pa[top[x]]]]); _lastlm=tmp.lm,_lastmx=tmp.mx; if(lastlm<=0&&nowlm;>0) add(1,1,n,p_id[pa[top[x]]],nowlm); else if(lastlm>0&&nowlm;<=0) add(1,1,n,p_id[pa[top[x]]],-lastlm); else if(lastlm>0&&nowlm;>0) add(1,1,n,p_id[pa[top[x]]],-lastlm+nowlm); x=pa[top[x]]; lastlm=_lastlm; lastmx=_lastmx; } else break; } } int main(){ //freopen("tt.in","r",stdin); cin>>n>>m; int i,j,k; for(i=1;i<=n;++i) scanf("%d",&_v[i]); int a,b; for(i=1;i <=n;){ for(j=i;j!=n&&lab;[j]==lab[j+1];++j); for(k=i;k<=j;++k) _begin[k]=i,_end[k]=j; i=j+1; } for(i=1;i<=num-1;++i) s.insert(0); build(1,n); for(i=1;i<=n;++i) Modify(i,_v[i]); int qte,x,y; while(m--){ scanf("%d",&qte;); if(qte==2){ multiset ::iterator it=s.end(); printf("%d\n",max(0,*(--it))); } else{ scanf("%d%d",&x;,&y;); Modify(x,y); } } return 0; }
弱省胡策Round6 C
想了好长时间的性质,结果发现是暴力题,稍微加了一点可行性剪枝就过了.
出题人我@$#^$%&$%#@^%#$&$%&...
#include#include #include #include #include #include using namespace std; multiset s; #define N 2010 int a[N]; int main(){ //freopen("tt.in","r",stdin); int T; cin>>T; int n,m,i,j; while(T--){ cin>>n>>m; int sum=0,Max=0; for(i=1;i<=n;++i){ scanf("%d",&a;[i]); sum+=a[i]; Max=max(Max,a[i]); } int ans; for(ans=max(Max,sum/m);ans<=sum;++ans){ int tim=0,last; for(i=1;i<=n;++i) s.insert(a[i]); while(!(s.begin()==s.end())){ ++tim; last=ans; while(1){ if(s.begin()==s.end()) break; multiset ::iterator it=s.upper_bound(last); if(it==s.begin()||last<*(--it)) break; last-=*it; s.erase(s.find(*it)); //for(multiset ::iterator it=s.begin();it!=s.end();++it)printf("%d ",*it);puts(""); } } //printf("%d ",tim); if(tim<=m) break; } cout< <
WC2014紫荆花之恋
orz jkxing!orz orz orz!
我现在终于明白正确的动态树分治是什么鬼啦...
我们并不是对于每个分治结构在里面维护每个子树的信息,而是直接把每个子树的信息维护到对应的子结构里面去就行啦!
还有,求每个点在分治结构中的贡献,用一个全局的lca倍增就行了,也不用单独在分治结构中维护!
一般来说,这种路径信息全局的lca应该都足以解决了.
于是我现在又要开动啦!
upd:现在一些恶心的点爆栈,剩下的还是都能过的,80分.
#include#include #include #include #include #include #include using namespace std; typedef long long ll; #define ls ch[0] #define rs ch[1] #define N 100010 namespace Treap{ struct Node{ Node*ch[2]; int v,p,s; Node():s(0){} inline void up(){ s=ls->s+rs->s+1; } }mem[N*50],*G=mem,Tnull,*null=&Tnull; stack bin; inline Node*newnode(int _v){ Node*re; if(!bin.empty()){ re=bin.top(); bin.pop(); } else re=G++; re->ls=re->rs=null; re->v=_v; re->p=rand(); re->s=1; return re; } inline void Rot(Node*&p;,bool d){ Node*q=p->ch[!d]; p->ch[!d]=q->ch[d]; q->ch[d]=p; p->up(); q->up(); p=q; } inline void insert(Node*&p;,int v){ if(p==null) p=newnode(v); else if(v v){ insert(p->ls,v); if(p->ls->p p) Rot(p,1); } else{ insert(p->rs,v); if(p->rs->p p) Rot(p,0); } p->up(); } inline int query(Node*p,int v){ if(p==null) return 0; if(v v) return 1+p->rs->s+query(p->ls,v); else return query(p->rs,v)+(p->v>=v); } inline void recover(Node*p){ if(p==null) return; if(p->ls!=null) recover(p->ls); if(p->rs!=null) recover(p->rs); bin.push(p); } void dfs(Node*p){ if(p->ls!=null) dfs(p->ls); printf("%d ",p->v); if(p->rs!=null) dfs(p->rs); } } int head[N],next[N<<1],end[N<<1],len[N<<1]; inline void addedge(int a,int b,int l){ static int q=1; end[q]=b; next[q]=head[a]; head[a]=q; len[q++]=l; } inline void make(int a,int b,int l){ addedge(a,b,l); addedge(b,a,l); } int dep[N],_dep[N],pa[N][21]; inline int lca(int x,int y){ if(dep[x] =0;--i) if(dep[pa[x][i]]>=dep[y]) x=pa[x][i]; if(x==y) return x; for(int i=20;i>=0;--i) if(pa[x][i]!=pa[y][i]) x=pa[x][i],y=pa[y][i]; return pa[x][0]; } inline int getdist(int x,int y){ return _dep[x]+_dep[y]-(_dep[lca(x,y)]<<1); } ll ans; int r[N]; struct Array{ int t[N],a[N],tclock; inline int operator[](const int&x;){ if(t[x]!=tclock){ t[x]=tclock; a[x]=0; } return a[x]; } inline void ch(int x,int d){ t[x]=tclock; a[x]=d; } }in; namespace Dynamic_System{ struct Tnode{ Tnode*pa; Treap::Node*root,*_root; set son; int up,g,siz; }mem[N],*G=mem,Tnull,*null=&Tnull;,*ins[N]; stack bin; inline Tnode*newnode(){ Tnode*re; if(!bin.empty()){ re=bin.top(); bin.pop(); } else re=G++; re->pa=null; re->root=Treap::null; re->_root=Treap::null; re->son.clear(); return re; } inline Tnode*sNode(int x){ Tnode*re=newnode(); re->g=re->up=x; re->siz=1; Treap::insert(re->root,r[x]); return re; } inline void recover(Tnode*p){ for(set ::iterator it=p->son.begin();it!=p->son.end();++it) recover(*it); in.ch(p->g,1); Treap::recover(p->root); Treap::recover(p->_root); p->son.clear(); bin.push(p); } inline Tnode*divide(int x,int pdis){ static int q[N],_pa[N],ms[N],siz[N],d[N]; //static int g,mins; //static Tnode*re,*tmp; static int fr,ta,g,mins; int i,j; static Tnode*tmp; Tnode*re; _pa[x]=0; d[x]=0; fr=ta=0; q[ta++]=x; re=newnode(); re->up=x; while(fr!=ta){ i=q[fr++]; Treap::insert(re->_root,r[i]-(d[i]+pdis)); for(j=head[i];j;j=next[j]) if(end[j]!=_pa[i]&∈[end[j]]){ _pa[end[j]]=i; d[end[j]]=d[i]+len[j]; q[ta++]=end[j]; } } mins=0x3f3f3f3f; for(i=0;i =0;--i){ ms[q[i]]=max(ms[q[i]],ta-siz[q[i]]); if(mins>ms[q[i]]){ mins=ms[q[i]]; g=q[i]; } ms[_pa[q[i]]]=max(ms[_pa[q[i]]],siz[q[i]]); siz[_pa[q[i]]]+=siz[q[i]]; } ins[re->g=g]=re; re->siz=ta; _pa[g]=0; d[g]=0; fr=ta=0; q[ta++]=g; while(fr!=ta){ i=q[fr++]; Treap::insert(re->root,r[i]-d[i]); for(j=head[i];j;j=next[j]) if(end[j]!=_pa[i]&∈[end[j]]){ _pa[end[j]]=i; d[end[j]]=d[i]+len[j]; q[ta++]=end[j]; } } if(ta==1) return re; in.ch(g,0); for(j=head[g];j;j=next[j]) if(in[end[j]]){ tmp=divide(end[j],len[j]); tmp->pa=re; re->son.insert(tmp); } return re; } inline void rebuild(Tnode*p){ Tnode*fa=p->pa; if(fa!=null) fa->son.erase(p); ++in.tclock; recover(p); Tnode*get=divide(p->up,fa==null?0:getdist(p->up,fa->g)); if(fa!=null){ get->pa=fa; fa->son.insert(get); } } inline void addnode(int x,int fa,int pdis){ dep[x]=dep[fa]+1; _dep[x]=_dep[fa]+pdis; pa[x][0]=fa; for(int j=1;j<=20;++j) pa[x][j]=pa[pa[x][j-1]][j-1]; make(x,fa,pdis); ins[x]=sNode(x); ins[x]->pa=ins[fa]; ins[fa]->son.insert(ins[x]); Tnode*last=ins[x],*node=null; for(Tnode*t=ins[fa];t!=null;t=t->pa){ int dis=getdist(t->g,x); Treap::insert(t->root,r[x]-dis); Treap::insert(last->_root,r[x]-dis); ans+=Treap::query(t->root,dis-r[x])-Treap::query(last->_root,dis-r[x]); if(last->siz/(double)(++t->siz)>0.75) node=t; last=t; } if(node!=null) rebuild(node); } } int main(){ //freopen("tt.in","r",stdin); int n; scanf("%*d%d",&n;); //scanf("%d",&n;); int pa,pdis; for(int i=1;i<=n;++i){ scanf("%d%d%d",&pa;,&pdis;,&r;[i]); pa^=(ans%1000000000); if(i==1){ dep[1]=1; _dep[1]=0; Dynamic_System::ins[1]=Dynamic_System::sNode(1); } else Dynamic_System::addnode(i,pa,pdis); //printf("%I64d\n",ans); printf("%lld\n",ans); } return 0; }
BZOJ3924
一样的动态树分治,对于每个分治结构维护所有点到根的加权距离以及所有点到父分治结构的根的加权距离,以及分治结构内部所有点的权值和.
计算答案时,每次向着答案更小的地方走就好了.
#include#include #include #include #include #include #include using namespace std; typedef long long ll; #define mp make_pair #define N 100010 int head[N],next[N<<1],end[N<<1],len[N<<1]; inline void addedge(int a,int b,int c){ static int q=1; end[q]=b; next[q]=head[a]; head[a]=q; len[q++]=c; } inline void make(int a,int b,int c){ addedge(a,b,c); addedge(b,a,c); } int seq[N<<1],in[N<<1],tclock,dep[N]; ll _dep[N]; int ans[N<<1][21],_log[N<<1]; inline int Min(int x,int y){ return dep[x]>dep[y]?y:x; } inline void dfs(int x,int fa){ seq[in[x]=++tclock]=x; for(int j=head[x];j;j=next[j]) if(end[j]!=fa){ dep[end[j]]=dep[x]+1; _dep[end[j]]=_dep[x]+len[j]; dfs(end[j],x); seq[++tclock]=x; } } inline void rmq_init(){ for(int i=1;i<=tclock;++i) ans[i][0]=seq[i]; for(int j=1;j<=20;++j) for(int i=1;i+(1< <=tclock;++i) ans[i][j]=Min(ans[i][j-1],ans[i+(1<<(j-1))][j-1]); for(int i=2;i<=tclock;++i) _log[i]=_log[i>>1]+1; } inline int lca(int x,int y){ x=in[x],y=in[y]; if(x>y) swap(x,y); int d=_log[y-x+1]; return Min(ans[x][d],ans[y-(1< son; }mem[N],*P=mem,Tnull,*null=&Tnull;,*ins[N]; inline Node*newnode(){ P->pa=null; return P++; } bool vis[N]; inline void maxi(int&x;,int y){ if(x up=x; fr=ta=pa[x]=0; q[ta++]=x; while(fr!=ta){ i=q[fr++]; for(j=head[i];j;j=next[j]) if(end[j]!=pa[i]&&!vis[end[j]]) pa[q[ta++]=end[j]]=i; } int g,Min_siz=0x3f3f3f3f; for(i=0;i =0;--i){ maxi(ms[q[i]],ta-siz[q[i]]); if(ms[q[i]] g=g)]=re; vis[g]=1; for(j=head[g];j;j=next[j]) if(!vis[end[j]]){ tmp=divide(end[j]); tmp->pa=re; re->son.push_back(tmp); } return re; } inline void up(int x,int y){ ins[x]->siz+=y; Node*last=ins[x]; for(Node*t=ins[x]->pa;t!=null;last=t,t=t->pa){ t->siz+=y; t->sum+=(ll)dist(t->g,x)*y; last->_sum+=(ll)dist(t->g,x)*y; } } inline ll getans(int x){ ll ans=ins[x]->sum; Node*last=ins[x]; for(Node*t=ins[x]->pa;t!=null;last=t,t=t->pa) ans+=t->sum-last->_sum+(ll)dist(t->g,x)*(t->siz-last->siz); return ans; } inline ll solve(Node*root){ ll res=getans(root->g); for(int j=0;j son.size();++j) if(getans(root->son[j]->up) son[j]); return res; } int main(){ //freopen("tt.in","r",stdin); int n,m; scanf("%d%d",&n;,&m;); int i,a,b,c; for(i=1;i
WJMZBMR模拟赛的某题
#include#include #include #include #include #include #include using namespace std; typedef long long ll; #define pb push_back #define inf 0x3f3f3f3f #define N 150010 int head[N],next[N<<1],end[N<<1],len[N<<1]; inline void addedge(int a,int b,int c){ static int q=1; end[q]=b; next[q]=head[a]; head[a]=q; len[q++]=c; } inline void make(int a,int b,int c){ addedge(a,b,c); addedge(b,a,c); } int seq[N<<1],in[N],tclock,dep[N],_dep[N]; int ans[N<<1][21],_log[N<<1]; inline int Min(int x,int y){ return dep[x] <=tclock;++i) _log[i]=_log[i>>1]+1; for(int i=1;i<=tclock;++i) ans[i][0]=seq[i]; for(int j=1;j<=20;++j) for(int i=1;i+(1< <=tclock;++i) ans[i][j]=Min(ans[i][j-1],ans[i+(1<<(j-1))][j-1]); } inline int lca(int x,int y){ x=in[x],y=in[y]; if(x>y) swap(x,y); int d=_log[y-x+1]; return Min(ans[x][d],ans[y-(1< <<1); } struct Node{ Node*pa; vector sum; vector _sum; vector tim; vector _tim; vector siz; vector __tim; int up,g; inline ll qsum(int _time){ int d=upper_bound(tim.begin(),tim.end(),_time)-tim.begin()-1; return sum[d]; } inline ll q_sum(int _time){ int d=upper_bound(_tim.begin(),_tim.end(),_time)-_tim.begin()-1; return _sum[d]; } inline ll qsiz(int _time){ int d=upper_bound(__tim.begin(),__tim.end(),_time)-__tim.begin()-1; return siz[d]; } }mem[N],*P=mem,Tnull,*null=&Tnull;,*ins[N]; inline Node*newnode(){ P->pa=null; return P++; } bool vis[N]; inline void maxi(int&x;,int y){ if(x up=x; fr=ta=pa[x]=0; q[ta++]=x; while(fr!=ta){ i=q[fr++]; for(j=head[i];j;j=next[j]) if(end[j]!=pa[i]&&!vis[end[j]]) pa[q[ta++]=end[j]]=i; } int g,Min_siz=0x3f3f3f3f; for(i=0;i =0;--i){ maxi(ms[q[i]],ta-siz[q[i]]); if(ms[q[i]] g=g]=re; vis[g]=1; for(j=head[g];j;j=next[j]) if(!vis[end[j]]) (divide(end[j]))->pa=re; re->tim.pb(0); re->sum.pb(0ll); re->_tim.pb(0); re->_sum.pb(0ll); re->__tim.pb(0); re->siz.pb(0); return re; } int a[N],w[N],sav[N]; int qu[N]; inline bool cmp(const int&x;,const int&y;){ return a[x]tim.pb(_time); ins[x]->sum.pb(ins[x]->sum.back()); ins[x]->__tim.pb(_time); ins[x]->siz.pb(ins[x]->siz.back()+1); Node*last=ins[x]; for(Node*t=ins[x]->pa;t!=null;last=t,t=t->pa){ int _dis=getdist(t->g,x); last->_tim.pb(_time); last->_sum.pb(last->_sum.back()+_dis); t->tim.pb(_time); t->sum.pb(t->sum.back()+_dis); t->__tim.pb(_time); t->siz.pb(t->siz.back()+1); } } inline ll query(int x,int _tim){ ll ans=ins[x]->qsum(_tim); Node*last=ins[x]; for(Node*t=ins[x]->pa;t!=null;last=t,t=t->pa) ans+=t->qsum(_tim)-last->q_sum(_tim)+(ll)(t->qsiz(_tim)-last->qsiz(_tim))*getdist(x,t->g); return ans; } inline int getc(){ static const int L=1<<15; static char buf[L],*S=buf,*T=buf; if(S==T){ T=(S=buf)+fread(buf,1,L,stdin); if(S==T) return EOF; } return*S++; } inline int getint(){ int c; while(!isdigit(c=getc())); int x=c-'0'; while(isdigit(c=getc())) x=(x<<1)+(x<<3)+c-'0'; return x; } int main(){ //freopen("tt.in","r",stdin); int n,Q,A; cin>>n>>Q>>A; int i,j; for(i=1;i<=n;++i) a[i]=getint(),w[i]=a[i]; sort(w+1,w+n+1); int id=0; for(i=1;i<=n;){ for(j=i;j!=n&&w;[j]==w[j+1];++j); sav[++id]=w[i]; i=j+1; } sav[id+1]=inf; for(i=1;i<=n;++i){ qu[i]=i; a[i]=lower_bound(sav+1,sav+id+1,a[i])-sav; } sort(qu+1,qu+n+1,cmp); int x,y,z; for(i=1;i <=n;++i) up(qu[i],a[qu[i]]); for(i=1;i<=n;++i){ ins[i]->tim.pb(inf); ins[i]->_tim.pb(inf); ins[i]->__tim.pb(inf); } ll ans=0; int u,l,r; while(Q--){ u=getint(); l=getint(); r=getint(); l=(ans+l)%A,r=(ans+r)%A; if(l>r) swap(l,r); --l; ans=0; if(l>=sav[1]) ans-=query(u,upper_bound(sav+1,sav+id+2,l)-sav-1); if(r>=sav[1]) ans+=query(u,upper_bound(sav+1,sav+id+2,r)-sav-1); //printf("%I64d\n",ans); printf("%lld\n",ans); } return 0; }
BZOJ1511
首先KMP,然后令$ans_i$表示前缀$i$的答案,然后依照我的代码分类讨论...就没了.
#include#include #include #include #include using namespace std; char s[1000010]; int next[1000010],ans[1000010]; int main(){ int n; scanf("%d",&n;); int i,j=0; scanf("%s",s+1); long long res=0; for(i=2;i<=n;++i){ for(;j&&s;[j+1]!=s[i];j=next[j]); if(s[j+1]==s[i]) ++j; next[i]=j; if(next[i]){ if(i%(i-next[i])==0) ans[i]=next[i]+ans[i-next[i]]; else ans[i]=i-i%(i-next[i])+ans[i%(i-next[i])]; } } for(i=1;i<=n;++i) res+=ans[i]; cout< <
BZOJ2850
基本全是KDTree,我们考虑一种复杂度稳定的算法吧...
我们将点分块,分成$\sqrt{n}$块,每块$\sqrt{n}$个点,那么每个块都有$O(n)$个斜率,对于每个块,我们把所有的询问离线进去跟斜率一起排序,维护一个点的序列使得点到当前向量的有向距离是有序的,然后斜率每一次改变相当于只是交换了对应两个点在序列中的位置.
我们用一个树状数组维护一下就行了,询问的时候直接二分.
于是这样的复杂度是$O(\sqrt{n}\times((n+m)logn))$.
可是细节太多...
我决定写KDTree辣!
BZOJ2028
set随便玩...
#include#include #include #include #include #include using namespace std; typedef pair pii; set be,en; #define mp make_pair #define N 200010 char s[10]; int _be[N],_en[N]; int main(){ int n; scanf("%d",&n;); int cnt=0,now=0,num,lab; set ::iterator it,next; while(n--){ scanf("%s",s); if(s[0]=='A'){ ++cnt; num=0; ++now; scanf("%d%d",&_be[cnt],&_en[cnt]); it=en.lower_bound(mp(_be[cnt],0)); while(1){ if(it==en.end()||_be[(*it).second]>_en[cnt]) break; --now; ++num; lab=(*it).second; next=it,++next; be.erase(be.find(mp(_be[lab],lab))); en.erase(en.find(mp(_en[lab],lab))); it=next; } be.insert(mp(_be[cnt],cnt)); en.insert(mp(_en[cnt],cnt)); printf("%d\n",num); } else printf("%d\n",now); } return 0; }
2333