[DS记录]CF757G Can Bash Save the Day?
command_block
·
·
个人记录
题意 : 给出一棵树,边有边权,再给出一个排列p.
-
给出l,r,x, 求\sum\limits_{l\leq i\leq r}dis(p_i,x)
-
交换p_i,p_{i+1}
------------
这题难度咋那么吓人啊,`CF`场出大数据解构会被人喷吧……
考虑维护“前缀”状态,答案可以差分一下。
相邻交换的套路可见 : [P3939 数颜色](https://www.luogu.com.cn/problem/P3939)
如果交换了$p_i,p_{i+1}$,相当于从状态 $i$ 中删去一个又加入一个。
再考虑 : [P3241 [HNOI2015]开店](https://www.luogu.com.cn/problem/P3241)
考虑先三度化(没啥细节),再建立可持久化边分树。(可持久化点分树是行不通的,难以管理多个儿子)
边分树上要记录区域内现有点数和,深度和。查询的时候贡献是 查询点深度x对面点的个数+对面的深度和。
时空复杂度都是$O(n\log n)$的,常数较大。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define INF 1000000000
#define MaxN 400500
using namespace std;
inline int read(){
int X=0;char ch=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return X;
}
struct Line
{int t,l,nxt;}g[MaxN<<1];
int tl,fir[MaxN];
void adl(int f,int t,int len){
g[++tl]=(Line){t,len,fir[f]};fir[f]=tl;
g[++tl]=(Line){f,len,fir[t]};fir[t]=tl;
}
int t[MaxN],tn,siz[MaxN],
vis[MaxN],ef,mp[MaxN];
void pfs(int u)
{
vis[t[++tn]=u]=ef;siz[u]=1;
for (int i=fir[u],v;i;i=g[i].nxt)
if (vis[v=g[i].t]<ef)
{pfs(v);siz[u]+=siz[v];}
}
int grt(int u)
{
ef++;tn=0;pfs(u);
int rt=0;
for (int i=1,u;i<=tn;i++){
u=t[i];
mp[u]=max(siz[u],tn-siz[u]);
if (mp[u]<=mp[rt])rt=u;
}return rt;
}
ll d[33][MaxN],*dis;
void dfs(int u)
{
vis[u]=ef;
for (int i=fir[u],v;i;i=g[i].nxt)
if (vis[v=g[i].t]<ef){
dis[v]=dis[u]+g[i].l;
dfs(v);
}
}
struct Node
{int dep,t[2],c[2];ll s[2];}
a[MaxN*33];
int tot,rt[MaxN>>1],fa[MaxN<<1];
int build(int u,int dep)
{
if (tn==1)return u;
int v=0,tp=0;
for (int i=fir[u];i;i=g[i].nxt)
if (siz[g[i].t]>siz[u])
{v=g[tp=i].t;break;}
g[tp].t=g[tp^1].t=0;dis=d[dep];
dis[u]=g[tp].l;ef++;dfs(u);
dis[v]=0;ef++;dfs(v);
int pos=++tot;
a[pos].dep=dep++;
fa[u=build(grt(u),dep)]=pos;a[pos].t[0]=u;
fa[v=build(grt(v),dep)]=pos;a[pos].t[1]=v;
return pos;
}
bool td[63];int st[63];
void grt(int u,int rt)
{
for (tn=0;u;u=fa[u])
td[++tn]=(a[fa[u]].t[1]==u);
reverse(td+1,td+tn+1);
st[1]=u=rt;
for (int i=2;i<=tn;i++)
st[i]=u=a[u].t[td[i]];
for (int i=1;i<=tn;i++)td[i]=td[i+1];
}
int np[63];
int chg(int u,int rt,bool op)
{
grt(u,rt);rt=tot+1;
for (int i=1,p;i<tn;i++){
a[p=++tot]=a[st[i]];
a[p].c[td[i]]+=op ? 1 : -1;
a[p].s[td[i]]+=op ? d[a[p].dep][u] : -d[a[p].dep][u];
a[p].t[td[i]]=tot+1;
}a[tot].t[td[tn-1]]=st[tn];
return rt;
}
ll qry(int u,int rt)
{
ll ret=0;grt(u,rt);
for (int i=1;i<tn;i++){
int p=st[i],c=a[p].c[td[i]^1];
ll sum=a[p].s[td[i]^1];
ret+=1ll*c*d[a[p].dep][u]+sum;
}return ret;
}
int n,q,p[MaxN>>1],las[MaxN>>1];
struct SLine
{int f,t,l;}l[MaxN>>1];
void cre(int u,int v,int len){
if (siz[v]>siz[u])swap(u,v);
adl(++tn,las[u],0);las[u]=tn;
adl(tn,v,len);
}
int main()
{
n=read();q=read();
for (int i=1;i<=n;i++)p[i]=read();
for (int i=1,f,t;i<n;i++){
f=read();t=read();
l[i]=(SLine){f,t,read()};
adl(f,t,l[i].l);
}ef++;pfs(1);tl=1;tn=n;
for (int i=1;i<=n;i++)fir[las[i]=i]=0;
for (int i=1;i<n;i++)
cre(l[i].f,l[i].t,l[i].l);
vis[0]=mp[0]=INF;
rt[0]=(tot=n+n)+1;
build(grt(1),0);
for (int i=1;i<=n;i++)
rt[i]=chg(p[i],rt[i-1],1);
ll las=0;
for (int i=1,op,u,l,r;i<=q;i++){
op=read();
if (op==1){
l=read()^las;
r=read()^las;
u=read()^las;
las=qry(u,rt[r])-qry(u,rt[l-1]);
printf("%lld\n",las);
las&=((1<<30)-1);
}else {
u=read()^las;
rt[u]=chg(p[u+1],rt[u],1);
rt[u]=chg(p[u],rt[u],0);
swap(p[u],p[u+1]);
}
}return 0;
}
```