2020-2021:teams:legal_string:jxm2001:contest:cf_global_13
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:contest:cf_global_13 [2021/03/01 19:34] jxm2001 |
2020-2021:teams:legal_string:jxm2001:contest:cf_global_13 [2021/03/01 21:54] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 78: | 行 78: | ||
| ===== G. Switch and Flip ===== | ===== G. Switch and Flip ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| 给定 $n(n\ge 3)$ 枚硬币，初始时 $i$ 号硬币位于位置 $a_i$ 且正面朝上。每次操作可以交换两枚硬币位置同时将两枚硬币翻面。 | 给定 $n(n\ge 3)$ 枚硬币，初始时 $i$ 号硬币位于位置 $a_i$ 且正面朝上。每次操作可以交换两枚硬币位置同时将两枚硬币翻面。 | ||
| 行 155: | 行 157: | ||
| _for(i,0,ans.size()) | _for(i,0,ans.size()) | ||
| printf("%d %d\n",ans[i].first,ans[i].second); | printf("%d %d\n",ans[i].first,ans[i].second); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== H. Yuezheng Ling and Dynamic Tree ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定 $a_2\sim a_n$ 表示结点 $i$ 的父结点，其中 $a_i\lt i$，接下来两种操作： | ||
| + | |||
| + | - $a_i\to \max(a_i-x,1),i\in [l,r]$ | ||
| + | - 查询 $u,v$ 的 $\text{LCA}$ | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 考虑分块，块大小为 $O(\sqrt n)$。对结点 $i$，用 $p_i$ 维护 $i$ 在同一个块中的最远祖先结点。 | ||
| + | |||
| + | 于是，对于查询操作，可以类似树剖查询做到 $O(\sqrt n)$。 | ||
| + | |||
| + | 对于修改操作，易知 $a_i$ 最多减小 $O(\sqrt n)$ 次后 $p_i$ 固定，因为此时必有 $a_i$ 和 $i$ 不在同一个块，于是 $p_i=i$。 | ||
| + | |||
| + | 当一个块满足所有 $p_i=i$ 时对整块修改操作只需要用懒标记维护 $a_i$ 即可。 | ||
| + | |||
| + | 每个块最多进行 $O(\sqrt n)$ 次整块修改操作，每次整块修改操作复杂度 $O(\sqrt n)$，共 $O(\sqrt n)$ 个块，于是整块修改操作的复杂度为 $O(n\sqrt n)$。 | ||
| + | |||
| + | 对于一个询问，最多有两个部分块修改操作，暴力维护即可，时间复杂度 $O(q\sqrt n)$。 | ||
| + | |||
| + | 总时间复杂度 $O\left((n+q)\sqrt n\right)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e5+5,MAXB=sqrt(MAXN)+5; | ||
| + | int a[MAXN],p[MAXN],blk_id[MAXN],blk_sz; | ||
| + | struct Block{ | ||
| + | int L,R,lazy,lazy_en; | ||
| + | void update_p(){ | ||
| + | lazy_en=true; | ||
| + | _rep(i,L,R){ | ||
| + | if(blk_id[i]==blk_id[a[i]]){ | ||
| + | lazy_en=false; | ||
| + | p[i]=p[a[i]]; | ||
| + | } | ||
| + | else | ||
| + | p[i]=i; | ||
| + | } | ||
| + | } | ||
| + | void update_a(int l,int r,int x){ | ||
| + | _rep(i,l,r) | ||
| + | a[i]=(i==1)?0:max(a[i]-x,1); | ||
| + | update_p(); | ||
| + | } | ||
| + | void update_a(int x){ | ||
| + | if(lazy_en)lazy+=x; | ||
| + | else | ||
| + | update_a(L,R,x); | ||
| + | } | ||
| + | }blk[MAXB]; | ||
| + | void update(int l,int r,int x){ | ||
| + | int pos1=blk_id[l],pos2=blk_id[r]; | ||
| + | if(pos1==pos2) | ||
| + | blk[pos1].update_a(l,r,x); | ||
| + | else{ | ||
| + | blk[pos1].update_a(l,blk[pos1].R,x); | ||
| + | _for(i,pos1+1,pos2) | ||
| + | blk[i].update_a(x); | ||
| + | blk[pos2].update_a(blk[pos2].L,r,x); | ||
| + | } | ||
| + | } | ||
| + | int A(int pos){ | ||
| + | return pos==1?0:max(a[pos]-blk[blk_id[pos]].lazy,1); | ||
| + | } | ||
| + | int query(int u,int v){ | ||
| + | while(p[u]!=p[v]){ | ||
| + | if(A(p[u])<A(p[v]))swap(u,v); | ||
| + | u=A(p[u]); | ||
| + | } | ||
| + | while(u!=v){ | ||
| + | if(u<v)swap(u,v); | ||
| + | u=A(u); | ||
| + | } | ||
| + | return u; | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),q=read_int(); | ||
| + | _rep(i,2,n)a[i]=read_int(); | ||
| + | blk_sz=sqrt(n)+1; | ||
| + | for(int l=1,r=0,blk_cnt=1;r!=n;l=r+1,blk_cnt++){ | ||
| + | r=min(l+blk_sz-1,n); | ||
| + | blk[blk_cnt].L=l; | ||
| + | blk[blk_cnt].R=r; | ||
| + | _rep(i,l,r) | ||
| + | blk_id[i]=blk_cnt; | ||
| + | blk[blk_cnt].update_p(); | ||
| + | } | ||
| + | while(q--){ | ||
| + | int t=read_int(); | ||
| + | if(t==1){ | ||
| + | int l=read_int(),r=read_int(),x=read_int(); | ||
| + | update(l,r,x); | ||
| + | } | ||
| + | else{ | ||
| + | int u=read_int(),v=read_int(); | ||
| + | enter(query(u,v)); | ||
| + | } | ||
| + | } | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/contest/cf_global_13.1614598496.txt.gz · 最后更改: 2021/03/01 19:34 由 jxm2001
