RikkawithStorehouse

The first line contains two integers $n,m\ (2 \leq n \leq 18, 0 \leq m \leq 2 \times 10^5)$ .
The second line contains $\lceil \frac{N}{2} \rceil$ integers $h_i\ (1 \leq h_i \leq 10^8)$ , representing $a_{\lceil \frac{N}{2} \rceil}, \dots, a_{N}$ in order, where $N = 2^n-1$ .
Then m lines follow, each line with two integers $x_i, w_i\ (\lceil \frac{N}{2} \rceil \leq x_i \leq n, 1 \leq w_i \leq 10^8)$ , representing the altitude of the $x_i$ -th storehouse is changed to $w_i$ during the i-th movement.

Output m+1 lines, each with a single number: the initial value of ans followed by the value of ans after each movement.
Writing a special judge is a tiring task. Therefore, you are required to output the answer module 998244353. Formally, if the simplest fraction representation of ans is $\frac{x}{y}$ , you need to output $x \times y^{998244351} \text{ mod } 998244353$ .

C++(clang++11) 解法, 执行用时: 684ms, 内存消耗: 10160K, 提交时间: 2020-11-29 23:00:02

#include<bits/stdc++.h>
using namespace std;
const int maxn=1<<19,mod=998244353;
int add(int x,int y){
	x+=y;return x>=mod?x-mod:x;
}
int mul(int x,int y){
	return 1ll*x*y%mod; 
}
int qpow(int x,int y){
	int ans=1;
	while(y){
		if(y&1)ans=mul(ans,x);
		x=mul(x,x),y>>=1;
	}
	return ans;
}
struct data{
	int a,b,c;
	friend data operator+(const data&x,const data&y){
		int A=add(add(x.a,y.a),1);
		int B=add(x.b,y.b);
		int C=add(x.c,y.c);
		data z;
		int i4A=qpow(mul(A,4),mod-2);
		z.a=add(1,mod-mul(4,i4A));
		z.b=mul(mul(4,B),i4A);
		z.c=add(C,mod-mul(B,mul(B,i4A)));
		return z;
	}
}tr[maxn<<2];
int n,h[maxn<<2],N,m;
int get(){
	int A=add(tr[2].a,tr[3].a);
	int B=add(tr[2].b,tr[3].b);
	int C=add(tr[2].c,tr[3].c);
	return mul(add(mul(4,mul(A,C)),mod-mul(B,B)),qpow(mul(4,A),mod-2));
}
int main(){
	cin>>n>>m;
	N=1<<n;
	for(int i=1<<n-1;i<N;i++)
	scanf("%d",&h[i]),tr[i]=(data){1,mod-add(h[i],h[i]),mul(h[i],h[i])};
	for(int i=(1<<n-1)-1;i;i--)
	tr[i]=tr[i<<1]+tr[i<<1|1];
	printf("%d\n",get());
	for(int i=1;i<=m;i++){
		int x,w;
		scanf("%d%d",&x,&w);
		h[x]=w;
		tr[x]=(data){1,mod-add(h[x],h[x]),mul(h[x],h[x])};
		x>>=1;
		while(x)tr[x]=tr[x<<1]+tr[x<<1|1],x>>=1;
		printf("%d\n",get());
	}
}

详情