【题目简介】
Description
给你一个N*N的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第K小数。
Input
第一行两个数N,Q，表示矩阵大小和询问组数；
接下来N行N列一共N*N个数，表示这个矩阵；
再接下来Q行每行5个数描述一个询问：x1,y1,x2,y2,k表示找到以(x1,y1)为左上角、以(x2,y2)为右下角的子矩形中的第K小数。
接下来N行N列一共N*N个数，表示这个矩阵；
再接下来Q行每行5个数描述一个询问：x1,y1,x2,y2,k表示找到以(x1,y1)为左上角、以(x2,y2)为右下角的子矩形中的第K小数。
Output
对于每组询问输出第K小的数。
Sample Input
2 2
2 1
3 4
1 2 1 2 1
1 1 2 2 3
Sample Output
1
3
HINT
矩阵中数字是109以内的非负整数；
20%的数据：N<=100,Q<=1000；
40%的数据：N<=300,Q<=10000；
60%的数据：N<=400,Q<=30000；
100%的数据：N<=500,Q<=60000。
Source
【题解】
虽然说好要写su套su，但是打隔膜太high结果时间不够了。。。
第一眼看到题目：果奔二维可持久化线段树？（NiroBC确实这么写了）
既然是离线还是用简单快速的乱搞好辣！
整体二分，对于区间[l,r]，询问答案为mid，则将[l,mid]之间的点插入二维树状数组。
然后对于一些询问，如果当前矩阵的元素个数>=k那么就加到左边，否则加到右边。
那么就转化出同样的子问题，左边二分[l,mid]，右边二分[mid+1,r]。
于是最后的复杂度就变成了O(mlog3n)辣！
（然而窝的程序狂wa怎么回事）
【Codes】
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=60010;
int n,m,cnt,T,i,j;
int tree[505][505],ans[N],id[N],tmp[N],mark[N];
struct shit{int x1,x2,y1,y2,K;}q[60005];
struct fuck{int x,y,w;}a[250005];
bool operator<(fuck a,fuck b){return a.w<b.w;}
void add(int x,int y,int t){
for(int i=x;i<=n;i+=i&-i)
for(int j=y;j<=n;j+=j&-j)
tree[i][j]+=t;
}
int query(int x,int y){
int tmp=0;
for(int i=x;i;i-=i&-i)
for(int j=y;j;j-=j&-j)
tmp+=tree[i][j];
return tmp;
}
int query(int k){
int x1=q[k].x1,y1=q[k].y1,x2=q[k].x2,y2=q[k].y2;
return query(x2,y2)+query(x1-1,y1-1)-query(x1-1,y2)-query(x2,y1-1);
}
void solve(int l,int r,int L,int R){
if(l>r||L==R)return;
int mid=(L+R)>>1;
while(a[T+1].w<=mid&&T<cnt){add(a[T+1].x,a[T+1].y,1);T++;}
while(a[T].w>mid){add(a[T].x,a[T].y,-1);T--;}
int cnt=0;
for(int i=l;i<=r;i++)
if(query(id[i])>q[id[i]].K-1){
mark[i]=1;ans[id[i]]=mid;cnt++;
}else mark[i]=0;
int l1=l,l2=l+cnt;
for(int i=l;i<=r;i++)
if(mark[i])tmp[l1++]=id[i];
else tmp[l2++]=id[i];
for(int i=l;i<=r;i++)id[i]=tmp[i];
solve(l,l1-1,L,mid);
solve(l1,l2-1,mid+1,R);
}
int main(){
scanf("%d%d",&n,&m);
int mx=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
a[++cnt].x=i,a[cnt].y=j,scanf("%d",&a[cnt].w);
mx=max(a[cnt].w,mx);
}
sort(a+1,a+cnt+1);
for(i=1;i<=m;i++)scanf("%d%d%d%d%d",&q[i].x1,&q[i].y1,&q[i].x2,&q[i].y2,&q[i].K);
for(i=1;i<=m;i++)id[i]=i;
solve(1,m,0,mx+1);
for(i=1;i<=m;i++)printf("%d\n",ans[i]);
}
评论 (0)
