[JZOJ6089]【CodeChef 2014 April Challenge】Final Battle of Chef【数据结构】【整体二分】

Description

$n,q,V\leq 100000,w_i\leq 10^9$

Solution

又是一道大数据结构

由于有一个下取整，这就导致了不同时间的修改值是不能简单的直接加在一起的。

容易发现，1操作的影响只会影响到距离不超过log的点。

这样我们很容易得到一个$q\log n\log ^2V$的做法

同一深度的修改有一种套路是维护BFS序。

对于子树内的点，我们将log个深度对应的BFS序区间减去相应的影响。

对于修改点的log个有用的祖先，我们也类似操作，注意重复影响的要减去。

这样我们每次修改要修改$log^2V$段区间，用线段树维护又有一个log

由于每个点只会变负一次，我们只需要维护区间减得同时维护区间最小值，发现区间区间最小值变非正了就暴力走下去改，更新答案，这样每个点只会改一次，复杂度是有保证的。

虽然这样已经能通过这道题了（我怎么会说这跑的比log^2还快）

我们还要寻找更优秀的算法。

我们不妨先不修改子树，每次修改点只改祖先。记录$tag_{i,j}$表示点i对距离自己为$j$的儿子的影响

那么每次修改就变成了$log^2$的了，我们只需要对它的log的祖先，每一个改一下标记。

现在可以支持单点查询是否变非正，直接跳log级祖先查一下就好。

但我们要求某个时间的子树内非正点的个数，如果我们能快速算出每个点变非正的时间就好了。

可以整体二分/CDQ分治！

我们对于所有的操作按时间分治，对于分治区间$[l,r]$记一个点集S，表示S中的点在时间[l,r]变非正，我们将出现时间在mid之前的所有操作都处理，一个个查询S中的点是否变非正，看是下放左区间还是右区间。

分析复杂度，每个点会查询log次，每次查询跳log个祖先，两个log

每个操作会用log次，每次时间log^2，这不可取！

我们发现如果每次都把操作暴力插回撤销，这非常的浪费。

因为我们总的需要查询的$tag_{i,j}$的改变次数只有$n\log^2 $

我们可以将$tag$数组可持久化，用一个链表或者vector存下每次改变的时间，查询的时候只需要移一下指针即可，容易看出指针的移动总次数只有$n\log ^2$

那么总的时间复杂度就降到了$O(Q\log^2)$

Code

//why always data structures ????

#include <bits/stdc++.h>

#define fo(i,a,b) for(int i=a;i<=b;++i)

#define fod(i,a,b) for(int i=a;i>=b;--i)

#define N 100005

#define LL long long

using namespace std;

int fs[N],nt[2*N],dt[2*N],pr[N],n,m,w[N],dfw[N],sz[N],dfn[N],ans[N],m1,ask[N][3],f[N],dep[N];

LL sm[N];

//tree_array

int c[N];

int lowbit(int k)

{

	return k&-k;

}

int get(int k)

{

	int s=0;

	while(k) s+=c[k],k-=lowbit(k);

	return s;

}

void put(int k)

{

	while(k<=n) c[k]++,k+=lowbit(k);

}

//prepare

void link(int x,int y)

{

	nt[++m1]=fs[x];

	dt[fs[x]=m1]=y;

}

void dfs(int k,int fa)

{

	f[k]=fa;

	dfw[dfn[k]=++dfn[0]]=k;

	dep[k]=dep[fa]+1;

	sz[k]=1;

	for(int i=fs[k];i;i=nt[i])

	{

		int p=dt[i];

		if(p!=fa) dfs(p,k),sz[k]+=sz[p];

	}

}

//solve

struct node

{

	LL v,t;

};

vector<node> tag[N][32];

int le[N][32],now[N][32],d[N],u1[N],u2[N],ts[N];

void ins(int k,int s,int ti)

{

	if(!s||!k) return;

	int v=s;

	for(int c=0;v;c++)

	{

		int vl=(f[k])?v-(v>>2):v;

		if(le[k][c]==0) tag[k][c].push_back((node){vl,ti});

		else tag[k][c].push_back((node){vl+tag[k][c][le[k][c]-1].v,ti});

		le[k][c]++;

		v>>=1;

	}

	ins(f[k],s>>1,ti);

}

LL query(int k,int ti)

{

	LL s=0;

	for(int p=0;p<=31&&k;k=f[k],p++)

	{

		while(now[k][p]<le[k][p]-1&&tag[k][p][now[k][p]+1].t<=ti) now[k][p]++;

		while(now[k][p]>0&&tag[k][p][now[k][p]].t>ti) now[k][p]--;

		if(now[k][p]<le[k][p]&&tag[k][p][now[k][p]].t<=ti) s+=tag[k][p][now[k][p]].v;

	}

	return s;

}

void doit(int l,int r,int x,int y)

{

	if(x>y) return;

	if(l==r) {fo(i,x,y) ts[d[i]]=l;return;}

	int mid=(l+r)>>1;

	u1[0]=0,u2[0]=0;

	fo(i,x,y)

	{

		if(pr[d[i]]<=query(d[i],mid)) u1[++u1[0]]=d[i];

		else u2[++u2[0]]=d[i];

	}

	fo(j,1,u1[0]) d[x+j-1]=u1[j];

	fo(j,1,u2[0]) d[x+u1[0]+j-1]=u2[j];

	int md=x+u1[0]-1;

	doit(l,mid,x,md);

	doit(mid+1,r,md+1,y);

}

bool cmp(int x,int y)

{

	return ts[x]<ts[y];

}

int main()

{

	cin>>n;

	fo(i,1,n) scanf("%d",&pr[i]);

	fo(i,1,n-1)

	{

		int x,y;

		scanf("%d%d",&x,&y);

		link(x,y),link(y,x);

	}

	dfs(1,0);

	int q;

	cin>>q;

	fo(i,1,q)

	{

		scanf("%d%d",&ask[i][0],&ask[i][1]);

		if(ask[i][0]==1)

		{

			scanf("%d",&ask[i][2]);

			ins(ask[i][1],ask[i][2],i);

		}

	}

	fo(i,1,n) d[i]=i;

	doit(1,q+1,1,n);

	sort(d+1,d+n+1,cmp);

	for(int i=1,j=1;i<=q;i++)

	{

		while(j<=n&&ts[d[j]]<=i) put(dfn[d[j]]),j++;

		if(ask[i][0]==2) printf("%d\n",get(dfn[ask[i][1]]+sz[ask[i][1]]-1)-get(dfn[ask[i][1]]-1));

	}

}

巴特西

[JZOJ6089]【CodeChef 2014 April Challenge】Final Battle of Chef【数据结构】【整体二分】

Description

Solution

Code

最新文章

热门文章