首页 > 代码库 > bzoj4129 Haruna’s Breakfast

bzoj4129 Haruna’s Breakfast

2024-10-23 04:34:39   202人阅读

Description

Haruna每天都会给提督做早餐！ 这天她发现早饭的食材被调皮的 Shimakaze放到了一棵树上，每个结点都有一样食材，Shimakaze要考验一下她。

每个食材都有一个美味度，Shimakaze会进行两种操作：
1、修改某个结点的食材的美味度。
2、对于某条链，询问这条链的美味度集合中，最小的未出现的自然数是多少。即mex值。
请你帮帮Haruna吧。

Input

第一行包括两个整数n，m，代表树上的结点数(标号为1~n)和操作数。

第二行包括n个整数a1...an，代表每个结点的食材初始的美味度。
接下来n-1行，每行包括两个整数u，v，代表树上的一条边。
接下来m 行，每行包括三个整数
0 u x 代表将结点u的食材的美味度修改为 x。
1 u v 代表询问以u，v 为端点的链的mex值。

Output

对于每次询问，输出该链的mex值。

Sample Input

10 10
1 0 1 0 2 4 4 0 1 0
1 2
2 3
2 4
2 5
1 6
6 7
2 8
3 9
9 10
0 7 14
1 6 6
0 4 9
1 2 2
1 1 8
1 8 3
0 10 9
1 3 5
0 10 0
0 7 7

Sample Output

0
1
2
2
3

HINT

1<=n<=5*10^4

1<=m<=5*10^4
0<=ai<=10^9

 

正解：树上带修改莫队+分块。

我只是感觉自己可能会忘记套路然后就又做了一道题。。

这题莫队的思路还是比较显然的，问题主要是如何查询。

我们把权值按照根号$n$分块。很显然，$mex<=n$，所以我们只需要把$<=n$的数标记就行了。

