题面
Bzoj权限题
luogu
Sol
整体二分+二维树状数组裸题。。。
二维树状数组写错了(WA)两遍。。。
# include <bits/stdc++.h>
# define IL inline
# define RG register
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
template <class Int>
IL void Input(RG Int &x){
RG int z = 1; RG char c = getchar(); x = 0;
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
x *= z;
}
const int maxn(505);
const int maxm(60005);
int n, q, c[maxn][maxn], cnt, ans[maxm], o[maxn * maxn], len;
struct Modify{
int x, y, v;
} mdy[maxn * maxn], tmp1[maxn * maxn];
struct Query{
int x1, y1, x2, y2, k, id;
} qry[maxm], tmp2[maxm];
IL void Cls(RG int x, RG int y){
for(RG int i = x; i <= n; i += i & -i)
for(RG int j = y; j <= n; j += j & -j)
c[i][j] = 0;
}
IL void Add(RG int x, RG int y){
for(RG int i = x; i <= n; i += i & -i)
for(RG int j = y; j <= n; j += j & -j)
++c[i][j];
}
IL int Sum(RG int x, RG int y){
RG int ret = 0;
for(RG int i = x; i; i -= i & -i)
for(RG int j = y; j; j -= j & -j)
ret += c[i][j];
return ret;
}
IL int SumMat(RG int x1, RG int y1, RG int x2, RG int y2){
return Sum(x2, y2) - Sum(x1 - 1, y2) - Sum(x2, y1 - 1) + Sum(x1 - 1, y1 - 1);
}
IL void Solve(RG int ml, RG int mr, RG int l, RG int r, RG int ql, RG int qr){
if(ql > qr || ml > mr) return;
if(l == r){
for(RG int i = ql; i <= qr; ++i) ans[qry[i].id] = o[l];
return;
}
RG int mid = (l + r) >> 1, h1 = ml - 1, t1 = mr + 1, h2 = ql - 1, t2 = qr + 1;
for(RG int i = ml; i <= mr; ++i)
if(mdy[i].v <= o[mid]) tmp1[++h1] = mdy[i], Add(mdy[i].x, mdy[i].y);
else tmp1[--t1] = mdy[i];
for(RG int i = ql; i <= qr; ++i){
RG int s = SumMat(qry[i].x1, qry[i].y1, qry[i].x2, qry[i].y2);
if(s >= qry[i].k) tmp2[++h2] = qry[i];
else qry[i].k -= s, tmp2[--t2] = qry[i];
}
for(RG int i = ml; i <= mr; ++i)
if(mdy[i].v <= o[mid]) Cls(mdy[i].x, mdy[i].y);
for(RG int i = ml; i <= mr; ++i) mdy[i] = tmp1[i];
for(RG int i = ql; i <= qr; ++i) qry[i] = tmp2[i];
Solve(ml, h1, l, mid, ql, h2), Solve(t1, mr, mid + 1, r, t2, qr);
}
int main(RG int argc, RG char* argv[]){
Input(n), Input(q);
for(RG int i = 1; i <= n; ++i)
for(RG int j = 1, a; j <= n; ++j)
Input(a), mdy[++cnt] = (Modify){i, j, a}, o[cnt] = a;
sort(o + 1, o + cnt + 1), len = unique(o + 1, o + cnt + 1) - o - 1;
for(RG int i = 1, x1, x2, y1, y2, k; i <= q; ++i){
Input(x1), Input(y1), Input(x2), Input(y2), Input(k);
qry[i] = (Query){x1, y1, x2, y2, k, i};
}
Solve(1, cnt, 1, len, 1, q);
for(RG int i = 1; i <= q; ++i) printf("%d
", ans[i]);
return 0;
}