*3400 的毒瘤 H 题,特意写个题解纪念一下(
首先对于这种数据结构不太好直接维护的东东可以考虑分块。然鹅我除了分块其他啥也没想到
我们设一个阈值 \(B\),每 \(B\) 个元素分为一块。
我们知道两点之间的 LCA 的大体思想肯定是暴力跳祖先,直到两点重合为止。不过由于此题修改操作的特殊性,什么倍增、树剖都萎掉了。
于是我们考虑一个大致思路:整块暴力跳,散块直接找祖先。
具体来说,我们设 \(pre_i\) 为 \(i\) 的祖先中最大的满足 \(j\) 与 \(i\) 不在同一块中的 \(j\)。
假设我们已经维护好了 \(pre_i\),那么找两点 \(u,v\) 之间的 LCA 这样实现:
正确性显然,如果你对树剖比较熟应该会理解得深刻一些。这部分复杂度 \(qB+\dfrac{qn}{B}\)。
接下来考虑修改操作,对于边角块,直接暴力修改其 \(a_i\) 值,然后对整块进行重构即可,这样最多只会重构两块,故这部分复杂度为单次询问 \(\mathcal O(B)\)。
对于整块,直接维护比较困难,不过注意到一个性质,那就是进行 \(B\) 次操作之后每个点的 \(fa\) 值都不会属于这个块,也就是说如果某个块的修改次数 \(\geq B\),那么 \(pre_i=fa_i\),故我们维护一个 \(cnt_i\) 表示每个块总共被改了多少次,如果 \(cnt_i\leq B\) 还是暴力重构整个块,否则打一个 \(+x\) 的标记,然后查询某个点的 \(pre\) 值时就返回 \(\max(1,pre_i-tag_i)\),其中 \(tag_i\) 为 \(i\) 所在的块打的标记大小。这部分复杂度为 \(B·\dfrac{n}{B}·B=nB\)
根据均值不等式可知 \(B=\sqrt{n}\) 时最优,总复杂度 \(n\sqrt{n}+q\sqrt{n}\)。
还有一些细节需注意,具体见代码罢:
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
namespace fastio{
#define FILE_SIZE 1<<23
char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf;
inline char getc(){return p1==p2&&(p2=(p1=rbuf)+fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1++;}
inline void putc(char x){(*p3++=x);}
template<typename T> void read(T &x){
x=0;char c=getchar();T neg=0;
while(!isdigit(c)) neg|=!(c^'-'),c=getchar();
while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(neg) x=(~x)+1;
}
template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x%10^48);}
template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x+1;recursive_print(x);}
void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);}
}
const int MAXN=1e5;
const int SQRT=316;
int n,qu,fa[MAXN+5],pre[MAXN+5];
int blk_sz,blk,L[SQRT+5],R[SQRT+5],bel[MAXN+5];
int tag[SQRT+5],sum[SQRT+5];
void update(int x){
for(int i=L[x];i<=R[x];i++) fa[i]=max(1,fa[i]-tag[x]);
tag[x]=0;
for(int i=L[x];i<=R[x];i++){
if(fa[i]<L[x]) pre[i]=fa[i];
else pre[i]=pre[fa[i]];
}
}
int getpre(int x){return max(pre[x]-tag[bel[x]],1);}
int getfa(int x){return max(fa[x]-tag[bel[x]],1);}
void modify(int l,int r,int x){
if(bel[l]==bel[r]){
for(int i=l;i<=r;i++) fa[i]=max(1,fa[i]-x);
update(bel[l]);return;
}
for(int i=l;i<=R[bel[l]];i++) fa[i]=max(1,fa[i]-x);
for(int i=L[bel[r]];i<=r;i++) fa[i]=max(1,fa[i]-x);
update(bel[l]);update(bel[r]);
for(int i=bel[l]+1;i<=bel[r]-1;i++){
tag[i]=min(n,tag[i]+x);sum[i]++;
if(sum[i]<=R[i]-L[i]+1) update(i);
}
}
int getlca(int u,int v){
while(u!=v){
if(bel[u]<bel[v]) swap(u,v);
if(bel[u]>bel[v]) u=getpre(u);
else{
if(getpre(u)==getpre(v)){
while(u!=v){
if(u<v) swap(u,v);
u=getfa(u);
}
} else {
u=getpre(u);v=getpre(v);
}
}
} return u;
}
int main(){
scanf("%d%d",&n,&qu);blk_sz=(int)pow(n,0.5);blk=(n-1)/blk_sz+1;
for(int i=1;i<=blk;i++){
L[i]=(i-1)*blk_sz+1;R[i]=min(i*blk_sz,n);
for(int j=L[i];j<=R[i];j++) bel[j]=i;
}
for(int i=2;i<=n;i++) scanf("%d",&fa[i]);
for(int i=1;i<=blk;i++) update(i);
while(qu--){
int opt;scanf("%d",&opt);
if(opt==1){int l,r,x;scanf("%d%d%d",&l,&r,&x);modify(l,r,x);}
else{int u,v;scanf("%d%d",&u,&v);printf("%d\n",getlca(u,v));}
}
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章