春季测试 2023 密码锁

\(k=1\) ：送分。

\(k=2\) ：贪心，小的在上，大的在下。

\(k=3\) ：二分答案，假定最小值在第二行，最大值在第三行，简单判断即可，用双指针，最小值在第三行，最大值在第二行的情况交换一下第一二行即可。

\(k=4\) ：仍然是二分答案，简单分讨最大最小值的相对位置，仍然用双指针，第二维用线段树维护即可。

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

const int MAXN=5e4+11;

int a[5][MAXN],N,K,mn,mx,cntk3[MAXN],ccntk3[5];

void k1(){
    int n;
    cin>>n;mx=-0x3f3f3f3f,mn=0x3f3f3f3f;
    for(int i=1; i<=n; i++){
        int x;
        cin>>x;
        mx=max(x,mx);
        mn=min(x,mn);
    }
    cout<<mx-mn<<endl;
}

void k2(){
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)cin>>a[0][i];
    for(int i=1; i<=n; i++)cin>>a[1][i];
    for(int i=1; i<=n; i++)if(a[1][i]<a[0][i])swap(a[1][i],a[0][i]);
    sort(a[1]+1,a[1]+n+1),sort(a[0]+1,a[0]+n+1);
    cout<<max(a[0][n]-a[0][1],a[1][n]-a[1][1])<<endl;
}

bool checker_k3(int mid){
    vector<pair<int,int>> allow;
    for(int i=1; i<=N; i++)for(int j=0; j<3; j++)
    if(a[(j+1)%3][i]<=mid+mn&&a[(j+2)%3][i]>=mx-mid)
        allow.push_back(make_pair(a[j][i],i));
    sort(allow.begin(),allow.end());
    for(int i=1; i<=N; i++)cntk3[i]=0;
    ccntk3[0]=N;ccntk3[1]=ccntk3[2]=ccntk3[3]=0;
    int SIZ=allow.size();
    for(int l=0,r=0; l<SIZ; l++){
        while(r<SIZ&&allow[r].first<=allow[l].first+mid){
            ccntk3[cntk3[allow[r].second]]--;
            ccntk3[++cntk3[allow[r].second]]++;
            r++;
        }
        if(ccntk3[0]==0)return 1;
        ccntk3[cntk3[allow[l].second]]--;
        ccntk3[--cntk3[allow[l].second]]++;
    }
    return 0;
}

