人生中第一个AC的codeforces题，大概
太难了，光是看答案就看了整整一下午，最后还是在b站上搜到讲解视频才明白的。俺们阿B真的是太厉害啦
这道题首先容易看出当矩阵中数字个数小于或等于所需要的个数时，直接输出他们的差即可。剩下的就是判断大于的情况。
这种情况的处理方法还多亏了大佬室友。像是个脑筋急转弯。但对我来说显然不是 可以证明在这种情况下，操作数至多为2，不是2就是1。证明方法是构造，总算知道tag里的构造算法是怎么回事了 首先从左上角开始往右下角画正方形，在正方形里填上同一种数字（颜色），直到整个方阵里的颜色种类恰好多余要求种类数，正方形再大一点就删过了。之后从这个正方形的右下的元素开始向左上方扩展正方形，由于和原来正方形重叠的部分已经被删过了，所以新的正方形每扩大一点，删除的颜色就会多2。也就是说用这样的删法，最终的颜色种类数与所要求的数字最多只会相差1，而这个1是可以通过恰当选择填充的颜色来避免的。这也就证明了操作数最多两步。
问题进而转化为能否一步完成。这个问题可以在n3解决。方法是先预处理数据，记录每种颜色在矩阵中最左上的坐标和最右下的坐标，框出一个矩形。然后枚举正方形的边长，从1到n。对于每一个边长，枚举每种颜色，根据颜色的边界坐标确定正方形要想框住所有的这种颜色，左上角定点所能在的范围，是一个矩形。只要所选的正方形的左上角顶点位于这个范围内，就能删除一种颜色。具体而言，一种颜色的左上角确定了正方形的右下界，颜色的右下角确定了正方形的左上界。下一步是根据正方形的界做标记。这里不能对这个矩形范围内的所有元素进行修改，因为这是n2的复杂度。这里应该用二维懒标记(2D lazy update)或者说二维差分。在范围的左上角加一，在右上角右边减一，在左下角下边减一，在右下角的右下加一。之后用计算前缀和的方法还原更新后的整个方阵。计算二维前缀和的方法是先扫描每一行，元素值为其行前缀和，再以此类推扫描每一列。还原后再用n^2时间扫描整个方阵，如果有一个元素满足n-k（颜色选择剩余部分已有的颜色）或者n-k+1（颜色选择不存在的颜色），则说明可以用一步完成，否则就只能两步完成了。
代码：
#include <iostream>
using namespace std;
bool m[250005];
struct color{
int r_min = 501, r_max = -1, c_min = 501, c_max = -1;
} map[250005];
int main(){
int n, k;
cin >> n >> k;
int cat = 0;
for(int i = 0; i<n; ++i){
for(int j = 0; j<n; ++j){
int x;
cin >> x;
if(!m[x]){
m[x] = 1;
++cat;
}
if(i<map[x].r_min)
map[x].r_min = i;
if(i>map[x].r_max)
map[x].r_max = i;
if(j<map[x].c_min)
map[x].c_min = j;
if(j>map[x].c_max)
map[x].c_max = j;
}
}
if(cat<=k){
cout << k-cat;
return 0;
}
else{
for(int i = 1; i<=n; ++i){
int tmp[501][501] = {0};
for(int j = 1; j<250005; ++j){
if(m[j]&&map[j].r_max-map[j].r_min+1<=i&&map[j].c_max-map[j].c_min+1<=i){
int ul_r = (map[j].r_max-i+1<0?0:map[j].r_max-i+1);
int ul_c = (map[j].c_max-i+1<0?0:map[j].c_max-i+1);
int br_r = map[j].r_min+1;
int br_c = map[j].c_min+1;
tmp[ul_r][ul_c]++;
tmp[ul_r][br_c]--;
tmp[br_r][ul_c]--;
tmp[br_r][br_c]++;
}
}
for(int j = 0; j<=n-i; ++j){
int sum = 0;
for(int t = 0; t<=n-i; ++t){
sum+=tmp[j][t];
tmp[j][t] = sum;
}
}
for(int j = 0; j<=n-i; ++j){
int sum = 0;
for(int t = 0; t<=n-i; ++t){
sum+=tmp[t][j];
tmp[t][j] = sum;
if(sum==cat-k||sum==cat-k+1){
cout << 1;
return 0;
}
}
}
}
}
cout << 2;
return 0;
}