Codeforces #666 Div1 D. Rainbow Rectangles

Editorialが見えなくなってる…。
https://codeforces.com/contest/1396/problem/D

問題

L*Lのグリッド中のうちNマスにキャンディーがある。
それぞれ、置かれたマスの位置と、キャンディーの色が与えられる。

このグリッドのうち矩形領域を選んだ時、全色のキャンディーが最低1個ずつは含まれるようにしたい。
矩形領域の選び方は何通りか。

解法

まず座標圧縮しておく。

下端を総当たりする。
各色のキャンディーが存在する列番号を昇順で並べた数列をCとするとき、矩形領域の左端・右端がC[i]とC[i+1]の内側にある場合は、条件を満たさないことになる。
その際、上端を徐々に下げていくことを考えよう。上端を下げるごとにそのようなCの要素が減っていく。
その結果、条件を満たさない矩形領域の左端・右端が増えていく。

そのような条件を満たさない矩形領域の左端・右端の組み合わせは、左端の値を横軸、右端の値を縦軸に置いた座標を考えると、複数の矩形の和集合で考えることができ、その組み合わせ数は和集合の面積として、Mapを使って数え上げることができる。

int N,K,L;
int X[2020],Y[2020],C[2020];
vector<pair<int,int>> ycand[2020];
const ll mo=1000000007;
vector<int> Ys;

multiset<int> Xs[2020];

class AreaRect {
public:
	map<ll,ll> M;
	ll sum;
	AreaRect() {
		M[0]=1LL<<60;
		M[1LL<<60]=0;
		sum=0;
	}
	void add(ll x,ll y) {
		auto k=M.lower_bound(x);
		if(k->second>=y) return;
		while(prev(M.lower_bound(x))->second<=y) {
			auto p=*prev(M.lower_bound(x));
			M.erase(p.first);
			sum-=(p.first-prev(M.lower_bound(p.first))->first)*(p.second-M.lower_bound(p.first)->second);
		}
		sum += (x-prev(M.lower_bound(x))->first)*(y-M.lower_bound(x)->second);
		M[x]=y;
		//cout<<"add "<<x<<" "<<y<<" "<<sum<<endl;
	}
};



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>L;
	Ys.push_back(0);
	Ys.push_back(L);
	FOR(i,N) {
		cin>>X[i]>>Y[i]>>C[i];
		Ys.push_back(Y[i]);
		C[i]--;
	}
	sort(ALL(Ys));
	Ys.erase(unique(ALL(Ys)),Ys.end());
	FOR(i,N) {
		Y[i]=lower_bound(ALL(Ys),Y[i])-Ys.begin();
		ycand[Y[i]].push_back({X[i],C[i]});
	}
	FOR(y,Ys.size()) sort(ALL(ycand[y]));
	
	ll ret=0;
	int prey=-1;
	FOR(y,Ys.size()-1) {
		AreaRect ar;
		
		FOR(i,K) Xs[i].clear(),Xs[i].insert(-1),Xs[i].insert(L);
		FOR(i,N) if(Y[i]>=y) Xs[C[i]].insert(X[i]);
		FOR(i,K) {
			int pre=0;
			FORR(x,Xs[i]) if(x>=0) {
				ar.add(L-(pre),x+1);
				pre=x+1;
			}
		}
		for(int y2=Ys.size()-2;y2>=y;y2--) {
			(ret+=1LL*(Ys[y]-prey)*(Ys[y2+1]-Ys[y2])%mo*((1LL*L*(L+1)-ar.sum)%mo))%=mo;
			FORR(c,ycand[y2]) {
				auto it=Xs[c.second].lower_bound(c.first);
				ar.add(L-(*prev(it)+1),*next(it)+1);
				
				Xs[c.second].erase(it);
			}
		}
		prey=Ys[y];
		
	}
	cout<<ret<<endl;
	
}

まとめ

解法が思いついても、割と実装がしんどい。