CF878E Numbers on the blackboard

一、题目

点此看题

二、解法

\(3300\) 的题啊，就差临门一脚了 \(...\)

直接做有点难，我们观察操作结构设计图论模型，因为这是相邻两个数配对的问题，那么如果两个数配对我们新建一个点表示它们配对后的数，然后把它们和新点连一条边，发现最后是一颗二叉树的结构。

定义某点的深度为从根到它向右走的次数，不难发现每个叶子的贡献是 \(2^{dep_i}\cdot a_i\)，问题是最大化贡献。

区间 \(dp\) 没有前途，可以先设计一个朴素 \(dp\)，设 \(dp[i][x]\) 表示第 \(i\) 个点的深度是 \(x\) 剩下的最大数：

\[dp[i][x]=dp[i-1][x-1]+2^x\cdot a_i,x>1 \]

\[dp[i][1]=\max (dp[i-1][y])+2\cdot a_i \]

初始化 \(dp[1][0]=a_1\)，这个 \(dp\) 可以很显然的降维，设 \(dp[i]\) 表示前 \(i\) 个点剩下的最大数：

\[dp[i]=\sum_{j=1}^{i-1}dp[j]+cal(j+1,i) \]

其中 \(cal(l,r)=\sum_{i=1}^{r-l+1}a_{i+l-1}\cdot 2^{i}\)，其实熟练的选手可以直接设计这个一维 \(dp\)，因为他的本质是枚举最后一段"链"，所以可以考虑所有情况。

但是本题有一个极其特殊的地方：答案对1e9+7取模，翻译一下就是不允许你使用取 \(\max\) 之类的操作，那么自然就不能 \(dp\) 了。我们考虑 \(dp\) 转贪心，它的主要思路是考虑转移点的性质然后直接取转移点。

考虑已经得到了 \(dp[i-1]\) 的转移点集合 \(s\)，考虑如果 \(a_i\) 是负数那么往 \(s\) 里面添加转移点 \(i\)，否则把 \(i\) 合并到前一个转移段是最优的，并且我们发现如果 \(i\) 的转移段权值为正，那么就可以直接往前合并。

简单的证明一下：不难发现这样操作是当前最优的，我们考虑这样操作有没有后效性，由于合并的条件是条件是当前转移段权值为正，那么无论当前的合并怎样都不会影响后面的合并的。

但是这道题还要我们解决区间问题（[OID脏话]），可以套路地离线，然后固定右端点，维护每一个左端点的答案，用并查集维护转移段，再维护转移段的权值前缀和。不难发现第一个转移段可能取不满，但是这并不会对合并造成影响，所以段还是以前的那些段，那么可以直接计算权值。

注意因为 \(dp\) 初始化的原因第一段的权值是要除以二的，因为第一个元素一开始直接作为根。

三、总结

其实 \(dp\) 转贪心能算做优化 \(dp\) 的方法，考虑转移点的性质即可。

四、后记

我把这道题出成模拟赛之后又多了很多新鲜做法，我把它们尽可能记录下来：

从二叉树的结构考虑，我们把"深度"修改成真正的深度，也就是把左儿子合并到根上，那么深度的定义就是树上的深度了，举个例子：

这棵多叉树的先序遍历就是原序列，考虑先前存在的任意一种树形结构，加入 \(i\) 点，如果 \(a_i\) 权值为正那么直接接到最后遍历到的节点上，获得最大的系数，并且和上一个点绑定。如果 \(a_i\) 权值为负那么直接接到根上，获得 \(2\) 的系数，通过上述分析我们也获得了关于转移段的结论。

#include 
#include 
using namespace std;
const int MOD = 1e9+7;
const int M = 100005;
#define int long long
const int inf = 2e9;
int read()
{
	int x=0,flag=1;char c;
	while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
	while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*flag;
}
int n,m,a[M],ans[M],pr[M],sf[M],fa[M],f[M],l[M],pw[M];
struct node
{
	int x,id;
};vector q[M];
int find(int x)
{
	if(x!=fa[x]) fa[x]=find(fa[x]);
	return fa[x];
}
void merge(int x,int y)
{
	if(l[x]>31 || f[x]+(f[y]<inf) f[x]=inf;
	else f[x]+=f[y]<=1;i--)
		sf[i]=(sf[i+1]*2+a[i])%MOD;
	for(int i=1;i<=m;i++)
	{
		int l=read(),r=read();
		q[r].push_back(node{l,i});
	}
	for(int i=1;i<=n;i++)
	{
		int x=find(i);
		while(find(x-1) && f[x]>0)
			merge(find(x-1),x),x=find(i);
		pr[x]=(pr[find(x-1)]+f[x])%MOD;
		for(auto t:q[i])
		{
			ans[t.id]=(pr[x]-pr[find(t.x)])*2
			+cal(t.x,find(t.x)+l[find(t.x)]-1);
			ans[t.id]=(ans[t.id]%MOD+MOD)%MOD;
		}
	}
	for(int i=1;i<=m;i++)
		printf("%lld\n",ans[i]);
}