题解 | #Contracting Convex Hull#

借用了逆十字的代码，然后加入了自己的一些理解。

#include<bits/stdc++.h>

using namespace std;

const int N=100005;

#define PII pair<int,int> 
// #define x first 
// #define y second

vector<PII> op0[N],op1[N];
int n,D,t[N<<2],tg[N<<2];

void change(int k,int l,int r,int x,int y,int v)
{
    if(x<=l&&r<=y){
        t[k]+=v;tg[k]+=v;return;//懒惰标记
    }
    int mid=(l+r)>>1;
    if(x<=mid) change(k<<1,l,mid,x,y,v);
    if(y>mid) change(k<<1|1,mid+1,r,x,y,v);
    t[k]=min(t[k<<1],t[k<<1|1])+tg[k];//+tg[k]其实就是把懒惰标记下传//更新父结点信息。
}

int ask(int k,int l,int r)
{
    if(l==r) return l;
    int mid=(l+r)/2;
//因为要找到一个结点t[k]=0。t[k]!=0;
    if(tg[k]+t[k<<1]==t[k]){
        return ask(k<<1,l,mid);
    }
    return ask(k<<1|1,mid+1,r);
}

int main()
{
    scanf("%d%d",&n,&D);
    int del=(1<<30)/D*D;
    for(int i=1;i<=n;i++){
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        x1+=del,x2+=del,y1+=del,y2+=del;
        vector<PII> _x,_y;
        if(x2-x1>=D){
            _x.push_back({0,D-1});
        }
        else if((x2-1)%D>=x1%D){
            _x.push_back({x1%D,(x2-1)%D});
        }
        else{
            _x.push_back({x1%D,D-1});
            _x.push_back({0,(x2-1)%D});
        }
                //这里后一个减一是为了防止 1-5 5-8被覆盖了两次，改成1-4，5-7就不会了。
        if(y2-y1>=D){
                        //全部覆盖
            _y.push_back({0,D-1});
        }
        else if((y2-1)%D>=y1%D){
                        //一段覆盖
            _y.push_back({y1%D,(y2-1)%D});
        }
        else{
                        //两端覆盖
            _y.push_back({y1%D,D-1});
            _y.push_back({0,(y2-1)%D});
        }
        for(auto j:_x)
            for(auto k:_y){
                                //分开op0是入边，op1是出边
                op0[j.first].push_back(k);
                op1[j.second+1].push_back(k);//这里加1是因为你取模放的时候减了1。
            }
//这里处理其实x不太重要，重要的是y，不是说重要不重要，就是偏重。
    }
    for(int i=0;i<D;i++){
                //更新覆盖区域  
                //入边。
        for(auto j:op0[i]){
            change(1,0,D-1,j.first,j.second,1);
        }
        // 出边
        for(auto j:op1[i]){
            change(1,0,D-1,j.first,j.second,-1);
        }
                //    
        if(t[1]==0){
            puts("YES");
            cout<<i<<" "<<ask(1,0,D-1)<<endl;return 0;
        }
    }
    puts("NO");
}