CF354D Transferring Pyramid 题解

题意：

cxy 正在使用一个有趣的数据结构——金字塔。

金字塔由 \(n\) 行组成，其中第 \(i\) 行有 \(i\) 个格子组成。每一行的最左端相对于上一行左移了半个格子的宽度，金字塔上的格子由 \(1\) 到 \(\binom {n+1}{2}\)，从上至下，从左至右的编号。

下图是一个 \(n = 5\) 的例子：

这个神奇的数据结构能接受下列两种操作：

改变一个特定位置上的值。它需要用 \(3\) 个数作为指令：1 i v。其中 \(i\) 为格子的编号，\(v\) 为改变后的值。

改变一个子金字塔的值。上图蓝色部分显示的是以 \(5\) 号格子为顶的子金字塔，它需要用 \(s + 2\) 个数作为指令：2 i v1 v2 ... vs，其中 \(i\) 为子金字塔顶的格子的编号，\(s\) 为子金字塔的大小 (如上图中是 \(6\))，\(v_i\) 为对应修改后的值。(可以不改变，即 \(v_i\) 为之前的值)

正式地，一个以 \(i\) 行 \(j\) 列为顶的子金字塔会包含行 \(i \sim n\)，其中第 \((i + p)\) 行包含格子 \(j \sim (j + p)\quad(0 \leq p \leq n - i)\)。

现在有两个金字塔，金字塔 \(A\) 的 \(k\) 个格子已经有非 \(0\) 的数，而金字塔 \(B\) 的所有格子都是 \(0\)。cxy 需要寻找一个操作序列，使得当它施加在 \(B\) 上后，能使 \(B\) 中的所有格子与 \(A\) 中的对应格子均相等。

在她的计算机中，执行一条指令的时钟周期数等于该操作序列的长度。因此，在众多合法操作序列中，她希望找到一条长度最短的操作序列（时钟周期最短的），请你帮她求出操作序列的长度的最小可能值。

输入格式

第一行包含两个正整数 \(n, k\) \((n, k \leq 10^5)\) ，分别表示金字塔的行数与非 \(0\) 数的个数。

接下来的 \(k\) 行，每行包含两个正整数，第 \(i + 1\) 行的整数 \(r_i, c_i (1 \leq c_i \leq r_i \leq n)\) 描述其中一个非 \(0\) 数所在的格子的行数和列数，保证同一个格子不会被描述超过一遍。

输出格式

输出一行一个整数，表示操作序列的长度的最小可能值。

首先我们先把它转成方便维护的形式

容易发现，原来的 \(r_i,c_i\) 对应的 \(x_i,y_i\) 满足 \[ \begin{aligned} &x_i = n - r_i + c_i \\&y_i = n -r_i + 1 \end{aligned} \] 同时可以发现，原来的赋值就变成了一个类似直角三角形的赋值

设 \(f_{i,j}(0 \le j \le i \le n)\) 表示正准备使用操作2粉刷第 \(i\) 列高度为 \(j\) 的金字塔，它上面类似梯形的区域的最小花费

例如下图中的黄色部分，就是当前准备使用操作2粉刷的金字塔

而上面的蓝色部分就是 \(f_{i,j}\)

则最终答案就是 \(f_{n,0}\) 。

记第 \(i\) 列高度（\(y\) 坐标）大于等于 \(j\) 的 \(i-j+1\) 个格子中，有 \(s_{i,j}\) 个非 \(0\) 格，则 \[ f_{i,0} = \min \left\{ f_{i-1,0} + 3s_{i,1}, \min_{1 \le k \le i} \left\{ f_{i-1,k-1} + \left(\dfrac{1}{2}k^2 + \dfrac{1}{2}k + 2\right) + 3_{i,k+1} \right\} \right\} \] 注意：这里是 \(f_{i,0}\) ，因为这个状态比较麻烦，单独提出来讲。

yhx巨佬太强了¹，~~其实这个方程并不是那么显然就能推出来的（~~

因为时间有限，这里就不画图说明了，仅作描述

\(f_{i-1,0} + 3s_{i,1}\) 表示「 \(1\) 到 \(i-1\) 构成的完整三角形的花费」加上「填涂大于等于 \(j\) 的 \(i-j+1\) 个格子的花费」
\(\min\limits_{1 \le k \le i}\)是枚举从 \(i-1\) 的哪个地方转移，这个比较好懂吧（
先解释后面的 \(3_{i,k+1}\) ，这个指的是 \(i\) 上面的那 \(i-j+1\) 个格子的花费
\(\left(\dfrac{1}{2}k^2 + \dfrac{1}{2}k + 2\right)\) 比较麻烦，建议画一画图（~~我时间有限，对不住了~~

这个指的是除了 \(f_{i-1,k-1}\) 和 \(i\) 上面那一段，剩下的一个小三角形的花费，其实原来的柿子是 \(\frac{k(k+1)}{2} + 2\) 。

终于解释完了 \(j=0\) 的情况。

对于 \(j \ge 1\) 的情况，有 \[ f_{i,j} = \min \left\{ f_{i,j-1},~f_{i-1,j-1}+3s_{i,j+1} \right\} \] 这个就很显然了，不解释了。

说了半天，这还只是一个 \(O(n^2)\) 的暴力

考虑继续优化，当然这需要善于观察性质。

注意到其实很多时候粉刷整个大三角形是很浪费的

全部单点修改的花费也只有 \(3k\)

因此我们可以发现，判断一个三角形是否有必要粉刷

或者具体地， \(f_{i,j}\) 在 \(j\) 大于某个边界时，没有必要转移了，一定是不优的

高度为 \(h\) 的三角形，粉刷所需的花费为 \(\dfrac{1}{2}h^2 + \dfrac{1}{2}h + 2\)

则有不等式，\(\dfrac{1}{2}h^2 + \dfrac{1}{2}h + 2 > 3k\) ，即 \(h < O(\sqrt{6k})\)

因此第二维只要枚举到 \(O(\sqrt{6k})\) 就好了

时间复杂度 \(O(n \sqrt{k})\) ，然后 \(f_{i,j}\) 滚动一下就能过了

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
// #define INF 0x3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N ((int)(1e5+15))
#define H ((int)(888))
#define F first
#define S second

pair<int,int> p[N];
int n,k,h;
int f[2][N],s[N],pre,now;
void down(int &x,int y){ x = (x > y) ? y : x;}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n); read(k);
    h=min(n,(int)sqrt(6*k));
    for(int i=1,r,c; i<=k; i++)
    {
        read(r); read(c);
        p[i]={n-r+c,n-r+1};
    }
    sort(p+1,p+1+k); memset(f,0x3f,sizeof(f));
    int x=1,y; f[0][0]=0;
    for(int i=1; i<=n; i++)
    {
        y = min(i,h); now = i & 1; pre = now ^ 1;
        for(int i=0; i<=y+1; i++) f[now][i]=INF,s[i]=0;
        for(; x<=k && p[x].F==i; x++) ++s[p[x].S > y ? y+1 : p[x].S];
        for(int j=y; j>=0; j--) s[j] += s[j+1];
        f[now][0] = f[pre][0] + s[1] * 3;
        for(int j=1; j<=y; j++)
            down(f[now][0], f[pre][j-1] + ((j*(j+1)>>1) + 2 + s[j+1]*3));
        for(int j=1; j<=y; j++)
            f[now][j]=f[now][j-1],down(f[now][j], f[pre][j-1] + s[j+1]*3);
    }
    write(f[n&1][0]); pc('\n');
    return 0;
}