和之前的题目差不多 用一个二维矩阵维护即可
// luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) ///////////////////////////////////// const int N=1e6+10; int n,m,t[2000][2000],k,ans[N],cnt,a[N],tot; void add(int x,int y,int v) { for(int i=x;i<=500;i+=i&-i) for(int j=y;j<=500;j+=j&-j)t[i][j]+=v; } int qsum(int x,int y) { int ans=0;for(int i=x;i>0;i-=i&-i) for(int j=y;j>0;j-=j&-j)ans+=t[i][j]; return ans; } int qjuxin(int x1,int y1,int x2,int y2) { int ans=qsum(x2,y2);ans+=qsum(x1-1,y1-1);ans-=qsum(x1-1,y2);ans-=qsum(x2,y1-1);return ans; } struct node{int x1,y1,x2,y2, k,op,id;}s[N],temp1[N],temp2[N]; void cdq(int l,int r,int L,int R) { if(L>R)return ; if(l==r) { rep(i,L,R)if(s[i].op==2)ans[s[i].id]=l; return ; } int mid=(l+r)>>1,cnt1=0,cnt2=0; rep(i,L,R) { if(s[i].op==1) { if(s[i].x2<=mid)add(s[i].x1,s[i].y1,1),temp1[++cnt1]=s[i]; else temp2[++cnt2]=s[i]; } else { int x=qjuxin(s[i].x1,s[i].y1,s[i].x2,s[i].y2); // printf("x=%d ",x); if(s[i].k<=x)temp1[++cnt1]=s[i]; else s[i].k-=x,temp2[++cnt2]=s[i]; } } rep(i,1,cnt1)if(temp1[i].op==1)add(temp1[i].x1,temp1[i].y1,-1); rep(i,1,cnt1)s[L-1+i]=temp1[i]; rep(i,1,cnt2)s[L+cnt1-1+i]=temp2[i]; cdq(l,mid,L,L+cnt1-1); cdq(mid+1,r,L+cnt1,R); } int main() { cin>>n>>m; rep(i,1,n)rep(j,1,n) { int x;scanf("%d",&x); s[++cnt]=(node){i,j,x,1,0,1,i}; } rep(i,1,m) { int a,b,c,d,e;scanf("%d%d%d%d%d",&a,&b,&c,&d,&e); s[++cnt]=(node){a,b,c,d,e,2,i}; } cdq(0,inf,1,cnt); rep(i,1,m) printf("%d ",ans[i]); return 0; }