laekov

全局二分的经典题。

最初试图用持久化线段树和分块，然后欢快地tle+mle了。看到jason_yu和mhy过了，只能说自己的常数优化还不过关啊。

第一次写这种二分。就是把所有东西扔进来快速排序，顺便考虑每个询问应该被扔到哪边。然后加树状数组来统计就好了。

代码巨丑。

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>

using namespace std;

struct query {

int x1, y1, x2, y2, k, n;

};

int _d_;

#define readInt(_x_) { \

int& _s_ = _x_; \

while (!isdigit(_d_ = getchar())); \

_s_ = 0; \

while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \

}

const int maxn = 509;

const int maxq = 310009;

int n, m, t, maxa, a[maxn][maxn], b[maxn][maxn], ttm;

int d[maxn * maxn], ans[maxq], tdr[maxq];

query q[maxq];

void btChg(int x, int y, int v) {

for (int p = x; p <= n; p += (p & -p))

for (int q = y; q <= n; q += (q & -q))

if (b[p][q] ^ ttm) { 

a[p][q] = v;

b[p][q] = ttm;

}

else

a[p][q] += v;

}

int btQry(int x, int y) {

int s = 0;

for (int p = x; p; p -= (p & -p))

for (int q = y; q; q -= (q & -q))

if (b[p][q] == ttm)

s += a[p][q];

return s;

}

void qSort(int vl, int vr, int ql, int qr) {

if (vl == vr) {

for (int i = ql; i <= qr; ++ i)

if (q[i]. n > -1)

ans[q[i]. n] = d[vl];

}

else {

++ ttm;

int vm = (vl + vr) >> 1;

for (int i = ql; i <= qr; ++ i)

if (q[i]. n == -1) {

if (q[i]. k <= d[vm]) {

btChg(q[i]. x1, q[i]. y1, 1);

tdr[i] = 0;

}

else

tdr[i] = 1;

}

for (int i = ql; i <= qr; ++ i)

if (q[i]. n > -1) {

int g = btQry(q[i]. x2, q[i]. y2) + btQry(q[i]. x1, q[i]. y1)

   - btQry(q[i]. x1, q[i]. y2) - btQry(q[i]. x2, q[i]. y1);

if (g < q[i]. k) {

q[i]. k -= g;

tdr[i] = 1;

}

else

tdr[i] = 0;

}

int i = ql, j = qr;

while (i < j) {

for (; i < j && tdr[i] == 0; ++ i);

for (; i < j && tdr[j] == 1; -- j);

if (i <= j) {

swap(q[i], q[j]);

swap(tdr[i], tdr[j]);

++ i;

-- j;

}

}

for (i = ql - 1; i < qr && tdr[i + 1] == 0; ++ i);

if (ql <= i)

qSort(vl, vm, ql, i);

if (i + 1 <= qr)

qSort(vm + 1, vr, i + 1, qr);

}

}

int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif

memset(a, 0, sizeof(a));

memset(b, 0, sizeof(b));

ttm = 0;

readInt(n);

readInt(m);

t = 0;

maxa = 0;

for (int i = 1; i <= n; ++ i)

for (int j = 1; j <= n; ++ j) {

readInt(q[t]. k);

if (q[t]. k > maxa)

maxa = q[t]. k;

d[i * n + j - n - 1] = q[t]. k;

q[t]. x1 = i;

q[t]. y1 = j;

q[t]. n = -1;

++ t;

}

sort(d, d + n * n);

for (int i = 0; i < m; ++ i) {

readInt(q[t]. x1);

-- q[t]. x1;

readInt(q[t]. y1);

-- q[t]. y1;

readInt(q[t]. x2);

readInt(q[t]. y2);

readInt(q[t]. k);

q[t]. n = i;

++ t;

}

qSort(0, n * n - 1, 0, t - 1);

for (int i = 0; i < m; ++ i)

printf("%d\n", ans[i]);

}