BZOJ 2738: 矩阵乘法 – [整体二分/树状数组]


题目传送门(BZOJ)
>原文链接<

题解 :

N特别小, 数点的话直接开一个二维树状数组即可.

我们可以把矩阵读入之后, 按权值排序, 这样就可以二分了.

对于一个询问(x1, y1, x2, y2, k), 二分出一个mid, 把1\sim mid这部分点都加进去, 权值为1

查询子矩形中权值和是否大于k, 若大于等于就向左走, 否则向右走.

解决了单组询问, 对于多组询问考虑整体二分.

solve(L, R, l, r)表示解决[L, R]这部分询问, 答案下标区间在[l, r]

验证上有一点不同, 若一次验证是小于k的, 我们把这部分减掉, 这样下次再验证这个询问时, 只需要加从mid+1开始的点, 具体实现的确是可以这样的,

因为某个询问往左走, 那么我们都不会减掉这次验证的答案,

若它往右走, 那么下次验证一定是从mid+1开始的

对于l = r, 把[L, R]这部分的答案都置成a[l].val即可

代码 :

#include 
#include 
#include 
#include 
using namespace std;
const int N = 510;
#define P(i, j) ((i-1)*n+j)
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)
char buf[100000], *p1, *p2;
inline int rd() {
    int x = 0; char ch = nc();
    while(!isdigit(ch)) ch = nc();
    while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc();
    return x;
}
struct POINT {
    int x, y, v;
    inline bool operator < (const POINT &A) const {
        return v < A.v;
    }
}a[N*N];
struct QUERY {
    int x1, x2, y1, y2, k, id;
}q[61000], b[61000];
int n, Q, t[N][N], ans[61000];
inline void add(int x, int y, int c) {
    for(int i = x; i <= n; i += i&-i)
    for(int j = y; j <= n; j += j&-j)
    t[i][j] += c;
}
inline int inq(int x, int y) {
    int re = 0;
    for(int i = x; i; i -= i&-i)
    for(int j = y; j; j -= j&-j)
    re += t[i][j];
    return re;
}
void solve(int L, int R, int l, int r) {
    if(L > R) return ;
    if(l == r) {
        for(int i = L; i <= R; i ++ ) ans[q[i].id] = a[l].v;
        return ;
    }
    int mid = (l+r) >> 1;
    int pl = L, pr = R;
    for(int i = l; i <= mid; i ++ ) add(a[i].x, a[i].y, 1);
    for(int i = L; i <= R; i ++ ) {
        int sum = inq(q[i].x2, q[i].y2)-
                  inq(q[i].x1-1, q[i].y2)-
                  inq(q[i].x2, q[i].y1-1)+
                  inq(q[i].x1-1, q[i].y1-1);
        if(sum >= q[i].k) b[pl++] = q[i];
        else q[i].k -= sum, b[pr--] = q[i];
    }
    for(int i = L; i <= R; i ++ ) q[i] = b[i];
    for(int i = l; i <= mid; i ++ ) add(a[i].x, a[i].y, -1);
    solve(L, pr, l, mid), solve(pl, R, mid+1, r);
}
int main() {
    n = rd(), Q = rd();
    for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= n; j ++ ) {
        a[P(i, j)].v = rd();
        a[P(i, j)].x = i;
        a[P(i, j)].y = j;
    }
    sort(a+1, a+n*n+1);
    for(int i = 1; i <= Q; i ++ ) {
        q[i].x1 = rd(), q[i].y1 = rd(), 
        q[i].x2 = rd(), q[i].y2 = rd();
        q[i].k = rd(), q[i].id = i;
    }
    solve(1, Q, 1, n*n);
    for(int i = 1; i <= Q; i ++ ) printf("%d\n", ans[i]);

}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注