题目描述
小Y家里有一个大森林，里面有 $n$ 棵树，编号从 $1$ 到 $n$ 。一开始这些树都只是树苗，只有一个节点，标号为 $1$ 。这些树都有一个特殊的节点，我们称之为生长节点，这些节点有生长出子节点的能力。
小Y掌握了一种魔法，能让第 $l$ 棵树到第 $r$ 棵树的生长节点长出一个子节点。同时她还能修改第 $l$ 棵树到第 $r$ 棵树的生长节点。
她告诉了你她使用魔法的记录，你能不能管理她家的森林，并且回答她的询问呢？
输入格式
第一行包含 2 个正整数 $n,m$，共有 $n$ 棵树和 $m$ 个操作。
接下来 $m$ 行，每行包含若干非负整数表示一个操作，操作格式为：
- $0$ $l$ $r$ 表示将第 $l$ 棵树到第 $r$ 棵树的生长节点下面长出一个子节点，子节点的标号为上一个 $0$ 号操作叶子标号加 $1$（例如，第一个 $0$ 号操作产生的子节点标号为 $2$），$l$ 到 $r$ 之间的树长出的节点标号都相同。保证 $1\leq l \leq r \leq n$。
- $1$ $l$ $r$ $x$ 表示将第 $l$ 棵树到第 $r$ 棵树的生长节点改到标号为 $x$ 的节点。对于区间内的每棵树，如果标号 $x$ 的点不在其中，那么这个操作对该树不产生影响。保证 $1 \leq l \leq r \leq n$，$x$ 不超过当前所有树中节点最大的标号。
- $2$ $x$ $u$ $v$ 询问第 $x$ 棵树中节点 $u$ 到节点 $v$ 的距离，也就是在第 $x$ 棵树中从节点 $u$ 和节点 $v$ 的最短路上边的数量。保证 $1 \leq x \leq n$，这棵树中节点 $u$ 和节点 $v$ 存在。
输出格式
输出包括若干行，按顺序对于每个小Y的询问输出答案。
限制与约定
| 测试点编号 | $n$ | $m$ | 约定 |
|---|---|---|---|
| 1 | $\leq 10^3$ | $\leq 10^3$ | |
| 2 | $\leq 10^5$ | $\leq 2 \times 10^5$ | 保证每次 $0$ 和 $1$ 操作修改的是 $1$ 到 $n$ 所有的树 |
| 3 | |||
| 4 | 保证每次 $0$ 操作生长节点都是这些树中编号最大的节点 | ||
| 5 | |||
| 6 | |||
| 7 | |||
| 8 | |||
| 9 | |||
| 10 |
时间限制：$2\texttt{s}$
空间限制：$256\texttt{MB}$
据说这道题目是cls出的....部分分还是给的很良心的
分析1
第一部分数据，直接暴力dfs，随便搞10分
第二部分数据，写一个LCA即可，20分
第三部分数据，由于生长点都是最大点，那么只需要线段树维护，由于有\(n\)棵线段树，直接主席树搞一搞就好了
这三部分似乎都是纯模板啊？直接可以获得50分
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<climits>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#define ll long long
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
return *p1++;
}
inline void read(int &x){
char c=nc(),b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline void read(ll &x){
char c=nc(),b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
int wt,ss[19];
inline void print(int x){
if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(ll x){
if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}
int n,m;
int Grow[100010],D[1010][1010],FA[1010][1010],c[10010];
struct data
{
int t,x,y,z;
}Work[200010];
int S,d[200010],p[400010][20];
int root[300010],tot;
int Ls[300010*30],Rs[300010*30],add[300010*30];
ll sum[300010*30];
inline int bulidtree(int L,int R){
int k=tot++;
add[k]=0;
if (L==R){
scanf("%lld",&sum[k]);
return k;
}
int mid=(L+R)>>1;
Ls[k]=bulidtree(L,mid);
Rs[k]=bulidtree(mid+1,R);
sum[k]=sum[Ls[k]]+sum[Rs[k]];
return k;
}
inline int update(int o,int L,int R,int x,int LL,int RR){
int k=tot++;
Ls[k]=Ls[o]; Rs[k]=Rs[o]; add[k]=add[o]; sum[k]=sum[o];
sum[k]+=(ll)x*(R-L+1);
if (LL==L && RR==R){
add[k]+=x;
return k;
}
int mid=(LL+RR)>>1;
if (R<=mid) Ls[k]=update(Ls[k],L,R,x,LL,mid);
else if (L>mid) Rs[k]=update(Rs[k],L,R,x,mid+1,RR);
else {
Ls[k]=update(Ls[k],L,mid,x,LL,mid);
Rs[k]=update(Rs[k],mid+1,R,x,mid+1,RR);
}
return k;
}
inline ll query(int o,int L,int R,int LL,int RR){
if (L==LL && R==RR) return sum[o];
int mid=(LL+RR)>>1;
ll ret=(ll)add[o]*(R-L+1);
if (R<=mid) return ret+query(Ls[o],L,R,LL,mid);
else if (L>mid) return ret+query(Rs[o],L,R,mid+1,RR);
else return ret+query(Ls[o],L,mid,LL,mid)+query(Rs[o],mid+1,R,mid+1,RR);
}
int lca(int x,int y)
{
if (d[x]<d[y]) swap(x,y);
int i;
for (i=0;(1<<i)<=d[x];i++);i--;
for (int j=i;j>=0;j--)
if (d[x]-(1<<j)>=d[y]) x=p[x][j];
if (x==y) return x;
for (int j=i;j>=0;j--)
if (p[x][j]!=-1 && p[x][j]!=p[y][j])
x=p[x][j],y=p[y][j];
return p[x][0];
}
int main()
{
read(n);read(m);
if (n<=1000 && m<=1000)
{
int s=1;
for (int i=1;i<=n;i++)
Grow[i]=1,D[i][1]=1;
int x,y,z;
while (m--)
{
read(x);
if (x==0)
{
read(x);read(y);
s++;
for (int i=x;i<=y;i++)
FA[i][s]=Grow[i],D[i][s]=D[i][Grow[i]]+1;
}
else if (x==1)
{
read(x);read(y);read(z);
for (int i=x;i<=y;i++)
if (D[i][z]>0) Grow[i]=z;
}
else if (x==2)
{
read(x);read(y);read(z);
int t=D[x][y]+D[x][z];
while (D[x][y]>D[x][z]) y=FA[x][y];
while (D[x][z]>D[x][y]) z=FA[x][z];
while (y!=z) y=FA[x][y],z=FA[x][z];
print(t-2*D[x][y]),putchar('\n');
}
}
return 0;
}
int flag=0,s=1,t=1;
for (int i=1;i<=m;i++)
{
read(Work[i].t);
if (Work[i].t==0 || Work[i].t==1)
{
read(Work[i].x);read(Work[i].y);
if (Work[i].x!=1 || Work[i].y!=n) flag=1;
if (Work[i].t==1) read(Work[i].z);
}
else read(Work[i].x),read(Work[i].y),read(Work[i].z);
}
if (!flag)
{
int s=1,grow=1;
d[1]=1;
for (int i=1;i<=m;i++)
{
if (Work[i].t==0)
{
s++;
d[s]=d[grow]+1;
p[s][0]=grow;
for (int j=1;(1<<j)<=s;j++)
if (p[s][j-1]!=-1) p[s][j]=p[p[s][j-1]][j-1];
}
else if (Work[i].t==1) grow=Work[i].z;
else
{
int x=Work[i].y,y=Work[i].z,z=lca(x,y);
print(d[x]+d[y]-2*d[z]),putchar('\n');
}
}
}
else
{
tot=0;
root[0]=bulidtree(1,n);
int now=1;
for (int i=1;i<=m;i++)
if (Work[i].t==0)
{
now++;
root[now]=update(root[now-1],Work[i].x,Work[i].y,1,1,n);
}
else if (Work[i].t==2)
{
print(abs(query(root[Work[i].z],Work[i].x,Work[i].x,1,n)-query(root[Work[i].y],Work[i].x,Work[i].x,1,n))),putchar('\n');
}
}
return 0;
}
京公网安备 11010502036488号