听说下雨天，分块和莫队更配哦~
恩。。。先跪PoPoQQQ
bzoj3585 mex
题目大意: 询问区间mex值
这题有用线段树的O(nlogn)做法，以前发过了，所以这里不做讨论
既然是区间询问且支持离线的数据结构题，我们很容易想到用莫队算法。
那么问题就在于区间之间如何转移。
想法1: 用平衡树维护插入和删除，询问时在平衡树上二分。
这样做每次插入、删除和询问都是O(logn)的
由于莫队算法需要进行O(q*sqrt(n))次插入或删除，则总的复杂度会达到O(q*sqrt(n)*logn).
这个做法的瓶颈在于插入和删除时的花费太大。
想法2: 将权值分块，维护每种权值出现的次数和每块有多少种权值出现。
这样可以做到每次O(1)的插入和删除，插入和删除的总
询问时先暴力找到第一个存在未存在的数的块，再在这个块内暴力，复杂度O(sqrt(n))。
虽然询问的复杂度高于上一种做法，但是实际上询问只会有q次，总的复杂度依然是O(n*sqrt(n)).
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define g() getchar()
template<class Q>void Scan(Q&x){
char c;int f=1;
while(c=g(),c<48||c>57)if(c=='-')f=-1;
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
x*=f;
}
#define rep(i,a,b) for(int i=a;i<b;++i)
const int MAXN=2e5+5;
int n,m,B,tot;
int a[MAXN],pos[MAXN];
struct qy{
int l,r,id;
}q[MAXN];
inline bool cmp(const qy&a,const qy&b){
if(pos[a.l]!=pos[b.l])return a.l<b.l;
return pos[a.l]&1?a.r<b.r:a.r>b.r;
}
inline void Init(){
Scan(n),Scan(m);
B=sqrt(n)+1;
tot=n/B+1;
rep(i,1,n+1){
Scan(a[i]);
if(a[i]>n)a[i]=n;
}
rep(i,0,n+1)pos[i]=i/B+1;
rep(i,1,m+1){
Scan(q[i].l),Scan(q[i].r);
q[i].id=i;
}
}
int cnt[MAXN],cnt1[MAXN];
inline void Add(int x){
if(++cnt[x]==1)++cnt1[pos[x]];
}
inline void Del(int x){
if(!(--cnt[x]))--cnt1[pos[x]];
}
inline int query(){
int i=1;
for(;i<=tot&&cnt1[i]==B;++i);
for(i=(i-1)*B;cnt[i]&&i<n;++i);
return i;
}
int ans[MAXN];
inline void Solve(){
sort(q+1,q+1+m,cmp);
int l=q[1].l,r=q[1].r;
rep(i,l,r+1)Add(a[i]);
ans[q[1].id]=query();
rep(i,2,m+1){
int ll=q[i].l,rr=q[i].r;
for(;r<rr;Add(a[++r]));
for(;r>rr;Del(a[r--]));
for(;l>ll;Add(a[--l]));
for(;l<ll;Del(a[l++]));
ans[q[i].id]=query();
}
rep(i,1,m+1)
printf("%d\n",ans[i]);
}
int main(){
Init(); Solve(); return 0;
}
bzoj4129 Haruna's Breakfast
题目大意: 询问树上两点间路径的mex值，支持单点修改
这题是上一题的加强版，从线形推广到树形。
这题如果从线段树入手会十分困难(其实是博主太弱了不会这样做，有会这种做法的请联系我)
考虑到莫队算法是可以推广到树上的，我们直接用上一题的思路就好了。
由于带修改，对树分块时块的大小最好设为n2/3,对权值分块还是sqrt(n)就好。
简单说下树上路径的转移方法，为了方便，以下所说的路径均不含lca。
假设现在的路径是(x1,y1),需要转移到路径(x2,y2).
我们将路径(x1,x2),(y1,y2)取反，就得到了(x2,y2).
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define g() getchar()
template<class Q>void Scan(Q&x){
char c; while(c=g(),c<48||c>57);
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}
#define rep(i,a,b) for(int i=a;i<b;++i)
const int MAXN=50005;
int B1,Bn,a[MAXN],pos[MAXN];
struct edge{
int t,n;
edge(int t=0,int n=0):t(t),n(n){}
}e[MAXN<<1];
int head[MAXN],tot;
inline void AddEdge(int s,int t){
e[++tot]=edge(t,head[s]),head[s]=tot;
e[++tot]=edge(s,head[t]),head[t]=tot;
}
int n,m,B2,bel[MAXN],siz[MAXN];
struct qy{
int x,y,z,id;
qy(int x=0,int y=0,int z=0,int id=0):
x(x),y(y),z(z),id(id){}
}q[MAXN];
inline bool cmp(const qy&a,const qy&b){
if(bel[a.x]!=bel[b.x])return bel[a.x]<bel[b.x];
if(bel[a.y]!=bel[b.y])
return bel[a.x]&1?bel[a.y]<bel[b.y]:bel[a.y]>bel[b.y];
return bel[a.y]&1?a.z<b.z:a.z>b.z;
}
struct tarjan{
int x,id,n;
tarjan(int x=0,int id=0,int n=0):x(x),id(id),n(n){}
}t[MAXN<<1];
int thd[MAXN],qtot;
inline void AddTarjan(int x,int y,int id){
t[++qtot]=tarjan(y,id,thd[x]),thd[x]=qtot;
t[++qtot]=tarjan(x,id,thd[y]),thd[y]=qtot;
}
bool col[MAXN];
int f[MAXN];
int find(int x){
return x==f[x]?x:f[x]=find(f[x]);
}
int p[MAXN],dep[MAXN],lca[MAXN];
void dfs(int x){
for(int i=head[x],y;i;i=e[i].n)
if((y=e[i].t)!=p[x]){
if(siz[bel[x]]<B2){
++siz[bel[y]=bel[x]];
}
p[y]=x;
dep[y]=dep[x]+1;
dfs(y);
}
col[x]=1;
for(int i=thd[x],y;i;i=t[i].n)
if(col[y=t[i].x])lca[t[i].id]=find(y);
f[x]=p[x];
}
bool on[MAXN];
int cnt[MAXN],cnt1[MAXN];
inline void Add(int x){
if(++cnt[x]==1)++cnt1[pos[x]];
}
inline void Del(int x){
if(--cnt[x]==0)--cnt1[pos[x]];
}
inline int query(){
int i=1;
for(;i<Bn&&cnt1[i]==B1;++i);
for(i=(i-1)*B1;i<n&&cnt[i];++i);
return i;
}
inline void Xor(int x){
on[x]^=1;
if(on[x])Add(a[x]);
else Del(a[x]);
}
struct modify{
int x,f,t;
modify(int x=0,int f=0,int t=0):
x(x),f(f),t(t){}
}mo[MAXN];
int mod_tot,qy_tot;
inline void change(int x,int y){
if(on[x])Del(a[x]);
a[x]=y;
if(on[x])Add(a[x]);
}
inline void Modify(int cur,int to){
for(;cur<to;++cur)change(mo[cur+1].x,mo[cur+1].t);
for(;cur>to;--cur)change(mo[cur].x,mo[cur].f);
}
inline void Rev(int x,int y){
if(dep[x]>dep[y])swap(x,y);
while(dep[y]>dep[x])Xor(y),y=p[y];
while(x!=y)Xor(x),Xor(y),x=p[x],y=p[y];
}
int ans[MAXN];
inline void Init(){
Scan(n),Scan(m);
B1=sqrt(n),Bn=n/B1+1;
B2=pow(n,2./3);
pos[0]=1;
rep(i,1,n+1){
pos[i]=i/B1+1;
Scan(a[i]);
if(a[i]>n)a[i]=n;
f[i]=bel[i]=i;
}
rep(i,1,n){
int x,y;
Scan(x),Scan(y);
AddEdge(x,y);
}
rep(i,1,m+1){
int t,x,y;
Scan(t),Scan(x),Scan(y);
if(t){
++qy_tot;
q[qy_tot]=qy(x,y,mod_tot,qy_tot);
AddTarjan(x,y,qy_tot);
}
else{
if(y>n)y=n;
mo[++mod_tot]=modify(x,a[x],y);
a[x]=y;
}
}
dfs(1);
rep(i,1,qy_tot+1){
if(bel[q[i].x]>bel[q[i].y])
swap(q[i].x,q[i].y);
}
}
inline void Solve(){
sort(q+1,q+1+qy_tot,cmp);
int x=q[1].x,y=q[1].y,z=q[1].z;
int Lca=lca[q[1].id];
Modify(mod_tot,z);
Rev(x,y);
Xor(Lca);
ans[q[1].id]=query();
Xor(Lca);
rep(i,2,qy_tot+1){
Modify(z,q[i].z),z=q[i].z;
Rev(x,q[i].x),x=q[i].x;
Rev(y,q[i].y),y=q[i].y;
Lca=lca[q[i].id];
Xor(Lca);
ans[q[i].id]=query();
Xor(Lca);
}
rep(i,1,qy_tot+1){
printf("%d\n",ans[i]);
}
}
int main(){
Init(); Solve(); return 0;
}
评论 (0)
