题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3585
数据生成器：http://paste.ubuntu.com/15521165/
我写的是莫队的算法，然而多了一个log，不过还是勉强卡过去辣
其实带log的算法，还有一种更优雅的写法：用线段树来维护区间最值
不过真正不带log的算法，还是只能是莫队配合分块吧！
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 200000+9;
int arr[N],cnt[N],n,m,block,vout[N];
set<int> ans;
struct Query{
int l,r,b,id;
bool operator < (const Query & B) const {
return b < B.b || (b == B.b && r < B.r);
}
}q[N];
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;
}
inline void update(int ty, bool delta) {
if (ty > n) return;
if (delta) {
cnt[ty]++;
if (cnt[ty] == 1) {
ans.erase(ty);
}
} else {
cnt[ty]--;
if (!cnt[ty]) {
ans.insert(ty);
}
}
}
int main(){
n = read(); m = read(); block = sqrt(n) + 1;
for (int i=1;i<=n;i++) {
arr[i] = read();
ans.insert(i);
} ans.insert(0);
for (int i=1;i<=m;i++) {
q[i].l = read();
q[i].r = read();
q[i].b = q[i].l / block;
q[i].id = i;
}
sort(q+1, q+1+m);
for (int i=1,p1=1,p2=0,l,r;i<=m;i++) {
l = q[i].l; r = q[i].r;
while (p1 < l) update(arr[p1++], 0);
while (p2 > r) update(arr[p2--], 0);
while (p2 < r) update(arr[++p2], 1);
while (p1 > l) update(arr[--p1], 1);
vout[q[i].id] = *(ans.begin());
}
for (int i=1;i<=m;i++) {
printf("%d\n",vout[i]);
}
return 0;
}
It’s actually a great and helpful piece of info. I’m satisfied that you just shared this helpful
information with us. Please stay us informed like this.
Thank you for sharing.
Hello there! This is kind of off topic but I need some help from an established blog.
Is it tough to set up your own blog? I’m not very techincal but I can figure
things out pretty fast. I’m thinking about making my
own but I’m not sure where to start. Do you
have any ideas or suggestions? Thanks
I will immediately snatch your rss feed as I can’t
to find your email subscription hyperlink or newsletter
service. Do you have any? Please permit me understand so that I could subscribe.
Thanks.
Howdy I am so grateful I found your website, I really found you by mistake, while I was
looking on Aol for something else, Anyways I am here now and would just like to say thanks a
lot for a incredible post and a all round exciting blog (I also
love the theme/design), I don’t have time to read it all at the moment but I have book-marked it and also added in your RSS
feeds, so when I have time I will be back to read more, Please do keep up the
fantastic job.
An impressive share! I’ve just forwarded this onto a friend who was doing a little research on this.
And he in fact bought me lunch because I found it for him…
lol. So let me reword this…. Thank YOU for the meal!! But yeah, thanks for
spending some time to discuss this subject here on your internet site.
Hi it’s me, I am also visiting this site on a regular
basis, this website is actually good and the visitors are really
sharing good thoughts.
obviously like your website however you have to test the spelling on several of your posts.
Many of them are rife with spelling issues and
I in finding it very bothersome to inform the truth however I’ll surely come again again.
Thanks for the marvelous posting! I really enjoyed reading it, you
will be a great author.I will be sure to bookmark your blog and will often come back later on. I want to
encourage continue your great writing,
have a nice holiday weekend!
Hey I know this is off topic but I was wondering if you knew of any widgets I could add to my blog that
automatically tweet my newest twitter updates. I’ve been looking
for a plug-in like this for quite some time and was hoping maybe you would have some experience with something like this.
Please let me know if you run into anything. I truly enjoy
reading your blog and I look forward to your
new updates.
I’m truly enjoying the design and layout of your site.
It’s a very easy on the eyes which makes it much more enjoyable for me to come here and visit
more often. Did you hire out a designer to create
your theme? Excellent work!
I visited various web pages except the audio
quality for audio songs existing at this web site is truly fabulous.
Hello, Neat post. There’s an issue along
with your site in internet explorer, might test this? IE still
is the market chief and a huge section of folks will pass over your great writing due to this problem.
Perfect work you have done, this web site is really cool with excellent information.
Excellent post. Keep writing such kind of information on your page.
Im really impressed by your blog.
Hey there, You’ve done a great job. I’ll certainly digg it and for my
part suggest to my friends. I’m sure they’ll be benefited from this
web site.
Excellent article. Keep posting such kind of information on your page.
Im really impressed by your site.
Hi there, You have performed a fantastic job.
I will definitely digg it and for my part recommend to my friends.
I’m sure they’ll be benefited from this website.
Appreciation to my father who told me on the topic of this weblog, this website is really amazing.
you are in reality a just right webmaster. The site loading pace is incredible.
It seems that you are doing any distinctive trick.
Also, The contents are masterwork. you’ve performed a excellent process in this subject!
This is really interesting, You are a very skilled blogger.
I have joined your feed and look forward to seeking more of your great post.
Also, I have shared your site in my social networks!
I used to be recommended this blog by way of my cousin. I am now not sure
whether this post is written by means of him as nobody else recognize such distinctive approximately my problem.
You’re wonderful! Thank you!
Amazing! This blog looks just like my old one!
It’s on a entirely different subject but it has pretty much the same
layout and design. Excellent choice of colors!
It’s impressive that you are getting ideas from this piece of
writing as well as from our dialogue made at this time.
Great write-up, I am normal visitor of one¦s website, maintain up the excellent operate, and It is going to be a regular visitor for a long time.