算法
暴力思路显然
观察到更改操作最多只影响一条链
于是显然
代码
#include <bits/stdc++.h>
const int MAXLEN = 263000;int k;
std::string Result;int q;
int Match;
char New_Result;int pows[20] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288};int State[MAXLEN];int Left_Son[MAXLEN];
int Right_Son[MAXLEN];
int Fa[MAXLEN];
void solve1_init()
{for (int i = 1; i <= pows[k] - 2; i++){if (i % 2)Left_Son[i + pows[k - 1] - i / 2] = i, Fa[i] = i + pows[k - 1] - i / 2;elseRight_Son[i + pows[k - 1] - i / 2] = i, Fa[i] = i + pows[k - 1] - i / 2;}Fa[pows[k] - 1] = -1;for (int i = 1; i <= pows[k - 1]; i++){Left_Son[i] = -1;Right_Son[i] = -1;}for (int i = 1; i <= pows[k - 1]; i++){if (Result[i] == '0' || Result[i] == '1'){State[i] = 1;}else{State[i] = 2;}}for (int i = pows[k - 1] + 1; i <= pows[k] - 1; i++){if (Result[i] == '0'){State[i] = State[Left_Son[i]];}else if (Result[i] == '1'){State[i] = State[Right_Son[i]];}else{State[i] = State[Left_Son[i]] + State[Right_Son[i]];}}
}void solve1()
{Result[Match] = New_Result;for (int i = Match; ~i; i = Fa[i]){if(Result[i] == '0' && i > pows[k - 1]){State[i] = State[Left_Son[i]];}else if (Result[i] == '1' && i > pows[k - 1]){State[i] = State[Right_Son[i]];}else if (i > pows[k - 1]){State[i] = State[Left_Son[i]] + State[Right_Son[i]];}else{State[i] = (Result[i] == '0' || Result[i] == '1') ? 1 : 2;}}printf("%d\n", State[pows[k] - 1]);
}int main()
{//freopen("tournament.in", "r", stdin);//freopen("tournament.out", "w", stdout);scanf("%d", &k);std::cin >> Result;Result = ' ' + Result;scanf("%d", &q);solve1_init();for (int i = 1; i <= q; i++){scanf("%d", &Match);getchar();scanf("%c", &New_Result);if(q <= 100 && k <= 6)solve1();elsesolve1();}return 0;
}/*
3
0110?11
6
5 1
6 ?
7 ?
1 ?
5 ?
1 11
2
3
3
5
4
*/
总结
树型结构常见优化套路题
以前也没见过啊
