第二十届浙大城市学院程序设计竞赛 I.Magic Tree DFS序线段树

传送门

大致思路：

  我们知道dfs序上的整颗子树dfs序编号连续，因为每次删除一个点或者新增一个点都导致子树上所有点的深度加一或者减一。由于是区间修改所以我们考虑dfs序上建线段树。

#include <iostream>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <stack>
#include <queue>
#include <numeric>
#include <cassert>
#include <bitset>
#include <cstdio>
#include <vector>
#include <unordered_set>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <deque>
#include <tuple>
#include <array>
 
#define all(a) a.begin(), a.end()
#define cnt0(x) __builtin_ctz(x)
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define cntone(x) __builtin_popcount(x)
#define db double
#define fs first
#define se second
#define AC main(void)
#define ls u << 1
#define rs u << 1 | 1
typedef std::pair<int, int> PII;
#define HYS std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
const long double eps = 1e-9;
int MOD = 571373;

const int N = 4e5 + 10, M = 6e5 + 10;
const int INF = 0x3f3f3f3f;

ll min(ll a, ll b)	{return a > b ? b : a;}
ll max(ll a, ll b)	{return a > b ? a : b;}
int min(int a, int b)	{return a > b ? b : a;}
int max(int a, int b)	{return a > b ? a : b;}


int n , m, _;

int d1[] = {0, 0, 1, -1};
int d2[] = {1, -1, 0, 0};

int w[N], h[N], e[N << 1], ne[N << 1], idx;
int id[N], nw[N], cnt;
int dep[N], sz[N], top[N], fa[N], son[N], ans[N], rid[N];
int vis[N];
int realfa[N];
int realson[N];
int iddeep[N];

struct node{
	int l, r;
	int add;
	int v;
}tr[N << 2];

inline void build(int u, int l, int r){
	tr[u] = {l, r};
	if(l == r){
		tr[u].v = iddeep[l];
		return ;
	}
	
	int mid = l + r >> 1;
	
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
}

inline void pushdown(int u){
	if(tr[u].add){
		int x = tr[u].add;
		tr[ls].v += x;
		tr[rs].v += x;
		tr[ls].add += x;
		tr[rs].add += x;
		tr[u].add = 0;
	}
}

inline int query(int u, int x){
	if(tr[u].l == tr[u].r)	return tr[u].v;
	
	pushdown(u);
	
	int mid = tr[u].l + tr[u].r >> 1;
	if(x <= mid)	return query(u << 1, x);
	return query(u << 1 | 1, x);
}

inline void modify(int u, int l, int r, int x){
	if(tr[u].l == tr[u].r){
		tr[u].v += x;
		return ;
	}
	
	if(tr[u].l >= l && tr[u].r <= r){
		tr[u].add += x;
		return ;
	}
	
	pushdown(u);
	
	int mid = tr[u].l + tr[u].r >> 1;
	
	if(l <= mid)	modify(u << 1, l, r, x);
	if(r > mid)	modify(u << 1 | 1, l, r, x);
}

inline void ADD(int u, int x, int v){
	if(tr[u].l == tr[u].r){
		tr[u].v = v;
		return ;
	}
	
	pushdown(u);
	
	int mid = tr[u].l + tr[u].r >> 1;
	if(x <= mid)	ADD(u << 1, x, v);
	else ADD(u << 1 | 1, x, v);
}

inline void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
//统计子树大小 并且 找出重儿子
inline void dfs1(int u, int father, int depth){
    dep[u] = depth, fa[u] = father, sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if (j == father || realfa[j] != u) continue;
        if(j <= n)
        	dfs1(j, u, depth + 1);
        else dfs1(j, u, depth);
        sz[u] += sz[j];
        if (sz[son[u]] < sz[j]) son[u] = j;
    }
}

//dfs序 nw标记dfs为cnt的时候对应的树上点的权值 top标记父亲是谁
inline void dfs2(int u, int t){
    id[u] = ++ cnt, nw[cnt] = w[u], top[u] = t, rid[cnt] = u;
    iddeep[id[u]] = dep[u];
    if(!son[u]) return;
    dfs2(son[u], t);
    for (int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if (j == fa[u] || j == son[u] || realfa[j] != u) continue;
        dfs2(j, j);
    }
}

inline void Init(){
	dfs1(1, -1, 1);
        dfs2(1, 1);
}

inline void solve(){
    std::cin >> n >> m;
    
    memset(h, -1, sizeof h);
    
    std::vector<int> last(n + 1);
    for(int i = 2; i <= n; i ++){
    	int x;
    	std::cin >> x;
    	realfa[i] = x;
    	add(x, i);
    	last[i] = x;
    }
    
    std::vector<PII> g(m);
    for(int i = 0; i < m; i ++){
    	int op, x;
    	std::cin >> op >> x;
    	g[i] = {op, x};
    	if(op == 1){
    		int father = realfa[x];
    		realfa[x] = i + n + 1;
    		realfa[i + n + 1] = father;
    		add(i + n + 1, x);
    		add(father, i + n + 1);
    	}
    }
    
    Init();
    
    int szz = n + m;

	build(1, 1, szz);

	for(int i = 2; i <= szz; i ++){
		if(i <= n){
			realfa[i] = last[i];
			realson[last[i]] = i;
		}else realfa[i] = realson[i] = 0;
	}

	for(int i = 0; i < m; i ++){
		auto &[op, x] = g[i];
		if(op == 1){
			int father = realfa[x];
			modify(1, id[x], id[x] + sz[x] - 1, 1);
			realfa[i + n + 1] = father;
			realfa[x] = i + n + 1;
			realson[father] = n + i + 1;
			realson[n + i + 1] = x;
			int depth = query(1, id[father]);
			ADD(1, id[i + n + 1], depth + 1);
		}else if(op == 2){
			int father = realfa[x];
			int sonn = realson[x];
			realfa[sonn] = father;
			realson[father] = sonn;
			modify(1, id[x], id[x] + sz[x] - 1, -1);
		}else{
			std::cout << query(1, id[x]) << '\n';
		}
	}
}


int main(){
    HYS
	_ = 1;
  	//_ = read();
	while(_ --)
    	solve();

    return 0;
}