题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2738
这个题,真的是妙啊!
整体二分看起来很好用的样子!
#include<bits/stdc++.h> #define LL long long #define abs(x) ((x)>0?(x):-(x)) using namespace std; const int N = 500+9; const int M = 250000+9; const int Q = 60000+9; struct Point{int val,x,y;inline bool operator < (const Point &B) const {return val < B.val;}}p[M]; struct Query{int k,x1,x2,y1,y2,id;}q[Q],buf[Q]; int n,m,vout[Q]; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar(); return ret*f; } namespace Fenwick_Tree{ #define BIT Fenwick_Tree #define lowbit(x) ((x)&-(x)) int sum[N][N]; inline void modify(int x, int y, int delta) { if (x <= 0 || y <= 0) return; for (int j=y;j<=n;j+=lowbit(j)) for (int i=x;i<=n;i+=lowbit(i)) sum[i][j] += delta; } inline int query(int x, int y){ if (x <= 0 || y <= 0) return 0; int ret = 0; for (int j=y;j;j-=lowbit(j)) for (int i=x;i;i-=lowbit(i)) ret += sum[i][j]; return ret; } }; void solve(int l, int r, int L, int R) { if (l == r) for (int i=L;i<=R;i++) vout[q[i].id] = p[l].val; else { int mid = l + r + 1 >> 1,ls=L-1,rs=R+1; for (int i=l;i<=mid-1;i++) BIT::modify(p[i].x,p[i].y,1); for (int i=L,tmp;i<=R;i++) { tmp = BIT::query(q[i].x1-1,q[i].y1-1); tmp += BIT::query(q[i].x2,q[i].y2); tmp -= BIT::query(q[i].x1-1,q[i].y2); tmp -= BIT::query(q[i].x2,q[i].y1-1); if (tmp >= q[i].k) buf[++ls] = q[i]; else q[i].k -= tmp, buf[--rs] = q[i]; } memcpy(q+L,buf+L,sizeof(buf[0])*(R-L+1)); for (int i=l;i<=mid-1;i++) BIT::modify(p[i].x,p[i].y,-1); if (L <= ls) solve(l,mid-1,L,ls); if (rs <= R) solve(mid,r,rs,R); } } int main(){ n = read(); m = read(); for (int j=1,t=1;j<=n;j++) for (int i=1;i<=n;i++,t++) p[t].x = i, p[t].y = j, p[t].val = read(); for (int i=1,a,b,c,d,e,f;i<=m;i++) q[i].y1 = read(), q[i].x1 = read(), q[i].y2 = read(), q[i].x2 = read(), q[i].k = read(), q[i].id = i; sort(p+1,p+1+n*n); solve(1,n*n,1,m); for (int i=1;i<=m;i++) printf("%d\n",vout[i]); return 0; }