更新日志
思路
和一维没有多大区别。
插入时，双重循环，分别循环两个维度。查询时同理。
细节
如果查询区间和用二维前缀和的方法即可。
模板
struct fenwick{
ll dat[N][N];
int lowbit(int x){return x&-x;}
void add(int x,int y,ll v){
for(int i=x;i<=n;i+=lowbit(i)){
for(int j=y;j<=n;j+=lowbit(j)){
dat[i][j]+=v;
}
}
}
ll query(int x,int y){
ll res=0;
for(int i=x;i>0;i-=lowbit(i)){
for(int j=y;j>0;j-=lowbit(j)){
res+=dat[i][j];
}
}
return res;
}
}fwt;
ll getsum(int x1,int y1,int x2,int y2){
return fwt.query(x2,y2)-fwt.query(x2,y1-1)-fwt.query(x1-1,y2)+fwt.query(x1-1,y1-1);
}
例题
代码
前注：非题解，不做详细讲解
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef double db;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<pii,pii> ppp;
template <typename Type>
using vec=vector<Type>;
template <typename Type>
using grheap=priority_queue<Type>;
template <typename Type>
using lrheap=priority_queue<Type,vector<Type>,greater<Type> >;
#define fir first
#define sec second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define per(i,x,y) for(int i=y;i>=x;i--)
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7/*998244353*/;
const int N=505,M=500*500+5,Q=6e4+5;
int n,q,m;
int a[N][N],x[M];
struct query{
int x1,y1,x2,y2;
int k;
}qs[Q];
int arr[Q],tmp[Q],ans[Q];
vec<pii> plcs[M];
bool can[M];
struct fenwick{
int dat[N][N];
int lowbit(int x){return x&-x;}
void add(int x,int y,ll v){
for(int i=x;i<=n;i+=lowbit(i)){
for(int j=y;j<=n;j+=lowbit(j)){
dat[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+=dat[i][j];
}
}
return res;
}
}fwt;
int getsum(int x1,int y1,int x2,int y2){
return fwt.query(x2,y2)-fwt.query(x2,y1-1)-fwt.query(x1-1,y2)+fwt.query(x1-1,y1-1);
}
void solve(int x,int y,int l,int r){
if(l>r)return;
if(l==r){
rep(i,x,y)ans[arr[i]]=l;
return;
}
int mid=l+r>>1;
rep(i,l,mid){
for(auto j:plcs[i]){
fwt.add(j.fir,j.sec,1);
}
}
int cnt=0;
rep(i,x,y){
query &now=qs[arr[i]];
int sum=getsum(now.x1,now.y1,now.x2,now.y2);
if(sum>=now.k){
can[i]=true;
cnt++;
}else{
can[i]=false;
now.k-=sum;
}
}
rep(i,l,mid){
for(auto j:plcs[i]){
fwt.add(j.fir,j.sec,-1);
}
}
int cnt1=0,cnt2=0;
rep(i,x,y){
if(can[i]){
tmp[x+cnt1]=arr[i];
cnt1++;
}else{
tmp[x+cnt+cnt2]=arr[i];
cnt2++;
}
}
rep(i,x,y)arr[i]=tmp[i];
solve(x,x+cnt-1,l,mid);
solve(x+cnt,y,mid+1,r);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>q;
rep(i,1,n)rep(j,1,n){
cin>>a[i][j];
x[++m]=a[i][j];
}
sort(x+1,x+1+m);
m=unique(x+1,x+1+m)-x-1;
rep(i,1,n)rep(j,1,n){
a[i][j]=lower_bound(x+1,x+1+m,a[i][j])-x;
plcs[a[i][j]].pub({i,j});
}
rep(i,1,q)cin>>qs[i].x1>>qs[i].y1>>qs[i].x2>>qs[i].y2>>qs[i].k;
rep(i,1,q)arr[i]=i;
solve(1,q,1,m);
rep(i,1,q)cout<<x[ans[i]]<<"\n";
return 0;
}