THUWC2024 小C的矩阵

upd: 图挂了，但懒得补了，将就着看（upd：这看个够吧）。

---

此处提交。

交互题，有一个 $n \times m$ 的 $01$ 矩阵，你可以询问一个矩形内是否有 $1$，你需要找到 $(x,y)=1$ 且满足 $x+y$ 最大，输出最大的 $x+y$。有询问次数和询问矩形大小和的限制，其中询问矩形大小和由 $\sum \max(xr-xl+1,yr-yl+1)$ 定义。

三种数据：

• $n=m=2$，询问次数限制为 $2$，询问矩形大小和限制为 $3$。

• $n=1,m=2^{12}$，询问次数限制为 $12$，询问矩形大小和限制为 $2^{12}-1$。

• $n=m=2^{12}$，询问次数限制为 $2^{13}$，询问矩形大小限制为 $7.4 \times 10^4$。

分别考虑。

一

手玩即可，四个格依次标号 $1,2,3,4$。

• 查询 $2,4$。

  • 为 $1$ 则查询 $4$。

    • 为 $1$ 则为四号格。

    • 为 $0$ 则为二号格。

  • 为 $0$ 则查询 $3$。

    • 为 $1$ 则为三号格。

    • 为 $0$ 则为一号格。

次数为 $2$，大小为 $3$。

二

二分即可，当递归到 $[l,r]$ 时，查询 $[mid+1,r]$，若为 $1$ 则递归 $[mid+1,r]$ 否则递归 $[l,mid]$。

次数为 $12$，大小为 $2^{12}-1$。

三

$x+y$ 相等的格子形成了一条从左下到右上的线。仍然考虑二分答案。套用法一，分为 $4$ 个边长为 $2^6$ 的正方形，发现可以将答案的范围缩小一半（有三种情况），这是很好的。只需要递归解决下图的问题。

将 LR 夹着的正方形取出来（下图红色的部分）。

其中灰色的部分是没有 $1$ 的，不然不会递归到 LR。对每个红色的正方形使用法一，三种情况取最优递归下去即可。

总共递归了 $12$ 次，标号 $0,1,2,..,11$，第 $i$ 次递归中间最多有 $2^{i}$ 个正方形。总次数最多为 $2\sum_{i=0}^{11}2^i = 2^{13}-2$，总大小最多为为 $\frac{3}{2}\sum_{i=0}^{11} 2^{i} \times \frac{2^{12}}{2^{i}} = 18 \times 2^{12} = 73728$。

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

const int N=4096;

extern "C"{
    extern bool Ask(int l,int r,int u,int v);
    extern int Solve(int n,int m,int id);
}

namespace A{
    int solve(){
        if(Ask(1,2,2,2)==1) return Ask(2,2,2,2)==1?4:3;
        else return Ask(2,2,1,1)==1?3:2;
    }
}
namespace B{
    int sol(int l,int r){
        if(l==r) return l;
        int mid=l+r>>1;
        return Ask(1,1,mid+1,r)==1?sol(mid+1,r):sol(l,mid);
    }
    int solve(){
        return sol(1,N)+1;
    }
}
namespace C{
    int calc(int xl,int xr,int yl,int yr){
        int xm=xl+xr>>1,ym=yl+yr>>1;
        if(Ask(xl,xr,ym+1,yr)==1) return Ask(xm+1,xr,ym+1,yr)==1?3:2;
        else return Ask(xm+1,xr,yl,ym)==1?2:1;
    }
    int sol(int l,int r){
        if(r-l==2) return l+1;
        int res=0,mid=l+r>>1,L=r-l>>1,x,y;
        if(mid<=N) x=mid-1,y=1;
        else x=N,y=mid-N;
        for(;x-L+1>=1&&y+L-1<=N;x-=L,y+=L) res=max(res,calc(x-L+1,x,y,y+L-1));
        return res==1?sol(l,mid):res==2?sol(l+mid>>1,mid+r>>1):sol(mid,r);
    }
    int solve(){
        return sol(1,2*N+1);
    }
}


int Solve(int n , int m , int id){
    if(id==1) return A::solve();
    else if(id==2) return B::solve();
    else return C::solve();
}