http://www.tsinsen.com/A1333

题意:……

思路:和之前的第k小几乎一样,只不过把一维BIT换成二维BIT而已。注意二维BIT写法QAQ

 #include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <stack>
using namespace std;
#define INF 0x3f3f3f3f
#define N 350000
typedef long long LL;
struct P {
int x1, x2, y1, y2, val, id;
P () {}
P (int x1, int y1, int x2, int y2, int val, int id) : x1(x1), y1(y1), x2(x2), y2(y2), val(val), id(id) {}
} q[N], lq[N], rq[N];
int bit[][], ans[N], n; int lowbit(int x) { return x & (-x); } void update(int x, int y, int w) {
for(int i = x; i <= n; i += lowbit(i))
for(int j = y; j <= n; j += lowbit(j)) bit[i][j] += w;
} int query(int x, int y) {
int ans = ;
for(int i = x; i; i -= lowbit(i))
for(int j = y; j; j -= lowbit(j)) ans += bit[i][j];
return ans;
} void Solve(int lask, int rask, int l, int r) {
if(lask > rask || l > r) return ;
if(l == r) {
for(int i = lask; i <= rask; i++) if(q[i].id) ans[q[i].id] = l;
return ;
}
int mid = (l + r) >> , lcnt = , rcnt = ;
for(int i = lask; i <= rask; i++) {
if(!q[i].id) {
if(q[i].val <= mid) {
update(q[i].x1, q[i].y1, );
lq[++lcnt] = q[i];
} else rq[++rcnt] = q[i];
} else {
int num = query(q[i].x2, q[i].y2) - query(q[i].x1 - , q[i].y2) - query(q[i].x2, q[i].y1 - ) + query(q[i].x1 - , q[i].y1 - );
if(num >= q[i].val) lq[++lcnt] = q[i];
else {
q[i].val -= num;
rq[++rcnt] = q[i];
}
}
}
for(int i = ; i <= lcnt; i++) if(!lq[i].id) update(lq[i].x1, lq[i].y1, -);
for(int i = ; i <= lcnt; i++) q[lask+i-] = lq[i];
for(int i = ; i <= rcnt; i++) q[lask+lcnt+i-] = rq[i];
Solve(lask, lask + lcnt - , l, mid);
Solve(lask + lcnt, rask, mid + , r);
} int main() {
int m, cnt = , a;
scanf("%d%d", &n, &m);
memset(bit, , sizeof(bit));
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++) {
scanf("%d", &a); q[++cnt] = P(i, j, , , a, );
}
for(int i = ; i <= m; i++) {
++cnt; q[cnt].id = i;
scanf("%d%d%d%d%d", &q[cnt].x1, &q[cnt].y1, &q[cnt].x2, &q[cnt].y2, &q[cnt].val);
}
Solve(, cnt, , INF);
for(int i = ; i <= m; i++) printf("%d\n", ans[i]);
}
05-08 08:16