P1527 [国家集训队] 矩阵乘法

题意

给定一个矩阵，每次询问子矩阵的第 \(k\) 大。

Sol

考虑把莫队扔到二维上来做。

发现复杂度变为：\(O(n ^ 2 q ^ {\frac {3}{4}})\)。

卡卡常就过了。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <cmath>
#include <vector>
#include <cassert>
#define il inline
#define rg register
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
int read() {
    int p = 0, flg = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') flg = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        p = p * 10 + c - '0';
        c = getchar();
    }
    return p * flg;
}
void write(int x) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    if (x > 9) {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}

const int N = 505, M = 2.5e5 + 5;
array <array <int, N>, N> mp;

namespace Cpt {

short bsi = 11;

array <short, M> agc;

class Node {

public:
    short l1, r1, l2, r2;
    int k, id;

    Node () : l1(), r1(), l2(), r2(), k(), id() {}

    Node (short _l1, short _l2, short _r1, short _r2, int _k, int _id) {
        l1 = _l1, r1 = _r1, l2 = _l2, r2 = _r2, k = _k, id = _id;
    }

    il bool operator <(const Node &t) const {
        if (agc[l1] != agc[t.l1]) return l1 < t.l1;
        if (agc[l2] != agc[t.l2]) return (agc[l1]) & 1 ? l2 < t.l2 : l2 > t.l2;
        if (agc[r2] != agc[t.r2]) return (agc[l2]) & 1 ? r2 < t.r2 : r2 > t.r2;
        else return (agc[r2]) & 1 ? r1 < t.r1 : r1 > t.r1;
        // if (l1 / bsi != t.l1 / bsi) return l1 < t.l1;
        // if (r1 / bsi != t.r1 / bsi) return (l1 / bsi) & 1 ? r1 < t.r1 : r1 > t.r1;
        // if (r2 / bsi != t.r2 / bsi) return (r1 / bsi) & 1 ? r2 < t.r2 : r2 > t.r2;
        // else return (r2 / bsi) & 1 ? l2 < t.l2 : l2 > t.l2;
    }

};

array <Node, M> edge;

namespace Blk {

short bsi = 610;

array <int, M> cur;
array <int, N> bk;

array <int, M> arc;

il int calc(int x) {
    return (x - 1) / bsi + 1;
}

il void modify(int x, short y) { cur[x] += y, bk[arc[x]] += y; }

il int query(int k) {
    rg short tot = 0;
    for (rg short i = 1; i <= 500; i++) {
        if (k - bk[i] <= 0) {
            tot = i;
            break;
        }
        k -= bk[i];
    }
    rg int ans = 0;
    for (rg int i = (tot - 1) * bsi + 1; i <= min(tot * bsi, (int)2.5e5); i++) {
        k -= (int)cur[i];
        if (k <= 0) {
            ans = i;
            break;
        }
    }
    // assert(ans >= 0);
    return ans;
}

}

il void modify(short x1, short x2, short y1, short y2, short k) {
    for (rg short i = x1; i <= x2; i++)
        for (rg short j = y1; j <= y2; j++)
            Blk::modify(mp[i][j], k);
}

}

vector <int> isl;
array <int, M> ans;

int main() {
    rg int n = read(), m = read();
    Cpt::bsi = n / pow(m, 0.25) / 3 + 1;
    Cpt::Blk::bsi = n + 1;
    for (short i = 1; i <= n; i++) Cpt::agc[i] = (i - 1) / Cpt::bsi + 1;
    for (int i = 1; i <= n * n; i++) Cpt::Blk::arc[i] = (i - 1) / Cpt::Blk::bsi + 1;
    for (rg short i = 1; i <= n; i++)
        for (rg short j = 1; j <= n; j++)
            mp[i][j] = read(), isl.push_back(mp[i][j]);
    sort(isl.begin(), isl.end());
    isl.erase(unique(isl.begin(), isl.end()), isl.end());
    for (rg short i = 1; i <= n; i++)
        for (rg short j = 1; j <= n; j++)
            mp[i][j] = lower_bound(isl.begin(), isl.end(), mp[i][j]) - isl.begin() + 1;
    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= n; j++)
    //         write(mp[i][j]), putchar(32);
    //     puts("");
    // }
    for (rg int i = 1; i <= m; i++) {
        rg short x1 = read(), y1 = read(), x2 = read(), y2 = read();
        rg int k = read();
        Cpt::edge[i] = Cpt::Node(x1, y1, x2, y2, k, i);
    }
    sort(Cpt::edge.begin() + 1, Cpt::edge.begin() + 1 + m);
    rg short l1 = 1, l2 = 1, r1 = 1, r2 = 1; Cpt::Blk::cur[mp[1][1]]++, Cpt::Blk::bk[Cpt::Blk::calc(mp[1][1])]++;
    for (int i = 1; i <= m; i++) {
        rg short x1 = Cpt::edge[i].l1, x2 = Cpt::edge[i].l2,
                y1 = Cpt::edge[i].r1, y2 = Cpt::edge[i].r2;
        // write(x1), putchar(32);
        // write(y1), puts("@");
        while (l1 > x1) l1--, Cpt::modify(l1, l1, l2, r2, 1);
        while (l2 > x2) l2--, Cpt::modify(l1, r1, l2, l2, 1);
        while (r1 < y1) r1++, Cpt::modify(r1, r1, l2, r2, 1);
        while (r2 < y2) r2++, Cpt::modify(l1, r1, r2, r2, 1);
        while (l1 < x1) Cpt::modify(l1, l1, l2, r2, -1), l1++;
        while (l2 < x2) Cpt::modify(l1, r1, l2, l2, -1), l2++;
        while (r1 > y1) Cpt::modify(r1, r1, l2, r2, -1), r1--;
        while (r2 > y2) Cpt::modify(l1, r1, r2, r2, -1), r2--;
        ans[Cpt::edge[i].id] = Cpt::Blk::query(Cpt::edge[i].k);
    }
    for (rg int i = 1; i <= m; i++) {
        // assert(ans[i] > -2);
        write(isl[ans[i] - 1]), puts("");
    }
    return 0;
}