bool true_checker_k3(int mid){
    if(checker_k3(mid))return 1;
    for(int i=1; i<=N; i++)swap(a[0][i],a[1][i]);
    if(checker_k3(mid))return 1;
    return 0;
}
void k3(){
    cin>>N;mx=-0x3f3f3f3f,mn=0x3f3f3f3f;
    for(int i=0; i<3; i++)for(int j=1; j<=N; j++){
        cin>>a[i][j];mx=max(mx,a[i][j]),mn=min(mn,a[i][j]);
    }
    int ans=mx-mn,l=0,r=ans;
    while(l<=r){
        int mid=l+r>>1;
        if(true_checker_k3(mid))ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<ans<<endl;
    return ;
}

namespace k4{
    int n;
    struct Segment{
        int Val[MAXN<<2],Tag[MAXN<<2],Lazy[MAXN<<2];
        #define lc ((k)<<(1))
        #define rc ((k)<<(1)|(1))
        #define mid ((l)+(r)>>(1))
        void up(int k){Val[k]=max(Val[lc],Val[rc]);Val[k]+=Tag[k];}
        void SET(int k){Lazy[k]=1;Val[k]=Tag[k]=0;}
        void down(int k){if(!Lazy[k])return;Lazy[k]=0;SET(lc),SET(rc);}
        void Insert(int x,int y,int v,int k,int l,int r){
            if(l>=x&&r<=y){Tag[k]+=v,Val[k]+=v;return;}
            if(l>y||x>r)return;   down(k);
            Insert(x,y,v,lc,l,mid),Insert(x,y,v,rc,mid+1,r),up(k);
        }
        #undef lc
        #undef rc
        #undef mid
    }seg;
    struct node{int x,y,id,sec;};
    vector<node>all;
    bool vis[5][MAXN];
    vector<pair<int,int>>allows[MAXN];
    inline int Get1(int x){
        int i=all[x].id;
        for(int j=all[x].sec-1;j>=0;j--)
            if(vis[j][i]){return allows[i][j].second;}
        return 0;
    }
    inline int Get2(int x){
        int i=all[x].id;
        for(int j=all[x].sec+1;j<allows[i].size();j++)
            if(vis[j][i]){return allows[i][j].second;}
        return 0x3f3f3f3f;
    }
    bool comp1(node x,node y){return x.x<y.x;}
    bool comp2(pair<int,int> x,pair<int,int> y){return x.second<y.second;}
	bool checker_k4(int mid,int pian_yi_liang,int is_reverse){
        all.clear();
        for(int i=1; i<=n; i++){
            allows[i].clear();
            for(int j=0; j<4; j++){
                int fir=j,sec=(j+1+pian_yi_liang)%4; // mn mx __ __ or mn __ mx __
                if(is_reverse)swap(fir,sec); // reverse
                if(a[fir][i]<=mid+mn&&a[sec][i]>=mx-mid) // check
                allows[i].push_back(make_pair(a[pian_yi_liang==0?(j+2)%4:(j+1)%4][i],a[(j+3)%4][i]));
            }
            if(allows[i].size()==0)return false;// 特判
            sort(allows[i].begin(),allows[i].end(),comp2);
            for(int j=0; j<allows[i].size(); j++)
            all.push_back((node){allows[i][j].first,allows[i][j].second,i,j});
        }
        for(int i=0; i<4; i++)for(int j=1; j<=n; j++)vis[i][j]=0;
        sort(all.begin(),all.end(),comp1);
        seg.SET(1);
        int SIZ=all.size();
        for(int l=0,r=0; l<SIZ; l++){
            while(r<SIZ&&all[r].x<=all[l].x+mid){
                vis[all[r].sec][all[r].id]=1;
                int PRE=Get1(r),NXT=Get2(r);
                int ChangeL=max(PRE+1,all[r].y-mid),ChangeR=min(all[r].y,NXT-mid-1);
                if(ChangeL<=ChangeR)seg.Insert(ChangeL,ChangeR,1,1,1,mx);
                r++;
            }
            if(seg.Val[1]==n)return 1;
            vis[all[l].sec][all[l].id]=0;
            int PRE=Get1(l),NXT=Get2(l);
            int ChangeL=max(PRE+1,all[l].y-mid),ChangeR=min(all[l].y,NXT-mid-1);
            if(ChangeL<=ChangeR)seg.Insert(ChangeL,ChangeR,-1,1,1,mx);
        }
        return 0;
	}
    bool true_checker_k4(int mid){
        if(checker_k4(mid,0,0)||checker_k4(mid,0,1)||checker_k4(mid,1,1))return 1;
        else return 0;
    }
    void solver(){
        scanf("%d",&n);
        mn=0x3f3f3f3f,mx=-0x3f3f3f3f;
        for(int i=0; i<4; i++)for(int j=1; j<=n; j++){
            cin>>a[i][j];
            mx=max(mx,a[i][j]),mn=min(mn,a[i][j]);
        }
        int ans=mx-mn,l=0,r=ans;
        while(l<=r){
            int mid=l+r>>1;
            if(true_checker_k4(mid))r=mid-1,ans=mid;
            else l=mid+1;
        }
        cout<<ans<<endl;
    }
}


int main(){
    int T;
    int k;
    cin>>T>>k;
    while(T--){
        if(k==1)k1();
        if(k==2)k2();
        if(k==3)k3();
        if(k==4)k4::solver();
    }
    return 0;
}