6
11
2015
0

CH Round #51 - Shinrein祭 #1

这是去年暑假的比赛。当时只会两个暴力,总分60

我们按题目顺序来看这三道题

A.Phorni  

这其实是个后缀平衡树的裸题。

我们用后缀平衡树来维护每个后缀的$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;
}

B.Arietta

很容易想到网络流模型。

然后我们可以利用线段树优化网络流连边。

所以就是每个子树维护一棵权值线段树,然后连边直接按照线段树查找的方式连即可。

而父亲的线段树直接$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;
}

C.Falsita  

我们稍作思考可以得出

$$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;
}

 

 

Category: contest hunter | Tags: | Read Count: 713

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com