题目传送门：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;
}
I’m gone to inform my little brother, that he should also
visit this blog on regular basis to take updated from most up-to-date news
update.
An outstanding share! I’ve just forwarded this onto a coworker who
had been conducting a little homework on this.
And he in fact ordered me dinner because I stumbled upon it
for him… lol. So let me reword this…. Thank YOU
for the meal!! But yeah, thanks for spending the time to
discuss this issue here on your web site.
Wow, this piece of writing is good, my sister is analyzing these things, therefore I am going to tell
her.
Wow that was unusual. I just wrote an very long comment but after I clicked submit
my comment didn’t appear. Grrrr… well I’m not writing all that over again. Anyhow, just
wanted to say great blog!
I blog often and I really thank you for your content.
This article has really peaked my interest. I’m going to book mark your site and keep checking for new details about once a week.
I opted in for your Feed as well.
Its not my first time to visit this website, i am visiting this web
page dailly and take nice data from here everyday.
Great article! We are linking to this great content on our
site. Keep up the great writing.
you are really a excellent webmaster. The web site loading velocity is incredible.
It kind of feels that you are doing any unique trick.
Also, The contents are masterpiece. you’ve performed a wonderful job in this topic!
This is a very good tip especially to those fresh to the blogosphere.
Simple but very precise information… Thank you for sharing this one.
A must read article!
Your means of telling all in this article is actually fastidious,
all be able to effortlessly be aware of it, Thanks a lot.
Just wish to say your article is as astonishing. The clarity on your submit is just cool and that i could
suppose you are a professional on this subject.
Well together with your permission allow me to seize
your RSS feed to stay updated with impending post.
Thanks a million and please carry on the gratifying work.
My spouse and I stumbled over here from a different web address and
thought I should check things out. I like
what I see so now i’m following you. Look forward to going over your
web page yet again.
Hi there this is somewhat of off topic but I was wanting to know if blogs use WYSIWYG editors or
if you have to manually code with HTML. I’m starting a blog soon but have no coding expertise so I wanted
to get advice from someone with experience. Any help would be greatly appreciated!
Whats Going down i am new to this, I stumbled upon this I’ve found It positively useful and it has aided me out loads. I’m hoping to contribute & help different users like its aided me. Good job.
That is really fascinating, You’re a very skilled blogger.
I have joined your feed and stay up for
seeking more of your magnificent post. Additionally, I’ve shared your web site in my social networks
Way cool! Some extremely valid points! I appreciate you penning this write-up plus the rest of the website
is also very good.
Hello my family member! I want to say that this article is awesome, great written and come with approximately
all significant infos. I’d like to see extra posts like this .
I visited multiple sites however the audio feature for audio songs current at this web page is really excellent.
Hi, i think that i saw you visited my site thus i came to “return the favor”.I’m
trying to find things to improve my website!I suppose its ok to use a few of your ideas!!
What’s up, I wish for to subscribe for this
blog to obtain most recent updates, thus where can i do it please assist.
Thank you for some other informative blog. The place else could I get
that type of information written in such an ideal manner?
I have a venture that I’m just now running on, and I’ve been at the look out
for such info.
Excellent blog post. I absolutely appreciate this website. Stick with it!
Very soon this site will be famous among all blog visitors, due to it’s fastidious articles or reviews
Hey! I’m at work browsing your blog from my new iphone! Just wanted to say I love
reading your blog and look forward to all your posts!
Carry on the superb work!
Hi there, I enjoy reading all of your post. I like to write a little comment to support you.
Do you mind if I quote a couple of your articles as long as I provide credit and sources back to your blog?
My blog site is in the exact same niche as yours and my visitors would genuinely benefit from some of the information you present here.
Please let me know if this ok with you. Appreciate it!
It’s hard to find knowledgeable people on this topic, but you sound like you know what you’re talking about! Thanks