本文共 2077 字，大约阅读时间需要 6 分钟。
考虑看到什么k小就整体二分套上去试一下。
// luogu-judger-enable-o2/* mail: mleautomaton@foxmail.com author: MLEAutoMaton This Code is made by MLEAutoMaton*/#include #include #include #include #include #include #include #include #include using namespace std;#define ll long long#define re register#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)inline int gi(){ int f=1,sum=0;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();} return f*sum;}const int N=1000010;struct node{ int x,y,k,xx,yy,id;}q[N],q1[N],q2[N];int c[510][510],n,Q,ans[N];int lowbit(int x){return x&(-x);}void Add(int x,int y,int d){for(int i=x;i<=n;i+=lowbit(i))for(int j=y;j<=n;j+=lowbit(j))c[i][j]+=d;}int query(int x,int y){int ret=0;for(int i=x;i>0;i-=lowbit(i))for(int j=y;j>0;j-=lowbit(j))ret+=c[i][j];return ret;}int query(int x,int xx,int y,int yy){return query(xx,yy)-query(x-1,yy)-query(xx,y-1)+query(x-1,y-1);}void solve(int l,int r,int ql,int qr){ if(ql>qr)return; if(l==r) { for(re int i=ql;i<=qr;i++) if(q[i].id)ans[q[i].id]=l; return; } int mid=(l+r)>>1,L=0,R=0; for(re int i=ql;i<=qr;i++) if(q[i].id) { int sum=query(q[i].x,q[i].xx,q[i].y,q[i].yy); if(sum>=q[i].k)q1[++L]=q[i]; else{q[i].k-=sum;q2[++R]=q[i];} } else { if(q[i].k<=mid){q1[++L]=q[i];Add(q[i].x,q[i].y,1);} else q2[++R]=q[i]; } for(re int i=ql;i<=qr;i++) if(!q[i].id && q[i].k<=mid)Add(q[i].x,q[i].y,-1); for(re int i=1;i<=L;i++)q[ql+i-1]=q1[i]; for(re int i=1;i<=R;i++)q[ql+L+i-1]=q2[i]; solve(l,mid,ql,ql+L-1);solve(mid+1,r,ql+L,qr);}int main(){ n=gi();int cnt=gi(); for(re int i=1;i<=n;i++) for(re int j=1;j<=n;j++) q[++Q]=(node){i,j,gi(),0,0,0}; int Time=0; while(cnt--) { Time++; int x=gi(),y=gi(),xx=gi(),yy=gi(),k=gi(); q[++Q]=(node){x,y,k,xx,yy,Time}; } solve(1,1e9,1,Q); for(int i=1;i<=Time;i++) printf("%d\n",ans[i]); return 0;}
转载于:https://www.cnblogs.com/mle-world/p/10580583.html