题意
给出n*n的矩阵，ai,j∈[1,n*n]，现在要矩形覆盖若干次，每次把一个正方形的ai,j改为x，求最少的次数使得最后有k种不同的数
n<=500
题解
设sum为初始不同的数，若sum<k则显然只能一个个加，ans=k-sum
若sum>k，则有结论：ans<=2
证明：可以从(1,1)开始往右下扩展新颜色的矩形1，直到最后一次sum>k为止，右下角为(x,x)
然后从(x+1,x+1)向左上扩展矩形2，颜色和矩形1相同
设此时的种数为s，若把颜色均改为和之前出现的则为s-1，若把矩形2改成不同颜色的则为s+1
故可以取到[s-1,s+1]
因为每次扩展时s最多减2，故从>s跳到<s的过程中一定会经过[s-1,s+1]，则必定有解
现在问题是怎么判断ans=1，3.5s+256MB
假设当前确定了一个矩形，则将其向左上或右下扩展影响不大
所以按斜线y-x=k来处理，把每种颜色所在的极大矩形提出，找到端点在斜线y-x=k上的极小正方形，则所有包含这个正方形的都可以除掉一种颜色
用f[i,j]记当前斜线，覆盖左上i号点右下j号点后除掉的颜色，二维前缀和解决
时间是斜线数n*(颜色数n^2+前缀和n^2)，即O(n^3)
标签：CF1720E,颜色,Paintings,斜线,sum,Misha,正方形,左上,矩形 From： https://www.cnblogs.com/gmh77/p/16648132.html