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;
}