CF补题大作战#2

碎碎念

直接1A一道edu的E，有点开心

CF1716E Swap and Maximum Block

给你一个长度为2^n数组，询问每次操作后该数组的最大子段和

每次操作会令i从1到n-2^x，交换i与i+2^x，同时每个数只被交换一次

solution

容易想到的一件事是我们可以用线段树来维护区间最大子段和

而我们的操作在线段树上的意义就是交换某一层的所有左右子树

所以两次相同操作会抵消，那么我们就可以预处理出所有2^n种交换方案的答案

由于在上层的操作并不会影响下层，所以第i层的空间复杂度为2^(i-1)*2^(n-i+1)=2^n

线段树一共n+1层，计算一个节点的复杂度是O(1)，所以总复杂度是(n+1)*2^n

#include<bits/stdc++.h>
#define N 1100000
#define pb push_back
#define ll long long
using namespace std;
struct node{ll l,r,sum,ans;};
vector<node>tr[N];
#define ls (nw<<1)
#define rs (ls+1)
#define mid (l+r>>1)
void build(int nw,int l,int r,int d)
{
	if(l==r)
	{
		int x;
		cin >> x;
		int y=max(x,0);
		tr[nw].pb({y,y,x,y});
		return;
	}
	build(ls,l,mid,d-1);
	build(rs,mid+1,r,d-1);
	for(int i=0;i<(1<<d);i++)
	{
		if(i<(1<<(d-1)))
		{
			node x,sl=tr[ls][i],sr=tr[rs][i];
			x.l=max(sl.l,sl.sum+sr.l);
			x.r=max(sr.r,sr.sum+sl.r);
			x.ans=max(max(sl.ans,sr.ans),sl.r+sr.l);
			x.sum=sl.sum+sr.sum;
			tr[nw].pb(x);
		}
		else
		{
			node x,sl=tr[rs][i-(1<<(d-1))],sr=tr[ls][i-(1<<(d-1))];
			x.l=max(sl.l,sl.sum+sr.l);
			x.r=max(sr.r,sr.sum+sl.r);
			x.ans=max(max(sl.ans,sr.ans),sl.r+sr.l);
			x.sum=sl.sum+sr.sum;
			tr[nw].pb(x);
		}
	}
}
int n,q;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin >> n;
	build(1,1,1<<n,n);
	cin >> q;
	int opt=0;
	while(q--)
	{
		int x;
		cin >> x;
		opt^=(1<<x);
		cout << tr[1][opt].ans << endl;
	}
	return 0;
}