题目链接

题解

将矩阵中的位置取出来按权值排序

直接整体二分 + 二维BIT即可

#include<algorithm>

#include<iostream>

#include<cstdio>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define lbt(x) (x & -x)

using namespace std;

const int maxn = 300005,maxm = 100005,INF = 0x3f3f3f3f;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}

	return flag ? out : -out;

}

struct node{int x,y,v;}e[maxn];

struct Que{int x1,y1,x2,y2,k,id;}q[maxn],t[maxn];

int b[maxn],bi,N,Q,n,tot,ans[maxn],s[505][505];

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

	for (int i = x; i <= n; i += lbt(i))

		for (int j = y; j <= n; j += lbt(j))

			s[i][j] += v;

}

int query(int x,int y){

	int re = 0;

	for (int i = x; i; i -= lbt(i))

		for (int j = y; j; j -= lbt(j))

			re += s[i][j];

	return re;

}

int sum(int x1,int y1,int x2,int y2){

	return query(x2,y2) - query(x2,y1 - 1) - query(x1 - 1,y2) + query(x1 - 1,y1 - 1);

}

inline bool operator <(const node& a,const node& b){

	return a.v < b.v;

}

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] = e[l].v;

		return;

	}

	int mid = l + r >> 1,li = L,ri = R,v;

	for (int i = l; i <= mid; i++) add(e[i].x,e[i].y,1);

	for (int i = L; i <= R; i++){

		v = sum(q[i].x1,q[i].y1,q[i].x2,q[i].y2);

		if (v >= q[i].k) t[li++] = q[i];

		else q[i].k -= v,t[ri--] = q[i];

	}

	for (int i = L; i <= R; i++) q[i] = t[i];

	for (int i = l; i <= mid; i++) add(e[i].x,e[i].y,-1);

	solve(l,mid,L,li - 1); solve(mid + 1,r,ri + 1,R);

}

int main(){

	n = read(); Q = read();

	REP(i,n) REP(j,n) e[++N] = (node){i,j,b[++bi] = read()};

	REP(i,Q) q[i].x1 = read(),q[i].y1 = read(),q[i].x2 = read(),q[i].y2 = read(),q[i].k = read(),q[i].id = i;

	sort(b + 1,b + 1 + bi); tot = 1;

	for (int i = 2; i <= bi; i++) if (b[i] != b[tot]) b[++tot] = b[i];

	REP(i,N) e[i].v = lower_bound(b + 1,b + 1 + tot,e[i].v) - b;

	sort(e + 1,e + 1 + N);

	solve(1,N,1,Q);

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

	return 0;

}

巴特西

BZOJ2738 矩阵乘法【整体二分 + BIT】

题目链接

题解

最新文章

热门文章

巴特西

BZOJ2738 矩阵乘法 【整体二分 + BIT】

题目链接

题解

最新文章

热门文章

BZOJ2738 矩阵乘法【整体二分 + BIT】