whiteqwq @ 2020-05-24 23:31:45
解释：
$rec[]$为离散化与实际数的对应数组
$ans[]$为答案
$q[]$为操作序列
$lq[],rq[]$为分治时临时序列
$num[]$是离散化数组
$update(),query()$是二维树状数组的基本操作
$divide()$是整体二分函数
```
#include<stdio.h>
#include<algorithm>
#define lowbit(x) x&-x
using namespace std;
const int maxn=505,maxm=60005;
int i,j,k,m,n,cnt,tot,nums;
int t[maxn][maxn],rec[maxn*maxn],ans[maxm];
struct opt{
int a,b,c,d,k,o,id;
}q[maxn*maxn+maxm],lq[maxn*maxn+maxm],rq[maxn*maxn+maxm];
struct data{
int x,y,v;
}num[maxn*maxn];
inline int cmp(data a,data b){
return a.v<b.v;
}
inline void read(int &x){
char c=getchar();
x=0;
for(;c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';c=getchar())
x=x*10+c-48;
}
void update(int x,int y,int v){
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=n;j+=lowbit(j))
t[i][j]+=v;
}
int query(int x,int y){
int res=0;
if(x==0||y==0)
return res;
for(int i=x;i;i-=lowbit(i))
for(int j=y;j;j-=lowbit(j))
res+=t[i][j];
return res;
}
int calc(int a,int b,int c,int d){
return query(c,d)-query(a-1,d)-query(c,b-1)+query(a-1,b-1);
}
void divide(int L,int R,int l,int r){
if(l>r)
return ;
if(L==R){
for(int i=l;i<=r;i++)
if(q[i].o)
ans[q[i].id]=L;
return ;
}
int lcnt=0,rcnt=0,mid=L+((R-L)>>1);
for(int i=l;i<=r;i++){
if(q[i].o==0){
if(q[i].k<=mid){
update(q[i].a,q[i].b,1);
lq[++lcnt]=q[i];
}
else rq[++rcnt]=q[i];
}
else{
int now=calc(q[i].a,q[i].b,q[i].c,q[i].d);
if(q[i].k<=now)
lq[++lcnt]=q[i];
else{
rq[++rcnt]=q[i];
rq[rcnt].k-=now;
}
}
}
for(int i=l;i<=r;i++)
if(q[i].o==0&&q[i].k<=mid)
update(q[i].a,q[i].b,-1);
for(int i=1;i<=lcnt;i++)
q[i+l-1]=lq[i];
for(int i=1;i<=rcnt;i++)
q[i+l+lcnt-1]=rq[i];
divide(L,mid,l,l+lcnt-1);
divide(mid+1,r,l+lcnt,r);
}
void newopt(int a,int b,int c,int d,int k,int o,int id){
cnt++,q[cnt].a=a,q[cnt].b=b,q[cnt].c=c,q[cnt].d=d,q[cnt].k=k,q[cnt].o=o,q[cnt].id=id;
}
int main(){
read(n),read(m);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
nums++,read(num[nums].v),num[nums].x=i,num[nums].y=j;
sort(num+1,num+1+nums,cmp);
for(i=1;i<=nums;i++){
if(i==1||num[i].v!=num[i-1].v)
tot++,rec[tot]=num[i].v;
newopt(num[i].x,num[i].y,0,0,tot,0,0);
}
for(i=1;i<=m;i++){
int a,b,c,d,k;
read(a),read(b),read(c),read(d),read(k);
newopt(a,b,c,d,k,1,i);
}
divide(1,tot,1,cnt);
for(i=1;i<=m;i++)
printf("%d\n",rec[ans[i]]);
return 0;
}
```