查询时我们从小到大枚举每一个块，如果当前这个块没有满，那么再枚举块内的每一个元素，这样我们就能很方便地找到答案了。

 

  1 //It is made by wfj_2048~  2 #include <algorithm>  3 #include <iostream>  4 #include <complex>  5 #include <cstring>  6 #include <cstdlib>  7 #include <cstdio>  8 #include <vector>  9 #include <cmath> 10 #include <queue> 11 #include <stack> 12 #include <map> 13 #include <set> 14 #define inf (1<<30) 15 #define N (100010) 16 #define il inline 17 #define RG register 18 #define ll long long 19 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) 20  21 using namespace std; 22  23 struct upd{ int u,v,x; }q1[N]; 24 struct que{ int i,tim,u,v; }q2[N]; 25 struct edge{ int nt,to; }g[2*N]; 26  27 int head[N],top[N],fa[N],son[N],dep[N],dfn[N],sz[N],bl[N],st[N],vis[N],val[N],sum[N],la[N],a[N],ans[N],n,m,num,Q1,Q2,Tp,Lca,cnt,Bl,totb,block; 28  29 il int gi(){ 30     RG int x=0,q=1; RG char ch=getchar(); 31     while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar(); 32     if (ch==‘-‘) q=-1,ch=getchar(); 33     while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar(); 34     return q*x; 35 } 36  37 il void insert(RG int from,RG int to){ 38     g[++num]=(edge){head[from],to},head[from]=num; return; 39 } 40  41 il int cmp(const que &a,const que &b){ 42     if (bl[a.u]==bl[b.u] && bl[a.v]==bl[b.v]) return a.tim<b.tim; 43     if (bl[a.u]==bl[b.u]) return bl[a.v]<bl[b.v]; return bl[a.u]<bl[b.u]; 44 } 45  46 il void dfs1(RG int x,RG int p){ 47     dep[x]=dep[p]+1,fa[x]=p,sz[x]=1; RG int v; 48     for (RG int i=head[x];i;i=g[i].nt){ 49     v=g[i].to; if (v==p) continue; 50     dfs1(v,x),sz[x]+=sz[v]; 51     if (sz[son[x]]<=sz[v]) son[x]=v; 52     } 53     return; 54 } 55  56 il void dfs2(RG int x,RG int p,RG int anc){ 57     top[x]=anc,dfn[x]=++cnt; RG int tp=Tp,v; 58     if (son[x]) dfs2(son[x],x,anc); if (Tp-tp>block) ++totb; 59     while (Tp-tp>block) bl[st[Tp--]]=totb; 60     for (RG int i=head[x];i;i=g[i].nt){ 61     v=g[i].to; if (v==p || v==son[x]) continue; 62     tp=Tp,dfs2(v,x,v); if (Tp-tp>block) ++totb; 63     while (Tp-tp>block) bl[st[Tp--]]=totb; 64     } 65     st[++Tp]=x; return; 66 } 67  68 il int lca(RG int u,RG int v){ 69     while (top[u]!=top[v]){ 70     if (dep[top[u]]<dep[top[v]]) swap(u,v); u=fa[top[u]]; 71     } 72     return dep[u]<dep[v] ? u : v; 73 } 74  75 il void update(RG int x){ 76     if (!vis[x]){ 77     vis[x]=1; if (a[x]>n) return; 78     ++val[a[x]]; if (val[a[x]]==1) ++sum[a[x]/Bl]; 79     } else{ 80     vis[x]=0; if (a[x]>n) return; 81     --val[a[x]]; if (!val[a[x]]) --sum[a[x]/Bl]; 82     } 83     return; 84 } 85  86 il void modify(RG int x,RG int v){ 87     if (!vis[x]) a[x]=v; else update(x),a[x]=v,update(x); return; 88 } 89  90 il void change(RG int u,RG int v){ 91     while (u!=v){ 92     if (dep[u]>dep[v]) update(u),u=fa[u]; else update(v),v=fa[v]; 93     } 94     return; 95 } 96  97 il int query(){ 98     for (RG int i=0;;++i) 99     if (sum[i]!=Bl) for (RG int j=i*Bl;;++j) if (!val[j]) return j;100 }101 102 il void work(){103     n=gi(),m=gi(),block=pow(n,0.6),Bl=sqrt(n);104     for (RG int i=1;i<=n;++i) a[i]=gi(),la[i]=a[i];105     for (RG int i=1,u,v;i<n;++i) u=gi(),v=gi(),insert(u,v),insert(v,u);106     dfs1(1,0),dfs2(1,0,1),cnt=0; if (Tp) ++totb; while (Tp) bl[st[Tp--]]=totb;107     for (RG int i=1,op,u,v;i<=m;++i){108     op=gi(),u=gi(),v=gi();109     if (!op)  q1[++Q1]=(upd){u,v,la[u]},la[u]=v;110     else{ if (dfn[u]>dfn[v]) swap(u,v); q2[++Q2]=(que){Q2,Q1,u,v}; }111     }112     sort(q2+1,q2+Q2+1,cmp);113     while (cnt<q2[1].tim) ++cnt,modify(q1[cnt].u,q1[cnt].v);114     change(q2[1].u,q2[1].v),Lca=lca(q2[1].u,q2[1].v);115     update(Lca),ans[q2[1].i]=query(),update(Lca);116     for (RG int i=2;i<=Q2;++i){117     while (cnt<q2[i].tim) ++cnt,modify(q1[cnt].u,q1[cnt].v);118     while (cnt>q2[i].tim) modify(q1[cnt].u,q1[cnt].x),--cnt;119     change(q2[i-1].u,q2[i].u),change(q2[i-1].v,q2[i].v);120     Lca=lca(q2[i].u,q2[i].v),update(Lca),ans[q2[i].i]=query(),update(Lca);121     }122     for (RG int i=1;i<=Q2;++i) printf("%d\n",ans[i]); return;123 }124 125 int main(){126     File("mex");127     work();128     return 0;129 }

 

bzoj4129 Haruna’s Breakfast


联系
我们