@codechef - SONATR@ Sonya and Tree

分手后的思念是犯贱 2023-06-01 13:56 7阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

给定 p 为 0~N-1 的一个排列，并给定一棵 N 个点的树。  
我们称一个包含 L 个结点的路径是“漂亮”的，当且仅当对于 0 ≤ i ≤ L-1，路径都存在 v 使得 p\[v\] = i，一棵树的“漂亮程度”被定义为其包含的“漂亮”路径数量。  
现给定 M 次操作，每次交换 p\[u\] 与 p\[v\]，询问每次操作完后当前树的“漂亮程度”。

**输入格式**  
输入的第一行包含一个整数 N，第二行包含 N 个整数 p1,p2,...,pN。  
接下来 N −1 行，每行包含两个整数 u 和 v，代表节点 u 和 v 之间有一条边。 接下来一行包含一个整数 M。 接下来 M 行，每行包含两个整数 u 和 v，代表一次操作。

**输出格式**  
对于每组数据，输出一行，包含一个整数，代表操作后树的漂亮程度。

**数据范围与子任务**  
• 1 ≤ N,M ≤ 5·10^5  
• 0 ≤ pi ≤ N −1  
• 1 ≤ u,v ≤ N

**样例数据**  
**输入**  
5  
2 0 1 3 4  
2 4  
1 2  
5 2  
1 3  
4  
2 1  
5 5  
3 4  
3 2  
**输出**  
4  
4  
3  
2

## @solution@ ##

本道题和 IOI2018 那道题的排座位其实很像。。。  
就是找一些特征值可以代表树上的一条链，然后维护一下。。。  
直接避免这些抽象的东西，我们切入正题。

先考虑给定 L，怎么判断长度为 L 的“漂亮”路径是否存在。  
一个链在有根树上有两种形态，一种由祖先连向子孙，一种形如 '^'。

对于祖先连向子孙这类形态，可以发现它有两个“特殊结点”：最上面那个，没有连向父亲的边；最下面那个，没有连向儿子的边。  
稍微思考一下就可以发现，我们如果限制没有连向儿子的边的特殊点个数为 1，则可能的形态只有一种。  
考虑维护特殊点个数。如果一个点有连向儿子的边，肯定会先选择到连 p 最小的儿子。  
于是：我们维护一个计数器 cnt = L；依次扫描 p\[i\]=0...L-1 的点，如果它的最小儿子 < L 则 cnt--。最终剩下 cnt = 1 则说明是我们想要的形态。

对于 '^' 型的链，依然还是先限制没有连向儿子的边的特殊点个数为 2。此时可能会出现三种形态：不相交的两条链、一条链、一条链然后 lca 往上延伸出了一个枝末。  
我们依次排除掉另两种情况。考虑找到一个 L' 使得存在一个点 x 使得它、它的最小儿子、它的次小儿子 < L'。假如我保证 L >= L'，则就可以排除掉第一个情况。  
考虑找到这个 x，得到它父亲的 p 值为 k。假如我保证 L < k 既可以排除掉第三个情况。

考虑怎么维护。首先开个 set 维护一个点 x 的儿子（其实更合理地应该是使用可删除任意结点的堆，但是我不会写。。。），方便我们得到一个点的最小儿子 k1，次小儿子 k2。  
维护一棵线段树表示我们的计数器，一开始线段树中位置 i 的值为 i，每个点 x 在 max(k1, p\[x\]) ~ N 中减一。  
看起来我们需要维护一个值的出现次数，但是注意到 cnt = 1/2 都是对应情况 cnt 的最小可能取值，于是维护一下最小值与最小值的出现次数即可。  
最后全局开一个 set 维护 max(k2, p\[x\]) 以及对应的 x，便于我们处理第二种情况。

交换的时候按照定义相应地改一改即可。时间复杂度 O(nlogn)。

## @accepted code@ ##

