BZOJ2738 矩阵乘法

题目

给你一个N*N的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第K小数。

思路

整体二分。

整体二分主要适用于对于二分状态的改变，可以在可接受的复杂度内修改的题目。

就本题而言，二分答案，如果考虑将[1,mid]的区间内的点加入树状数组中，在二维平面上标记为1，然后比较每个询问与K的关系，接着将询问分组，接着二分。

以上应该是整体二分的基本模型。

代码

#include
#define M 60005
using namespace std;
struct node{
    int x,y,val;
    bool operator < (const node& res)const{
        return valr)return;
    if(ql==qr){
        for(int i=l;i<=r;i++)ans[id[i]]=ql;
        return;
    }
    int mid=(ql+qr)>>1,c1=0,c2=0,c=l-1;
    while(nowmid)update(now--,-1);
    for(int i=l;i<=r;i++){
        if(query(wk[id[i]].x1,wk[id[i]].y1,wk[id[i]].x2,wk[id[i]].y2)>1;
                if(B[mid].val>=A[i][j]){
                    res=mid;
                    r=mid-1;
                }
                else l=mid+1;
            }
            A[i][j]=res;
        }
    for(int i=1;i<=Q;i++){
        scanf("%d%d%d%d%d",&wk[i].x1,&wk[i].y1,&wk[i].x2,&wk[i].y2,&wk[i].k);
        id[i]=i;
    }
    solve(1,Q,1,bcnt);
    for(int i=1;i<=Q;i++){
        printf("%d\n",B[ans[i]].val);
    }
    return 0;
}