crz_qwq @ 2024-07-25 12:42:50
rt
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n=2;
int tr[N<<2];
void pushup(int p){tr[p]=tr[p<<1]+tr[p<<1|1];}
void update(int p,int pl,int pr,int x,int d)
{
if(pl==x&&pr==x)
{
tr[p]+=d;
return ;
}
int mid=(pl+pr)>>1;
update(p<<1,pl,mid,x,d);
update(p<<1|1,mid+1,pr,x,d);
}
int query(int p,int pl,int pr,int L,int R)
{
if(L<=pl&&pr<=R)
return tr[p];
if(R<pl||pr<L)
return 0;
int mid=(pl+pr)>>1;
return query(p<<1,pl,mid,L,R)+query(p<<1|1,mid+1,pr,L,R);
}
vector<int>edge[N];
int son[N],sz[N],fa[N],dep[N];
int dfn[N],rnk[N],top[N],id;
void dfs1(int u,int ft)
{
sz[u]=1;
fa[u]=ft;
dep[u]=dep[ft]+1;
son[u]=-1;
for(auto &v:edge[u])
{
if(v==ft)
continue;
dfs1(v,u);
sz[u]+=sz[v];
if(sz[v]>sz[son[u]])
son[u]=v;
}
}
void dfs2(int u,int t)
{
top[u]=t;
dfn[u]=++id;
rnk[id]=u;
dfs2(son[u],t);
for(auto &v:edge[u])
{
if(v==fa[u])
continue;
dfs2(v,v);
}
}
int qrange(int x,int y)
{
int res=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
res+=query(1,1,n,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
return res+query(1,1,n,dfn[x],dfn[y]);
}
signed main()
{
int x,y;
cin>>x>>y;
edge[1].emplace_back(2);
edge[2].emplace_back(1);
dfs1(1,0);
dfs2(1,1);
update(1,1,n,dfn[1],x);
update(1,1,n,dfn[2],y);
cout<<qrange(1,2);
}by haimingbei @ 2024-07-25 12:52:17
？？
by Igallta @ 2024-07-25 12:57:15
@crz_qwq
书剖线段树，高射炮打蚊子/wul
by Igallta @ 2024-07-25 12:58:02
@crz_qwq
哥你是不是没有 build？
by crz_qwq @ 2024-07-25 12:59:02
@Igallta 不需要build吧，我一般不写build的
by ran_qwq @ 2024-07-25 13:04:30
dfs2 v=son[u]没有continue
by Stars_visitor_tyw @ 2024-07-25 13:04:37
借楼求助马蜂优良0pts
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int a[N], n, m, tag[4*N], tree[4*N], mod, mul[4*N];
void pushup(int cur)
{
tree[cur]=tree[cur*2]%mod+tree[cur*2+1]%mod;
return ;
}
void addtag(int cur, int lt, int rt, int val)
{
tag[cur]+=val;
tree[cur]+=(rt-lt+1)*val%mod;
return ;
}
void addtag1(int cur, int lt, int rt, int val)
{
tag[cur]=tag[cur]*val%mod;
mul[cur]=mul[cur]*val%mod;
tree[cur]=tree[cur]*val%mod;
return ;
}
void pushdown(int cur, int lt, int rt)
{
if(tag[cur]==0&&mul[cur]==1)
{
return ;
}
int mid=(lt+rt)>>1;
addtag1(cur*2,lt,mid,mul[cur]);
addtag1(cur*2+1,mid+1,rt,mul[cur]);
addtag(cur*2,lt,mid,tag[cur]);
addtag(cur*2+1,mid+1,rt,tag[cur]);
tag[cur]=0;
mul[cur]=1;
return ;
}
void build(int cur, int lt, int rt)
{
if(lt==rt)
{
tree[cur]=a[lt];
return ;
}
int mid=lt+rt>>1;
build(cur*2,lt,mid);
build(cur*2+1,mid+1,rt);
pushup(cur);
return ;
}
int query(int cur, int lt, int rt, int qx, int qy)
{
if(qy<lt||qx>rt)
{
return 0;
}
if(qx<=lt&&rt<=qy)
{
return tree[cur];
}
pushdown(cur,lt,rt);
int mid=lt+rt>>1;
return query(cur*2,lt,mid,qx,qy)+query(cur*2+1,mid+1,rt,qx,qy);
}
void update(int cur, int lt, int rt, int qx, int qy, int val)
{
if(qy<lt||qx>rt)
{
return ;
}
if(qx<=lt&&rt<=qy)
{
addtag(cur,lt,rt,val);
return ;
}
pushdown(cur,lt,rt);
int mid=lt+rt>>1;
update(cur*2,lt,mid,qx,qy,val);
update(cur*2+1,mid+1,rt,qx,qy,val);
pushup(cur);
return ;
}
void update1(int cur, int lt, int rt, int qx, int qy, int val)
{
if(qy<lt||qx>rt)
{
return ;
}
if(qx<=lt&&rt<=qy)
{
addtag1(cur,lt,rt,val);
return ;
}
pushdown(cur,lt,rt);
int mid=lt+rt>>1;
update1(cur*2,lt,mid,qx,qy,val);
update1(cur*2+1,mid+1,rt,qx,qy,val);
pushup(cur);
return ;
}
signed main()
{
cin>>n>>m;
a[1]=n,a[2]=m;
for(int i=1;i<=100005;i++)
{
mul[i]=1;
}
build(1,1,2);
update1(1,1,2,1,2,1);
cout<<query(1,1,2,1,2);
return 0;
}by crz_qwq @ 2024-07-25 13:06:00
@ran_qwq thx
by crz_qwq @ 2024-07-25 13:07:20
@ran_qwq 过了thx
by crz_qwq @ 2024-07-25 13:09:41
@taoyiwei17_cfynry %%% 小菊若看不懂
by ran_qwq @ 2024-07-25 13:10:01
@taoyiwei17_cfynry 把取模删了