牛牛的方格图

感觉自己在降智...

一开始写c想二分,二分半天也没二分出什么...最后是枚举.

想e的时候一直想偏序,我不知道正解是啥,最后写完我的想法刚好没时间了..当然还没调qwq

介绍下自己的想法,将方格的横坐标看成是时间,然后在维护时间的一个优先队列,假如现在的时间要大于优先队列对头的时间,那么对头就要去除,然后对于横坐标进行差分,只要从1开始到i的前缀和值是正数说明这个点被遍历过.细节就是一种颜色大于1的才有贡献,贡献是横纵坐标取min...肯定没这么复杂.待会看下正解.

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e6+5;
const int M=1e3+5;

struct sb{
	int x,y;
};

bool cmp(sb A,sb B)
{
	if(A.x==B.x)	return A.y<B.y;
	else			return A.x<B.x;
}

vector<sb>col[N];
bool vis[M][M];
int a[M][M];
vector<sb>num;
struct cnm{
	int x,y,time;
	friend bool operator <(cnm A,cnm B)
	{
		if(A.time==B.time)	return A.x<B.x; 
		else				return A.time>B.time; 
	}
};

priority_queue<cnm>Q;
vector<cnm>nm[M];
int b[M];

void run()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
			col[a[i][j]].push_back({i,j});
		}
	}
	for(int i=1;i<=1e6;i++)
	{
		//sort(col[i].begin(),col[i].end(),cmp);
		int mnx=1e9,mny=1e9,mxx=0,mxy=0;
		for(auto X:col[i])
		{
			mnx=min(mnx,X.x);
			mny=min(mny,X.y);
			mxx=max(mxx,X.x);
			mxy=max(mxy,X.y);
		}
		int sz=(int)col[i].size();
		if(sz>1)
		{
			//cout<<i<<' '<<col[i][0].y<<' '<<col[i][sz-1].y+1<<'\n';
			nm[mnx].push_back({mny,mxy+1,mxx+1});
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		while(Q.size())
		{
			auto y=Q.top();
			if(y.time<=i)
			{
				b[y.x]--,b[y.y]++;
				Q.pop();
			}
			else
			{
				break;
			}
		}
		for(cnm y:nm[i])	 b[y.x]++,b[y.y]--,Q.push({y});
        //for(int j=1;j<=m;j++)    cout<<b[j]<<' ';puts("");
		int res=0;
		for(int j=1;j<=m;j++)
		{
			res+=b[j];
			if(res<=0)	ans++;
		}
	}
	cout<<ans<<'\n';
}

int main()
{
	//debug();
	int T=1;
	//scanf("%d",&T);
	while(T--)	run(); 
	return 0;
}
/*

*/