聯賽模擬測試10 C. 射手座之日
題目描述
分析
方法一（線段樹）
線段樹維護的是以當前節點為左端點的區間的貢獻
而區間的右端點則會從 \(1\) 到 \(n\) 逐漸右移
當我們把右端點從 \(i-1\) 的位置擴展到 \(i\) 的位置時
如果原先區間的最近公共祖先到根節點的路徑中經過 \(a[i-1]\) 和 \(a[i]\) 的最近公共祖先
那麼我們直接把這些區間的價值累加到 \(a[i-1]\) 和 \(a[i]\) 的最近公共祖先上
同時將其子樹清空，還要把 \(a[i]\) 位置上的貢獻加一
每次移完右端點後都要統計一下答案
程式碼
#include<cstdio>
#include<cstring>
#include<iostream>
inline int read(){
int x=0,fh=1;
char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e6+5;
int n,head[maxn],tot=1,a[maxn],x[maxn];
struct asd{
int to,next;
}b[maxn];
void ad(int aa,int bb){
b[tot].to=bb;
b[tot].next=head[aa];
head[aa]=tot++;
}
int siz[maxn],son[maxn],f[maxn],dep[maxn];
void dfs1(int now,int fa){
f[now]=fa;
siz[now]=1;
dep[now]=dep[fa]+1;
for(int i=head[now];i!=-1;i=b[i].next){
int u=b[i].to;
if(u==fa) continue;
dfs1(u,now);
siz[now]+=siz[u];
if(son[now] || siz[son[now]]<siz[u]){
son[now]=u;
}
}
}
int dfn[maxn],tp[maxn],dfnc,rk[maxn];
void dfs2(int now,int top){
tp[now]=top;
dfn[now]=++dfnc;
rk[dfnc]=now;
if(son[now]) dfs2(son[now],top);
for(int i=head[now];i!=-1;i=b[i].next){
int u=b[i].to;
if(u==f[now] || u==son[now]) continue;
dfs2(u,u);
}
}
int get_LCA(int u,int v){
while(tp[u]!=tp[v]){
if(dep[tp[u]]<dep[tp[v]]) std::swap(u,v);
u=f[tp[u]];
}
if(dep[u]<dep[v]) std::swap(u,v);
return v;
}
struct trr{
int l,r,tag;
long long cnt,sum;
}tr[maxn];
void push_up(int da){
tr[da].cnt=tr[da<<1].cnt+tr[da<<1|1].cnt;
tr[da].sum=tr[da<<1].sum+tr[da<<1|1].sum;
}
void push_down(int da){
if(tr[da].tag==-1){
tr[da<<1].tag=tr[da<<1|1].tag=-1;
tr[da<<1].cnt=tr[da<<1|1].cnt=0;
tr[da<<1].sum=tr[da<<1|1].sum=0;
tr[da].tag=0;
}
}
void build(int da,int l,int r){
tr[da].l=l,tr[da].r=r;
if(tr[da].l==tr[da].r){
return;
}
int mids=(tr[da].l+tr[da].r)>>1;
build(da<<1,l,mids);
build(da<<1|1,mids+1,r);
}
void xg(int da,int wz,long long val){
if(tr[da].l==tr[da].r){
tr[da].cnt+=val;
tr[da].sum=tr[da].cnt*x[rk[wz]];
return;
}
push_down(da);
int mids=(tr[da].l+tr[da].r)>>1;
if(wz<=mids) xg(da<<1,wz,val);
else xg(da<<1|1,wz,val);
push_up(da);
}
long long cx(int da,int l,int r){
if(tr[da].l>=l && tr[da].r<=r){
long long x=tr[da].cnt;
tr[da].cnt=0;
tr[da].sum=0;
tr[da].tag=-1;
return x;
}
push_down(da);
int mids=(tr[da].l+tr[da].r)>>1;
long long ans=0;
if(l<=mids) ans+=cx(da<<1,l,r);
if(r>mids) ans+=cx(da<<1|1,l,r);
push_up(da);
return ans;
}
int main(){
freopen("sagittarius.in","r",stdin);
freopen("sagittarius.out","w",stdout);
memset(head,-1,sizeof(head));
n=read();
int aa;
for(int i=2;i<=n;i++){
aa=read();
ad(aa,i);
ad(i,aa);
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int i=1;i<=n;i++){
x[i]=read();
}
build(1,1,n);
long long ans=0;
for(int i=1;i<=n;i++){
if(i>1){
int now=get_LCA(a[i],a[i-1]);
long long cs=cx(1,dfn[now],dfn[now]+siz[now]-1);
xg(1,dfn[now],cs);
}
xg(1,dfn[a[i]],1);
ans+=tr[1].sum;
}
printf("%lld\n",ans);
return 0;
}
方法二（樹上啟發式合併）
這一道題有 \(20\%\) 的部分排列是按照 \(dfn\) 序生成的
而這樣的序列對於任意一個節點來說，它的子節點的編號都是連續的
這樣的話貢獻在這棵子樹內的區間就為 \((siz+1) \times siz/2\)
其中 \(siz\) 為子樹大小
這就啟示我們可以維護子樹內連續區間段的長度
這樣的話子樹的值就可以直接累加到父親節點上
因此我們可以使用樹上啟發式合併
連續區間段的維護則要用到一個性質
我們設 \(rk[a[i]]=i\)，那麼如果有一個連續區間短
那麼很顯然，它們的 \(rank\) 值是連續的
程式碼
#include<cstdio>
#include<cstring>
#define rg register
inline int read(){
rg int x=0,fh=1;
char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e6+5;
int h[maxn],tot=1;
struct asd{
int to,nxt;
}b[maxn];
int a[maxn],x[maxn],n;
void ad(int aa,int bb){
b[tot].to=bb;
b[tot].nxt=h[aa];
h[aa]=tot++;
}
int son[maxn],siz[maxn],dep[maxn],f[maxn];
void dfs1(int now,int fa){
siz[now]=1;
f[now]=fa;
dep[now]=dep[fa]+1;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==fa) continue;
dfs1(u,now);
siz[now]+=siz[u];
if(son[now]==0 || siz[u]>siz[son[now]]){
son[now]=u;
}
}
}
long long nans[maxn],ans,mans,tmp;
int orz,len[maxn],rk[maxn];
long long js(int now){
int len1=len[rk[now]-1],len2=len[rk[now]+1];
int len3=len1+len2+1;
len[rk[now]-len1]=len3;
len[rk[now]+len2]=len3;
return 1LL*(len3+1)*len3/2-1LL*(len1+1)*len1/2-1LL*(len2+1)*len2/2;
}
void xg(int now,int op){
if(op==-1) len[rk[now]]=0;
else {
mans+=js(now);
}
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==orz || u==f[now]) continue;
xg(u,op);
}
}
void dfs2(int now,int op){
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==f[now] || u==son[now]) continue;
dfs2(u,0);
}
if(son[now]){
dfs2(son[now],1);
orz=son[now];
}
xg(now,1);
orz=0;
tmp=mans;
nans[now]=mans;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==f[now]) continue;
tmp-=nans[u];
}
ans+=1LL*tmp*x[now];
if(op==0){
xg(now,-1);
mans=0;
}
}
int main(){
freopen("sagittarius.in","r",stdin);
freopen("sagittarius.out","w",stdout);
memset(h,-1,sizeof(h));
n=read();
rg int aa;
for(rg int i=2;i<=n;i++){
aa=read();
ad(aa,i);
ad(i,aa);
}
for(rg int i=1;i<=n;i++){
a[i]=read();
rk[a[i]]=i;
}
for(rg int i=1;i<=n;i++){
x[i]=read();
}
dfs1(1,0);
dfs2(1,0);
printf("%lld\n",ans);
return 0;
}
兩種方法相比，樹上啟發式合併的程式碼更短，常數也更小
