• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

生命周期分析

分析

本题要计算的就是l~r与z的LCA的深度之和

让我想想,是否可以将求多个dep转化一下.

让我们从dep有一个理解,dep就是从i到root总共有多少点.开始

总的来说,我们发现对于一个查询:l,r,Z,所有的LCA都在从Z到根的路径上。从而有一些点,它们对很多的 lca 的深度都有贡献,这个贡献等于这个点下面的LCA的数量,所以我们可以在从每个LCA到根的路径上的每个点的权重上加1。然后从Z向上到根,一路上算出来的重量就是答案。

总而言之,若只有一次询问,则我们想统计答案,只需要将l~r中所有点,从其位置向根节点中的路径的所有点点权+1,最后从z向根节点求一个区间和,即为答案

是时候考虑优化了:每次我们都是从某个点操作到根,所以用树链划分段树就好了。

但是考虑到l ~ r区间外的点对z根路径的贡献每次计数都不能很好的排除,所以每次都要清空段树。

我们每次清空段树,然后从l ~ r重新添加,切割段树的复杂度是\(O(n * logn * logn)\),要做q次,所以复杂度还是不太理想。

看数据范围,\(O(n * logn * logn)\)应该是正解。现在我们要想办法优化最后一个q的复杂度。

我们看到区间l~r,我们需要考虑的是,如何排除l~r之外区间的影响?

我们联想一下类似于主席树的思路,我们从1开始以此将从该节点到根节点的路径中的所有点全部+1,则对于[l,r]的区间影响,我们可以通过用[1,r]的版本减去[1,l-1]版本的影响

我们可以将询问的区间拆开为两个,将询问离线查询。按照右端点从小到大排序(左端点都是根),然后按从小到大的顺序添加点,每遇到一个询问就查询一次,从而排除掉区间之外的点的影响,也就优化掉一个 q 的复杂度。

具体实现过程看一下代码。

Ac_code

#includebits/stdc。h

使用命名空间std

const int N=5e4 10,mod=201314

typedef pairint,int PII;

typedef long long LL

结构节点

{

int l,r,sum,tag

} tr[N2];

结构查询

{

int r,z,id;//每个查询分为两个部分,分别存储一个查询的l-1,r,Z,查询的编号,是左端点还是右端点。

bool f;

布尔运算符(常量查询W)常量

{

返回rW.r

}

} que[N1];

int h[N],e[N],ne[N],idx

int sz[N],son[N],fa[N],dep[N];

int top[N],id[N],ts;

PII人;

//对于每个ans,第一个存储的是1~l-1版本中从Z到根的权重之和。

//而每个ans的第二个存储的是1 ~ R版本中Z到根的权重之和。

//两者相减可以消除Z到根节点其他区间对权重和的影响。

int n,q;

void add(int a,int b)

{

e[idx]=b,ne[idx]=h[a],h[a]=idx;

}

void dfs1(int u,int depth)

{

sz=1,dep=深度;

for(int I=h;~我;我=ne)

{

int j=e

dfs1(j,深度1);

SZ=SZ[j];

if(SZ[j]SZ[son])son=j;

}

}

void dfs2(int u,int tp)

{

top=tp,id=ts;

如果(!子)回归;

dfs2(son,TP);

for(int I=h;~我;我=ne)

{

int j=e

if(j==son)继续;

dfs2(j,j);

}

}

无效俯卧撑(英寸

t u) { tr.sum = (LL)(tr[u<<1].sum + tr[u<<1|1].sum)%mod; } void pushdown(int u) { auto &root = tr,&left = tr[u<<1],&right = tr[u<<1|1]; if(root.tag) { left.tag = (LL)(left.tag + root.tag)%mod; right.tag = (LL)(right.tag + root.tag)%mod; left.sum = (LL)(left.sum + 1ll*(left.r - left.l + 1)*root.tag%mod)%mod; right.sum = (LL)(right.sum + 1ll*(right.r - right.l + 1)*root.tag%mod)%mod; root.tag = 0; } } void build(int u,int l,int r) { tr = {l,r}; if(l==r) return ; int mid = l + r >> 1; build(u<<1,l,mid),build(u<<1|1,mid+1,r); } void modify(int u,int l,int r) { if(l<=tr.l&&tr.r<=r) { tr.tag ++ ; tr.sum = (LL)(tr.sum + tr.r - tr.l + 1)%mod; return ; } pushdown(u); int mid = tr.l + tr.r >> 1; if(l<=mid) modify(u<<1,l,r); if(r>mid) modify(u<<1|1,l,r); pushup(u); } int query(int u,int l,int r) { if(l<=tr.l&&tr.r<=r) return tr.sum; int res = 0; pushdown(u); int mid = tr.l + tr.r >> 1; if(l<=mid) res = (LL)(res + query(u<<1,l,r))%mod; if(r>mid) res = (LL)(res + query(u<<1|1,l,r))%mod; return res; } void modify_chain(int x) { while(top[x]!=1) { modify(1,id[top[x]],id[x]); x = fa[top[x]]; } modify(1,1,id[x]); } int query_chain(int x) { int res = 0; while(top[x]!=1) { res = (LL)(res + query(1,id[top[x]],id[x]))%mod; x = fa[top[x]]; } res = (LL)(res + query(1,1,id[x]))%mod; return res; } int main() { scanf("%d%d",&n,&q); memset(h,-1,sizeof h); for(int i=2;i<=n;i++) { cin>>fa;fa++; add(fa,i); } for(int i=0;i<q;i++) { int l,r,z;scanf("%d%d%d",&l,&r,&z); l++,r++,z++; que[i*2] = {l-1,z,i,1}; que[i*2+1] = {r,z,i,0}; } dfs1(1,1); dfs2(1,1); build(1,1,n); sort(que,que+q*2); int now = 0; for(int i=0;i<q*2;i++) { while(now<que.r) modify_chain(++now);//对于每一个点都将其到根的路径中的所有点点权+1 if(que.f) ans[que.id].first = query_chain(que.z);//遇到询问后,记录一下这是哪个询问的左端点版本还是右端点版本 else ans[que.id].second = query_chain(que.z); } for(int i=0;i<q;i++) printf("%d\n",((ans.second-ans.first)%mod+mod)%mod); return 0; }
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now