题解归档 - cf2228D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2228D
• 本地来源：problems/cf2228D/idea.md
• 题目链接：https://codeforces.com/contest/2228/problem/D
• 原始标题：cf2228D - Sanae, Cross and Color

思路

cf2228D - Sanae, Cross and Color

pattern: sweep a vertical threshold and count compatible horizontal thresholds.

claim: For a fixed vertical coloring, a horizontal threshold is valid iff it is at least both left/right minimum y values and smaller than both left/right maximum y values.

necessary: Each quadrant must contain a point. On the left side this means the horizontal cut must leave at least one left point below and one left point above, so lmin <= k < lmax. The right side gives rmin <= k < rmax.

sufficient: If max(lmin,rmin) <= k < min(lmax,rmax), each of left-bottom, left-top, right-bottom, right-top has at least one point by the corresponding minimum/maximum point. Distinct horizontal colorings correspond to distinct global y levels after which the cut is placed, so the count is the number of used y coordinates in [max(lmin,rmin), min(lmax,rmax)).

brute/check: brute.cpp enumerates all integer cut positions for small grids and stores the produced color strings, so duplicate thresholds are counted once. gen.cpp generates random distinct points.

edge: duplicate x groups, duplicate y groups, empty coordinate gaps, all points monotone, and cuts after first/last group.

代码

来源：problems/cf2228D/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T,n,i,j,x,y;
    cin>>T;
    while(T--){
        cin>>n;
        vector<pair<int,int>>p(n);
        vector<int>lc(n+2),rc(n+2),hy(n+2),pre(n+2);
        for(i=0;i<n;i++){
            cin>>x>>y;
            p[i]={x,y};
            rc[y]++;
            hy[y]=1;
        }
        for(i=1;i<=n;i++) pre[i]=pre[i-1]+hy[i];
        sort(p.begin(),p.end());
        int lmn=n+1,lmx=0,rmn=1,rmx=n;
        while(rmn<=n&&rc[rmn]==0) rmn++;
        while(rmx>=1&&rc[rmx]==0) rmx--;
        ll ans=0;
        for(i=0;i<n;){
            j=i;
            while(j<n&&p[j].first==p[i].first){
                y=p[j].second;
                rc[y]--;
                lc[y]++;
                lmn=min(lmn,y);
                lmx=max(lmx,y);
                j++;
            }
            while(rmn<=n&&rc[rmn]==0) rmn++;
            while(rmx>=1&&rc[rmx]==0) rmx--;
            if(j<n){
                int L=max(lmn,rmn),R=min(lmx,rmx);
                if(L<R) ans+=pre[R-1]-pre[L-1];
            }
            i=j;
        }
        cout<<ans<<"\n";
    }
    return 0;
}