当前位置:网站首页>[lnoi2014] LCA - tree chain subdivision - multipoint LCA depth and problems
[lnoi2014] LCA - tree chain subdivision - multipoint LCA depth and problems
2022-04-23 09:42:00 【Zimba_】
Templates : Topic link
Advanced : Topic link
The question :
Given a tree n n n A dot tree . q q q Time to ask , Each query gives three values l , r , z l,r,z l,r,z, Ask for ∑ i = l r d e p ( L C A ( i , z ) ) \sum_{i=l}^{r}dep(LCA(i,z)) ∑i=lrdep(LCA(i,z)).
( n < = 1 e 5 , q < = 1 e 5 ) (n<=1e5,q<=1e5) (n<=1e5,q<=1e5)
Ideas :
Consider asking for some a a a Sum point b b b Of L C A LCA LCA depth , We can put some a a a To r o o t root root All points on the path are weighted 1 1 1, Then query points b b b To r o o t root root Their path and are their L C A LCA LCA Depth . Modify... In reverse b b b To r o o t root root The path of , check a a a To r o o t root root The path and are the same .
Then consider multiple points and single points L C A LCA LCA Depth and , You can take each point to r o o t root root All paths add 1 1 1, Then query a single point to r o o t root root The path and .
This becomes the operation of tree chain modification and query , You can use tree chain partition to maintain .
But this question can't be asked every time o ( ( r − l ) l o g 2 n ) o((r-l)log^2n) o((r−l)log2n) Modification of , So we need to find the prefix sum offline , Just take the prefix and subtract it again . Total complexity o ( ( n + q ) l o g 2 n ) o((n+q)log^{2}n) o((n+q)log2n).
Code :
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=201314;
typedef pair<ll,ll> P;
ll tree[1000005],laz[1000005];
void push_down(ll k,ll l,ll r)
{
ll mid=(l+r)/2;
tree[2*k+1]+=laz[k]*(mid-l+1);
laz[2*k+1]+=laz[k];
tree[2*k+2]+=laz[k]*(r-mid);
laz[2*k+2]+=laz[k];
laz[k]=0;
}
ll query(ll k,ll l,ll r,ll x,ll y)
{
if(x<=l&&r<=y)
{
return tree[k];
}
push_down(k,l,r);
ll ans=0,mid=(l+r)/2;
if(x<=mid)ans+=query(2*k+1,l,mid,x,y);
if(y>=mid+1)ans+=query(2*k+2,mid+1,r,x,y);
return ans;
}
void update(ll k,ll l,ll r,ll x,ll y,ll a)
{
if(x<=l&&r<=y)
{
tree[k]+=a*(r-l+1);
laz[k]+=a;
return ;
}
push_down(k,l,r);
ll mid=(l+r)/2;
if(x<=mid)update(2*k+1,l,mid,x,y,a);
if(y>=mid+1)update(2*k+2,mid+1,r,x,y,a);
tree[k]=tree[2*k+1]+tree[2*k+2];
}
vector<ll>v[100005];
ll dep[100005],fa[100005],siz[100005],son[100005];
void dfs1(ll x,ll pre)
{
siz[x]=1;
dep[x]=dep[pre]+1;
fa[x]=pre;
for(ll i=0;i<v[x].size();i++)
{
ll to=v[x][i];
if(to!=pre)
{
dfs1(to,x);
siz[x]+=siz[to];
}
}
son[x]=x;
for(ll i=0;i<v[x].size();i++)
{
ll to=v[x][i];
if(to!=pre)
{
if(son[x]==x||siz[son[x]]<siz[to])son[x]=to;
}
}
}
ll id[100005],idx,top[100005];
void dfs2(ll x,ll pre)
{
if(son[pre]==x)top[x]=top[pre];
else top[x]=x;
id[x]=++idx;
if(son[x]!=x)dfs2(son[x],x);
for(ll i=0;i<v[x].size();i++)
{
ll to=v[x][i];
if(to!=pre&&to!=son[x])
{
dfs2(to,x);
}
}
}
ll n,m;
void add(ll x,ll val)
{
while(top[x]!=1)
{
update(1,1,n,id[top[x]],id[x],val);
x=fa[top[x]];
}
update(1,1,n,id[top[x]],id[x],val);
}
ll get(ll x)
{
if(x==0)return 0;
ll ans=0;
while(top[x]!=1)
{
ans+=query(1,1,n,id[top[x]],id[x]);
x=fa[top[x]];
}
ans+=query(1,1,n,id[top[x]],id[x]);
return ans;
}
map<ll,ll>mp[100005];
vector<P>ve;
struct Q
{
ll l,r,z;
}q[200005];
int main()
{
scanf("%lld%lld",&n,&m);
for(ll i=2;i<=n;i++)
{
ll a;
scanf("%lld",&a);
a++;
v[a].push_back(i);
v[i].push_back(a);
}
dfs1(1,0);
dfs2(1,0);
for(int i=1;i<=m;i++)
{
ll l,r,z;
scanf("%lld%lld%lld",&l,&r,&z);
l++;r++;z++;
q[i]=Q{
l,r,z};
ve.push_back(P(l-1,z));
ve.push_back(P(r,z));
}
sort(ve.begin(),ve.end());
int cnt=1;
for(int i=0;i<ve.size();i++)
{
while(cnt<=n&&cnt<=ve[i].first)
{
add(cnt,1);
cnt++;
}
mp[ve[i].first][ve[i].second]=get(ve[i].second)%mod;
}
for(int i=1;i<=m;i++)
{
ll l=q[i].l,r=q[i].r,z=q[i].z;
ll ans=mp[r][z]-mp[l-1][z];
printf("%lld\n",(ans%mod+mod)%mod);
}
return 0;
}
版权声明
本文为[Zimba_]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204230621425343.html
边栏推荐
- ABAP implementation publishes restful services for external invocation example
- SAP CR transmission request sequence and dependency check
- How to use SQL statement union to get another column of another table when the content of a column in a table is empty
- golang力扣leetcode 396.旋转函数
- AI上推荐 之 MMOE(多任务yyds)
- Little girl walking
- Vivo, hardware safe love and thunder
- Image processing in opencv -- Introduction to contour + contour features
- Using sqlmap injection to obtain the account and password of the website administrator
- MySQL of database -- Fundamentals
猜你喜欢
Redis 内存占满导致的 Setnx 命令执行失败
MySQL of database -- overview and installation
ABAP 7.4 SQL Window Expression
Kettle实验 转换案例
亚马逊云科技入门资源中心,从0到1轻松上云
Exclusive thoughts and cases of JS
Kernel PWN learning (3) -- ret2user & kernel ROP & qwb2018 core
重载、重写、隐藏的对比
653. Sum of two IV - input BST
How to use SQL statement union to get another column of another table when the content of a column in a table is empty
随机推荐
What is monitoring intelligent playback and how to use intelligent playback to query video recording
kettle庖丁解牛第14篇之JSON输入
Kettle实验 (三)
《数字电子技术基础》3.1 门电路概述、3.2 半导体二极管门电路
AI上推荐 之 MMOE(多任务yyds)
GUI, CLI and UNIX Philosophy
Dropout技术之随机神经元与随机深度
108. Convert an ordered array into a binary search tree
Less than 100 secrets about prime numbers
kernel-pwn学习(3)--ret2user&&kernel ROP&&QWB2018-core
《數字電子技術基礎》3.1 門電路概述、3.2 半導體二極管門電路
SAP pi / PO soap2proxy consumption external WS example
Two methods of building Yum source warehouse locally
Go language learning notes - language interface | go language from scratch
JS prototype chain
SAP CR transmission request sequence and dependency check
Compile and debug mysql8 with clion under MacOS x
Kettle experiment conversion case
Employee probation application (Luzhou Laojiao)
NPM reports an error: operation not allowed, MKDIR 'C: \ program files \ node JS \ node_ cache _ cacache’