题解当笔记....
题目描述
题目链接:https://www.luogu.com.cn/problem/P1527
算法1
(整体二分 + 二维数组) $O(n * log^3n)$
C++ 代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<string>
#include<cstring>
#include<bitset>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<iomanip>
#include<algorithm>
#define dbgfull(x) cerr << #x << " = " << x << " (line " << __LINE__ << ")"<<endl;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define dbg(x) cerr << #x " = " << (x) << endl
#define endl "\n"
#define int long long
#define PI acos(-1)
//CLOCKS_PER_SEC clock()函数每秒执行次数
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 6e5+5,M = N * 2;
int mod = 1e9 +7;
int n,m,k,S,T;
struct node{
int op,x,y,xx,yy,v,id;
}q[N],lq[N],rq[N];
int tr[505][505];
int lowbit(int x){
return x & -x;
}
void add(int x,int y,int v){
for(int i = x ; i <= n ; i += lowbit(i)){
for(int j = y ; j <= n ; j += lowbit(j)){
tr[i][j] += v;
}
}
}
int query(int x,int y){
int res = 0;
for(int i = x ; i > 0 ; i -= lowbit(i)){
for(int j = y ; j > 0 ; j -= lowbit(j)){
res += tr[i][j];
}
}
return res;
}
int ans[N];
int get(int x,int y,int xx,int yy){
return query(xx,yy) - query(xx,y - 1) - query(x - 1,yy) + query(x - 1,y - 1);
}
void work(int vl,int vr,int ql,int qr){
if(vl > vr || ql > qr) return;
//找到答案,更新所有查询操作
if(vl == vr){
for(int i = ql ; i <= qr ; ++i){
if(q[i].op == 2) ans[q[i].id] = vl;
}
return;
}
int mid = vl + vr >> 1,nl = 0,nr = 0;
for(int i = ql ; i <= qr ; ++i){
//插入操作
if(q[i].op == 1){
//若插入的值小于等于mid则将该数的位置在树状数组中+1,进入左半边
if(q[i].v <= mid) add(q[i].x,q[i].y,1),lq[nl++] = q[i];
else rq[nr++] = q[i];
}
//查询操作
else{
//查询该矩阵中小于mid的数的个数
int t = get(q[i].x,q[i].y,q[i].xx,q[i].yy);
//若要查询个数小于等于t,则答案在左半边区间
if(q[i].v <= t) lq[nl++] = q[i];
//否则答案在右半边区间,减去左半边区间的个数
else{
q[i].v -= t;
rq[nr++] = q[i];
}
}
}
//回溯树状数组
for(int i = ql ; i <= qr ; ++i){
if(q[i].op == 1){
if(q[i].v <= mid) add(q[i].x,q[i].y,-1);
}
}
for(int i = 0 ; i < nl ; ++i) q[ql + i] = lq[i];
for(int i = 0 ; i < nr ; ++i) q[ql + nl + i] = rq[i];
work(vl,mid,ql,ql + nl - 1);
work(mid + 1,vr,ql + nl,qr);
}
void solve(){
cin >> n >> m;
int tot = 0;
int mind = INF,maxd = -INF;
for(int i = 1 ; i <= n ; ++i){
for(int j = 1 ; j <= n ; ++j){
int x;
cin >> x;
//插入操作,在i,j位置插入x
q[++tot] = {1,i,j};
q[tot].v = x;
mind = min(mind,x);
maxd = max(maxd,x);
}
}
for(int i = 1 ; i <= m ; ++i){
int x,y,xx,yy,k;
//查询操作,查询左上角为x,y,右下角为xx,yy矩形区间内第k小的数
cin >> x >> y >> xx >> yy >> k;
q[++tot] = {2,x,y,xx,yy,k,i};
}
work(mind,maxd,1,tot);
for(int i = 1 ; i <= m ; ++i) cout << ans[i] << endl;
}
signed main(){
IOS;
solve();
return 0;
}
算法2
(整体二分 + 扫描线) $O(n * log^2n)$
待续....