$305$ $pits$

T3 回文树

solution

1. 用 $dfs$ $($ 记忆化搜索 $)$ 来预处理每个子树分别有多少个不同的字符 , 状态转移方程如下 ：

   $dp_{i,c} = dp_{2i,c} + dp_{2i + 1,c} +$ $($根节点是否为字符 $c)$ $c$ 为当前搜索的字符

2. 用一个 $check$ 函数来判断子树是否为回文 ， 具体的：

   如果串的长度为奇数，且只有一个字符的数量为奇数，为回文串

   如果串的长度为偶数，且字符的数量都为偶数，为回文串

3. 先预处理出答案，对于每一个修改，注意到修改节点只会对当前节点及节点父亲产生影响，所以只需修改被影响的节点即可，注意只当修改后的节点回文与原来不同时才会对 $ans$ 有影响

时间复杂度：$O(qlg{n} + n)$

code

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 5;

int n, q, w[N][30], flag[N], ans;
string s;

int dfs(int t, int color) {
	if(t > n) return 0;
	if(w[t][color]) return w[t][color];
	return w[t][color] = dfs(2 * t, color) + dfs(2 * t + 1, color) + ((s[t] - 'a' + 1) == color);
}

bool check(int t) {
	int sum = 0, k2 = 0;
	for(int i = 1 ; i <= 26 ; i ++) {
		sum += w[t][i];
		if(w[t][i] % 2 == 1) k2 ++;
	}
	if(sum == 1) return true;
	if(sum % 2 == 0 && k2 == 0) return true;
	if(sum % 2 == 1 && k2 == 1) return true;
	return false;
}

void solve(int t, char ch) {
	int p = t;
	vector<int> v;
	while(p > 0) {
		w[p][s[t] - 'a' + 1] --;
		w[p][ch - 'a' + 1] ++;

		v.push_back(p);
		p /= 2;
	}
	for(int i = 0 ; i < v.size() ; i ++) {
		int f = check(v[i]);
		if(f && !flag[v[i]]) ans ++, flag[v[i]] = true;
		if(!f && flag[v[i]]) ans --, flag[v[i]] = false;
	}
	s[t] = ch;
	cout << ans << endl;
}

signed main() {
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);

	cin >> n >> q >> s;

	s = " " + s;
	for(int i = 1 ; i <= 26 ; i ++) dfs(1, i);

	for(int i = 1 ; i <= n ; i ++) {
		if(check(i)) ans ++, flag[i] = true;
	}
	cout << ans << endl;
	while(q --) {
		int x;
		char ch;
		cin >> x >> ch;
		solve(x, ch);
	}
	return 0;
}

T4 构造题

solution

由题目，顺序对和逆序对的数量相等，因为在一个序列中数对数量为 $n * (n - 1) / 2$ 所以顺序对和逆序对的数量为 $n * (n - 1) / 4$

只需先按顺序排 $(1 , k)$ 满足 $(2n - 1 - k) * k <= (n - k) * (n - k - 1)$ 的 $k$ 最大，记 $f$ 为顺序对和逆序对的差，交换 $f / 2$ 的位置即可

code

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 5;

int n , a[N];

signed main(){
	freopen("gz.in" , "r" , stdin);
	freopen("gz.out" , "w" , stdout);
	
	cin >> n;
	
	int l = 1 , r = n , rsum = (n - 1) * n / 4 , lsum = 0;
	
	for(int i = 1 ; i <= n ; i ++){
		lsum = (n - i) * (n - i - 1) / 2;
		if(lsum >= rsum) a[l ++] = i;
		else a[r --] = i , rsum -= (r - l + 1);
	}
	for(int i = 1 ; i <= n ; i ++) cout << a[i] << " ";
	return 0;
}