#include<set> #include<cstdio> #include<iostream> #include<algorithm> using namespace std; typedef pair<int, int> pii; const int MAXN = 500000; const int INF = (1<<30); struct edge{ edge *nxt; int to; }edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt=&edges[0]; void addedge(int u, int v) { edge *p = (++ecnt); p->to = v, p->nxt = adj[u], adj[u] = p; p = (++ecnt); p->to = u, p->nxt = adj[v], adj[v] = p; } struct segtree{ struct node{ int l, r, tg; pii mn; }t[4*MAXN + 5]; pii merge(pii a, pii b) { pii ret = make_pair(min(a.first, b.first), 0); if( a.first == ret.first ) ret.second += a.second; if( b.first == ret.first ) ret.second += b.second; return ret; } void pushup(int x) { t[x].mn = merge(t[x << 1].mn, t[x << 1 | 1].mn); } void pushdown(int x) { if( t[x].tg ) { t[x << 1].tg += t[x].tg, t[x << 1 | 1].tg += t[x].tg; t[x << 1].mn.first += t[x].tg, t[x << 1| 1].mn.first += t[x].tg; t[x].tg = 0; } } void build(int x, int l, int r) { t[x].l = l, t[x].r = r, t[x].tg = 0; if( l == r ) { t[x].mn = make_pair(l, 1); return ; } int mid = (l + r) >> 1; build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r); pushup(x); } void modify(int x, int l, int r, int d) { if( l > t[x].r || r < t[x].l ) return ; if( l <= t[x].l && t[x].r <= r ) { t[x].tg += d, t[x].mn.first += d; return ; } pushdown(x); modify(x << 1, l, r, d); modify(x << 1 | 1, l, r, d); pushup(x); } pii query(int x, int l, int r) { if( l > t[x].r || r < t[x].l ) return make_pair(INF, 0); if( l <= t[x].l && t[x].r <= r ) return t[x].mn; pushdown(x); return merge(query(x << 1, l, r), query(x << 1 | 1, l, r)); } }T; set<int>st[MAXN + 5]; set<pii>st2; int p[MAXN + 5], fa[MAXN + 5], N, M; void dfs(int x, int f) { fa[x] = f; for(edge *q=adj[x];q;q=q->nxt) { if( q->to == f ) continue; dfs(q->to, x); st[x].insert(p[q->to]); } } int f[MAXN + 5], g[MAXN + 5]; void update(int x) { set<int>::iterator it = st[x].begin(); if( it != st[x].end() ) { if( f[x] == 0 ) f[x] = max(p[x], *it), T.modify(1, f[x], N, -1); else { if( f[x] != max(p[x], *it) ) { if( f[x] < max(p[x], *it) ) T.modify(1, f[x], max(p[x], *it)-1, 1); else T.modify(1, max(p[x], *it), f[x]-1, -1); f[x] = max(p[x], *it); } } it++; if( it != st[x].end() ) { if( g[x] == 0 ) g[x] = max(p[x], *it), st2.insert(make_pair(g[x], x)); else { if( g[x] != max(p[x], *it) ) { st2.erase(make_pair(g[x], x)); g[x] = max(p[x], *it); st2.insert(make_pair(g[x], x)); } } } } } void update(int &x, pii p, int k) { if( p.first == k ) x += p.second; } int get_ans() { int ret = 0; update(ret, T.query(1, 1, N), 1); set<pii>::iterator it = st2.begin(); if( it != st2.end() ) { if( fa[it->second] ) update(ret, T.query(1, it->first, p[fa[it->second]]-1), 2); else update(ret, T.query(1, it->first, N), 2); } return ret; } int main() { scanf("%d", &N); for(int i=1;i<=N;i++) scanf("%d", &p[i]), p[i]++; for(int i=1;i<N;i++) { int u, v; scanf("%d%d", &u, &v); addedge(u, v); } dfs(1, 0); T.build(1, 1, N); for(int i=1;i<=N;i++) update(i); scanf("%d", &M); for(int i=1;i<=M;i++) { int u, v; scanf("%d%d", &u, &v); if( fa[u] ) st[fa[u]].erase(p[u]); if( fa[v] ) st[fa[v]].erase(p[v]); swap(p[u], p[v]); if( fa[u] ) st[fa[u]].insert(p[u]); if( fa[v] ) st[fa[v]].insert(p[v]); update(u), update(v); if( fa[u] ) update(fa[u]); if( fa[v] ) update(fa[v]); printf("%d\n", get_ans()); } }

## @details@ ##

事实上。。。写得不好 set 用得太多的话。。。是会被卡常的。。。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11335519.html