这是去年暑假的比赛。当时只会两个暴力，总分60
我们按题目顺序来看这三道题
这其实是个后缀平衡树的裸题。
我们用后缀平衡树来维护每个后缀的$rank$，然后用线段树维护一下幻影们对应的后缀的字典序的最小值即可。
int n,m,rt,len,type,tot,h[maxn],a[maxn],b[maxn],ls[maxn],rs[maxn];
ll rk[maxn];
char s[maxn],ch[10];
struct seg{int mi;}t[4*maxn];
inline void rebuild(int k,ll l,ll r)
{
if(!k)return;
rk[k]=l+r;
rebuild(ls[k],l,mid);rebuild(rs[k],mid,r);
}
inline void rturn(int &k,ll l,ll r)
{
int t=ls[k];ls[k]=rs[t];rs[t]=k;k=t;rebuild(k,l,r);
}
inline void lturn(int &k,ll l,ll r)
{
int t=rs[k];rs[k]=ls[t];ls[t]=k;k=t;rebuild(k,l,r);
}
inline bool cmp(int x,int y){return a[x]<a[y]||(a[x]==a[y]&&rk[x-1]<rk[y-1]);}
inline void insert(int &k,ll l,ll r)
{
if(!k){k=tot;rk[k]=l+r;return;}
if(cmp(tot,k)){insert(ls[k],l,mid);if(h[ls[k]]>h[k])rturn(k,l,r);}
else {insert(rs[k],mid,r);if(h[rs[k]]>h[k])lturn(k,l,r);}
}
inline void insert(int x)
{
a[++tot]=x;h[tot]=rand()*rand();
insert(rt,1,(ll)1<<61);
}
inline void pushup(int k)
{
t[k].mi=rk[b[t[k<<1].mi]]<=rk[b[t[k<<1|1].mi]]?t[k<<1].mi:t[k<<1|1].mi;
}
inline void build(int k,int l,int r)
{
if(l==r){b[l]=read();t[k].mi=l;return;}
build(lch);build(rch);
pushup(k);
}
inline void change(int k,int l,int r,int x)
{
if(l==r)return;
if(x<=mid)change(lch,x);else change(rch,x);
pushup(k);
}
inline int query(int k,int l,int r,int x,int y)
{
if(l==x&&r==y)return t[k].mi;
if(y<=mid)return query(lch,x,y);
else if(x>mid)return query(rch,x,y);
else
{
int t1=query(lch,x,mid),t2=query(rch,mid+1,y);
return rk[b[t1]]<=rk[b[t2]]?t1:t2;
}
}
int main()
{
n=read();m=read();len=read();type=read();
scanf("%s",s);
for1(i,len)insert(s[len-i]-'a'+1);
build(1,1,n);int ans=0;
while(m--)
{
scanf("%s",ch);
if(!type)ans=0;
if(ch[0]=='I')insert((read()^ans)+1);
else if(ch[0]=='C'){int x=read(),y=read();b[x]=y;change(1,1,n,x);}
else {int x=read(),y=read();printf("%d\n",ans=query(1,1,n,x,y));}
}
return 0;
}
很容易想到网络流模型。
然后我们可以利用线段树优化网络流连边。
所以就是每个子树维护一棵权值线段树，然后连边直接按照线段树查找的方式连即可。
而父亲的线段树直接$merge$儿子的。
和$vfleaking$的$A+B problem$差不多。
int n,m,s,t,cnt,maxflow,tot=1,head[maxm],cur[maxm],h[maxm];
queue<int>q;
int rt[maxn],lc[maxm],rc[maxm];
struct edge{int go,next,v;}e[maxm];
vector<int> son[maxn];
inline void add(int x,int y,int v)
{
e[++tot]=(edge){y,head[x],v};head[x]=tot;
e[++tot]=(edge){x,head[y],0};head[y]=tot;
}
bool bfs()
{
for(int i=0;i<=cnt;i++)h[i]=-1;
q.push(s);h[s]=0;
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=head[x];i;i=e[i].next)
if(e[i].v&&h[e[i].go]==-1)
{
h[e[i].go]=h[x]+1;q.push(e[i].go);
}
}
return h[t]!=-1;
}
int dfs(int x,int f)
{
if(x==t) return f;
int tmp,used=0;
for(int i=cur[x];i;i=e[i].next)
if(e[i].v&&h[e[i].go]==h[x]+1)
{
tmp=dfs(e[i].go,min(e[i].v,f-used));
e[i].v-=tmp;if(e[i].v)cur[x]=i;
e[i^1].v+=tmp;used+=tmp;
if(used==f)return f;
}
if(!used) h[x]=-1;
return used;
}
void dinic()
{
maxflow=0;
while(bfs())
{
for (int i=0;i<=cnt;i++)cur[i]=head[i];maxflow+=dfs(s,inf);
}
}
inline void insert(int x)
{
int l,r;
for(l=1,r=n,++cnt;l<r;++cnt)
if(x<=mid)
{
add(cnt,lc[cnt]=cnt+1,inf);
r=mid;
}else
{
add(cnt,rc[cnt]=cnt+1,inf);
l=mid+1;
}
add(cnt,t,1);
}
inline int merge(int x,int y,int l,int r)
{
if(x*y==0)return x+y;
int k=++cnt;
if(l==r)add(k,x,inf),add(k,y,inf);
else
{
add(k,lc[k]=merge(lc[x],lc[y],l,mid),inf);
add(k,rc[k]=merge(rc[x],rc[y],mid+1,r),inf);
}
return k;
}
inline void dfs(int x)
{
if(!son[x].size())return;
for(int i=son[x].size()-1;~i;i--)
{
dfs(son[x][i]);
rt[x]=merge(rt[x],rt[son[x][i]],1,n);
}
}
inline void query(int k,int l,int r,int x,int y)
{
if(!k)return;
if(l==x&&r==y){add(cnt,k,inf);return;}
if(y<=mid)query(lc[k],l,mid,x,y);
else if(x>mid)query(rc[k],mid+1,r,x,y);
else query(lc[k],l,mid,x,mid),query(rc[k],mid+1,r,mid+1,y);
}
int main()
{
n=read();m=read();s=0;t=1;cnt=t;
for2(i,2,n)son[read()].push_back(i);
for1(i,n)rt[i]=cnt+1,insert(read());
dfs(1);
while(m--)
{
int l=read(),r=read(),x=read(),y=read();
add(s,++cnt,y);
query(rt[x],1,n,l,r);
}
dinic();
cout<<maxflow<<endl;
return 0;
}
我们稍作思考可以得出
$$ans[x]=\sum_{y是x的儿子}sum[y]*(size[x]-size[y])+w[x]*(size[x]-1)$$
其中$size[x]$表示$x$的子树大小，$sum[x]$表示x的子树权值和，$w[x]$表示x的权值。
首先注意到$sum[x]$和$w[x]$都是很容易用一棵线段树来维护的。所以我们在答案的表达式中去除这些很容易维护的量。
与此同时，我们发现只需要维护 $\sum_{y是x的儿子}size[y]*sum[y]$ 就可以再++--一些常数或者说只和$x$有关的东西就可以得出$ans$。
所以说一个点$x$的答案只与它的所有儿子$y$有关，但是我们并不能在询问的时候遍历儿子找$ans$，这样是肯定会$T$的。
所以我们考虑时刻维护$x$的$ans$。
这个如何维护呢？
我们考虑利用树链剖分来维护子树信息（这个十分重要）
先考虑单点修改。
当$w[k]+=delta$的时候，我们沿着$k$往上走到根，每个点的$ans$都加了$size[y]*delta$。
如果是在重链上的话，我们就整体打个标记$delta$表示这个点的$ans[x]+=sum[son[x]]*delta$。$son[x]$表示$x$的重儿子。
所以这部分也可以用一棵线段树来维护。
否则我们直接$O（1）$用轻儿子更新父亲即可。
这样最多往上跳$O（logn）$次，每次是$O（logn）$的。所以复杂度就是$O（log^2 n）$。
再考虑子树修改
如果对$k$执行了$k$的子树$+=delta$。那么$k$的父亲及往上实际上相当于单点修改了$w[k]+=size[k]*delta$。
那么我们对于上面这部分沿用上面的算法即可。
然后考虑$k$及$k$的子树。
我们发现每个节点所有权值都被$+=delta$。所以相应的$sum[y]*size[y]$也$+=size[y]*delta*size[y]$。
我们对这些增量求和发现就是 $\sum_{y是x的儿子}size[y]^2*delta$
这样的话，我们可以直接事先求出$\sum_{y是x的儿子}size[y]^2$ 那么就只需要维护$delta$就可以了。
同理一棵线段树搞定。
所以这题的关键之处在于想到时刻维护每个点的$ans$并且用树链剖分来维护子树信息。
struct segment_tree
{
struct seg{ll tag,sum;}t[4*maxn];
inline void pushup(int k)
{
t[k].sum=t[k<<1].sum+t[k<<1|1].sum;
}
inline void update(int k,int l,int r,int ll z)
{
t[k].sum+=z*(r-l+1);
t[k].tag+=z;
}
inline void pushdown(int k,int l,int r)
{
if(!t[k].tag)return;
update(k<<1,l,mid,t[k].tag);
update(k<<1|1,mid+1,r,t[k].tag);
t[k].tag=0;
}
inline void add(int k,int l,int r,int x,int y,ll z)
{
if(l==x&&r==y){update(k,l,r,z);return;}
pushdown(k,l,r);
if(y<=mid)add(lch,x,y,z);
else if(x>mid)add(rch,x,y,z);
else add(lch,x,mid,z),add(rch,mid+1,y,z);
pushup(k);
}
inline ll query(int k,int l,int r,int x,int y)
{
if(l==x&&r==y)return t[k].sum;
pushdown(k,l,r);
if(y<=mid)return query(lch,x,y);
else if(x>mid)return query(rch,x,y);
else return query(lch,x,mid)+query(rch,mid+1,y);
}
}T,G,Q;
int n,m,cnt,tot,head[maxn],son[maxn],fa[maxn],l[maxn],r[maxn],top[maxn];
ll size[maxn],sizesize[maxn],ret[maxn],sum[maxn],w[maxn],s[maxn];
struct edge{int go,next;}e[maxn];
inline void add(int x,int y)
{
e[++tot]=(edge){y,head[x]};head[x]=tot;
}
inline void dfs(int x)
{
size[x]=1;sum[x]=w[x];
for4(i,x)
{
dfs(y);
sum[x]+=sum[y];
size[x]+=size[y];
sizesize[x]+=size[y]*size[y];
ret[x]+=sum[y]*size[y];
if(size[y]>size[son[x]])son[x]=y;
}
}
inline void dfs2(int x,int chain)
{
l[x]=++cnt;top[x]=chain;
if(son[x])dfs2(son[x],chain);
for4(i,x)if(y!=son[x])dfs2(y,y);
s[x]=size[x]-1;
for4(i,x)s[x]+=size[y]*(size[x]-size[y]);
r[x]=cnt;
}
inline void update(int x,ll z)
{
while(x)
{
int y=top[x];
if(l[y]<=l[x]-1)G.add(1,1,n,l[y],l[x]-1,z);
x=fa[top[x]];
ret[x]+=size[y]*z;
}
}
char ch[2];
int main()
{
n=read();m=read();
for2(i,2,n)add(fa[i]=read(),i);
for1(i,n)w[i]=read();
dfs(1);
dfs2(1,1);
while(m--)
{
scanf("%s",ch);
if(ch[0]=='S')
{
int x=read(),y=read();
T.add(1,1,n,l[x],l[x],y);
update(x,y);
}
else if(ch[0]=='M')
{
int x=read(),y=read();
T.add(1,1,n,l[x],r[x],y);
update(x,size[x]*y);
Q.add(1,1,n,l[x],r[x],y);
}else
{
int x=read();ll ans=0;
ans=size[x]*(T.query(1,1,n,l[x],r[x])+sum[x])-(T.query(1,1,n,l[x],l[x])+w[x]);
ans-=ret[x]+size[son[x]]*G.query(1,1,n,l[x],l[x]);
ans-=sizesize[x]*Q.query(1,1,n,l[x],l[x]);
printf("%.6f\n",(double)ans/s[x]*2.0);
}
}
return 0;
}
评论 (0)
