[洛谷 5665][CSP-S2019]划分

题目链接

https://www.luogu.com.cn/problem/P5665

题解

36 分的做法比较显然：我们设 \(s_i\) 为前缀和，\(f(i,j)\) 代表前 \(i\) 个数，上一段的末尾为 \(j\) 时的最小值。

转移方程为：

$$f(i,j)=\min f(j,k)+(s_i-s_j)^2$$

正解是怎样的呢？我们首先有两个引理：

1. 所有合法的划分方案中，最优解的段数是最少的。
2. 在 \(1\) 的前提下，设最优解分为 \(k\) 段，最优解的每段末尾的下标分别为 \(s_1,s_2,\ldots ,s_k\)，一个合法解的每段末尾的下标分别为 \(t_1,t_2,\ldots ,t_k\)，则 \(\forall i \in [1,k]\)，都有 \(s_i \geq t_i\)。

证明可以看 myy 的题解（感性理解似乎也不是很难）。

这样我们就可以用单调队列在 \(O(n)\) 的时间内求出所有断点了。

---

如果不考虑高精度的部分，我们已经拿到了 88 分。

幸运的是，本题只有答案部分要用到高精度：\(s_i\) 足够用 64 位整数存储，从而最终答案在 128 位整数的存储范围之内。

NOI Linux 是 32 位机，__int128 并不能用。考场上一种简单的高精度实现是类似压位高精度的做法——用两个 long long 组合起到 128 位整数的作用。

（当然各大 OJ 基本都是 64 位机，就可以为所欲为了）

另外，本题对内存限制较紧，因此 int 足够存下的数据就别开 long long 了。

#include <iostream>
#define MAXN 40000005
#define MOD 1073741824
using namespace std;
long long s[MAXN];
int n,op,a[MAXN],b[MAXN],p[MAXN],q[MAXN];
void geninput()
{
 if(!op)
 {
  for(int i=1;i<=n;i++)
   cin>>a[i];
 }
 else
 {
  long long x,y,z,m;
  cin>>x>>y>>z>>b[1]>>b[2]>>m;
  for(int i=3;i<=n;i++)
   b[i]=(x*b[i-1]+y*b[i-2]+z)%MOD;
  int lp=0;
  while(m--)
  {
   int p,l,r;
   cin>>p>>l>>r;
   for(int i=lp+1;i<=p;i++)
    a[i]=(b[i]%(r-l+1))+l;
   lp=p;
  }
 }
}
long long f(int x)
{
 return 2*s[x]-s[p[x]];
}
void print(__int128 x)
{
 if(x<10)cout<<(int)x;
 else
 {
  print(x/10);
  cout<<int(x%10);
 }
}
int main()
{
 ios::sync_with_stdio(false);
 cin>>n>>op;
 geninput();
 for(int i=1;i<=n;i++)
  s[i]=s[i-1]+a[i];
 int l=0,r=0;
 for(int i=1;i<=n;i++)
 {
  while(l<r&&f(q[l+1])<=s[i])
   l++;
  p[i]=q[l];
  while(l<=r&&f(q[r])>=f(i))
   r--;
  q[++r]=i;
 }
 __int128 ans=0;
 for(int i=n;i;i=p[i])
  ans+=(__int128)(s[i]-s[p[i]])*(s[i]-s[p[i]]);
 print(ans);
 return 0;
}