链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4408
神犇题解：http://www.cnblogs.com/ihopenot/p/6179880.html
题解
假如我们给定一个已经排好序的序列{ai}
考虑神秘数产生的原因：\({a_i} > 1 + \sum\limits_{j = 1}^{i – 1} {{a_j}}\)
考虑给定的询问，如果使用函数式线段树进行处理，那么已经排好序了
现在的问题就是如何找到最小的、符合上述要求的\({a_i}\)
这货不满足二分的性质，所以不能用二分
然后我就不会做了 QwQ
这时，神犇ihopenot说：“直接暴力模拟就可以了啊！”
具体来说：
假设当前已经能够凑出1~i中的所有的数
统计1~(i+1)这个区间内所有数的和
如果等于i则停止，否则继续该操作
我们来考虑一下为什么这样做复杂度是正确的：
假设当前能凑出1~i,使用的最大的数为a
那么合法的下一个数一定在a+1到i+1之间
换一句话来说：进行一次增值操作可以“收割”长度为i-a的区间
更进一步：使用的数最小为a+2，能凑出的数至少为i+a+2
更进两步：下一次至少可以收割长度为i的区间
更进三步：每次收割区间的长度会增加ai，而且ai > a(i-1)+1
更进四步：仔细想一想，这货比Fibonacci数列增长还要快，所以至多进行log(n)次
然后这题就用函数式线段树来暴力迭代就可以辣！
这™是我第四次被Fibonacci数列坑了 QwQ
ps：这货貌似是双倍经验，参见BZOJ_4299
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 100000+9;
const int M = 3300000;
const int INF = 1e9;
int n,m,arr[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;
}
namespace Chair_Tree{
#define CT Chair_Tree
int ch[M][2],sum[M],root[N];
int ans_tmp,cnt;
void insert(int p, int &w, int l, int r, int v) {
w = ++cnt; sum[w] = sum[p] + v;
memcpy(ch[w],ch[p],sizeof(ch[w]));
if (l < r) {
int mid = l + r + 1 >> 1;
if (v < mid) insert(ch[p][0], ch[w][0], l, mid-1, v);
else insert(ch[p][1],ch[w][1], mid, r, v);
}
}
inline void insert(int p, int v) {
insert(root[p-1],root[p],1,INF,v);
}
void query(int p, int w, int l, int r, int v) {
if (l == r) {
ans_tmp += sum[w] - sum[p];
} else {
int mid = l + r + 1 >> 1;
if (v < mid) query(ch[p][0],ch[w][0],l,mid-1,v);
else {
ans_tmp += sum[ch[w][0]] - sum[ch[p][0]];
query(ch[p][1],ch[w][1],mid,r,v);
}
}
}
inline int query(int l, int r, int v) {
ans_tmp = 0;
query(root[l-1],root[r],1,INF,v);
return ans_tmp;
}
};
int main(){
n = read();
for (int i=1;i<=n;i++) {
arr[i] = read();
CT::insert(i,arr[i]);
}
m = read();
for (int j=1,l,r,cur,tmp;j<=m;j++) {
l = read(); r = read(); cur = 0;
while ((tmp = CT::query(l,r,cur+1)) > cur) {
cur = tmp;
}
printf("%d\n",cur+1);
}
return 0;
}
I know this if off topic but I’m looking into starting
my own blog and was curious what all is needed to get set up?
I’m assuming having a blog like yours would cost a pretty penny?
I’m not very internet smart so I’m not 100% positive. Any
recommendations or advice would be greatly appreciated.
Appreciate it
Do you mind if I quote a couple of your articles as long as I provide credit and
sources back to your weblog? My website is in the very same
niche as yours and my users would truly benefit
from some of the information you present here. Please let me know if this alright with you.
Thanks a lot!
It’s remarkable in support of me to have a web site, which is valuable in support of my experience.
thanks admin
I like what you guys tend to be up too. This kind of clever work
and exposure! Keep up the amazing works guys I’ve included you guys
to my blogroll.
There is definately a lot to learn about this subject.
I like all the points you’ve made.
Hi there! Would you mind if I share your blog with my myspace group?
There’s a lot of people that I think would really appreciate
your content. Please let me know. Thank you
Do you mind if I quote a few of your articles as long as I provide
credit and sources back to your site? My website is in the exact same area of
interest as yours and my users would definitely benefit from some of the information you present here.
Please let me know if this ok with you. Cheers!
There is definately a lot to find out about this topic.
I really like all of the points you have made.
Inspiring quest there. What occurred after?
Thanks!
What’s up friends, fastidious paragraph and good arguments commented
at this place, I am actually enjoying by these.
Hello to all, since I am truly keen of reading this webpage’s post to be updated daily.
It consists of fastidious information.
Hi there colleagues, its great piece of writing concerning teachingand fully defined, keep it up
all the time.
My relatives every time say that I am wasting my time here at web, however I know I am getting know-how all the time by reading such
pleasant articles or reviews.
That is a very good tip particularly to those fresh to the blogosphere.
Simple but very precise information… Thanks for sharing this
one. A must read article!
I’m not sure exactly why but this blog is loading extremely slow for
me. Is anyone else having this problem or is it a problem on my end?
I’ll check back later and see if the problem still exists.
Have you ever considered writing an ebook or guest authoring on other websites?
I have a blog based on the same topics you discuss and would really like to have you share some stories/information. I know my viewers would enjoy your work.
If you’re even remotely interested, feel free to shoot me an e-mail.
Hello there! Quick question that’s entirely off topic.
Do you know how to make your site mobile friendly?
My blog looks weird when viewing from my iphone4. I’m trying to find a theme or
plugin that might be able to resolve this issue.
If you have any recommendations, please share. Many thanks!
I was able to find good info from your blog posts.
I’ve read some excellent stuff here. Certainly price bookmarking for revisiting.
I surprise how much effort you set to make any such fantastic informative
web site.
I go to see each day a few sites and information sites to read articles or reviews, however
this website gives quality based posts.
Right away I am ready to do my breakfast, afterward having my breakfast coming
yet again to read further news. pof natalielise
Marvelous, what a web site it is! This web site provides helpful
facts to us, keep it up.
Heya! I realize this is kind of off-topic but I needed to
ask. Does operating a well-established website
such as yours take a lot of work? I am brand new to operating
a blog however I do write in my diary every day.
I’d like to start a blog so I can easily share my experience and views online.
Please let me know if you have any kind of recommendations or tips for brand new aspiring bloggers.
Appreciate it!
There is certainly a lot to learn about this subject.
I really like all the points you have made.
Hey there! Someone in my Facebook group shared this site with us so I came to look it over.
I’m definitely enjoying the information. I’m book-marking and will be tweeting
this to my followers! Wonderful blog and excellent design and style.
Wonderful blog you have here but I was wondering if you knew of any
forums that cover the same topics talked about here? I’d really like to be a part of community where I can get feed-back from other experienced individuals
that share the same interest. If you have any recommendations, please let me know.
Thanks!
I’m curious to find out what blog system you’re working with?
I’m having some small security issues with my latest blog and I would like
to find something more secure. Do you have any suggestions?
My family members all the time say that I am killing my time here at net,
but I know I am getting knowledge every day by reading such pleasant posts.
plenty of fish natalielise
It’s an awesome post designed for all the internet people;
they will obtain advantage from it I am sure. natalielise pof
Spot on with this write-up, I seriously think this website needs much more
attention. I’ll probably be back again to read through more,
thanks for the info!
Today, while I was at work, my cousin stole my apple ipad
and tested to see if it can survive a 25 foot drop, just so she can be a youtube
sensation. My iPad is now broken and she has 83 views.
I know this is totally off topic but I had to share it with
someone!
Howdy just wanted to give you a quick heads up.
The text in your post seem to be running off the screen in Ie.
I’m not sure if this is a formatting issue or something to do with web browser compatibility but I figured I’d
post to let you know. The layout look great though! Hope you get the problem fixed
soon. Thanks
It’s hard to come by well-informed people about
this subject, however, you sound like you know what you’re talking about!
Thanks
Superb, what a website it is! This website gives useful information to us, keep it up.
Hello, Neat post. There’s an issue along with your web site in web explorer, would check
this? IE nonetheless is the marketplace leader and a good component of folks will miss your wonderful writing because of this problem.
Hello, i believe that i saw you visited my blog so i came to return the desire?.I am trying to in finding
things to improve my website!I assume its good enough
to use a few of your ideas!!
Hey there would you mind sharing which blog platform you’re using?
I’m planning to start my own blog in the near future but I’m having a
tough time making a decision between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your layout seems different then most blogs
and I’m looking for something completely unique.
P.S Apologies for getting off-topic but I had to ask!
It’s very straightforward to find out any matter on net as compared to books, as I
found this article at this web page.
We’re a group of volunteers and starting a new scheme in our community.
Your web site offered us with valuable information to work on. You’ve done an impressive job
and our whole community will be thankful to you.
You could certainly see your expertise in the article you
write. The sector hopes for even more passionate writers such as you who are not afraid to
say how they believe. At all times follow your heart.
I do not even know how I ended up right here, however I thought this submit was once good.
I do not realize who you are however certainly you are going to a well-known blogger for those who aren’t
already. Cheers!
Write more, thats all I have to say. Literally, it seems as though
you relied on the video to make your point.
You definitely know what youre talking about, why throw away your
intelligence on just posting videos to your site when you could be giving us something
informative to read?
Good day! I know this is somewhat off topic but I was wondering which blog platform are you
using for this site? I’m getting sick and tired of WordPress because I’ve had
problems with hackers and I’m looking at alternatives for another
platform. I would be great if you could point me in the direction of a good platform.
I enjoy reading through an article that can make men and women think.
Also, thanks for allowing for me to comment!
I know this if off topic but I’m looking into starting
my own blog and was curious what all is required to get set up?
I’m assuming having a blog like yours would cost a pretty penny?
I’m not very internet smart so I’m not 100% sure.
Any suggestions or advice would be greatly appreciated.
Thanks
Hi there, all the time i used to check webpage posts here in the early hours in the
dawn, since i love to find out more and more.
Truly no matter if someone doesn’t be aware of then its up to other viewers that
they will help, so here it occurs.
whoah this weblog is magnificent i like reading your articles.
Keep up the great work! You already know, many persons are looking round for this info, you can help them greatly.
I have read so many articles or reviews regarding the blogger
lovers however this piece of writing is really a nice piece of writing, keep it up.
You really make it seem so easy with your presentation but I find this topic to be really something which I think I would never understand.
It seems too complicated and extremely broad for me.
I am looking forward for your next post, I will try to get the
hang of it!
Since the admin of this website is working, no hesitation very rapidly it will
be famous, due to its quality contents.
Does your website have a contact page? I’m having trouble locating
it but, I’d like to shoot you an e-mail. I’ve got some ideas for your blog you
might be interested in hearing. Either way, great site and
I look forward to seeing it expand over time.
Hi there i am kavin, its my first occasion to commenting anywhere, when i read this
paragraph i thought i could also create comment due to this good post.
It’s a shame you don’t have a donate button! I’d certainly donate to this superb blog!
I suppose for now i’ll settle for bookmarking and adding your RSS feed to my
Google account. I look forward to fresh updates and will talk about this blog with my Facebook group.
Chat soon!
Great blog right here! Also your website a lot up fast! What host are you using?
Can I am getting your associate hyperlink in your host? I desire
my web site loaded up as fast as yours lol
If you want to grow your experience only keep visiting this site and be
updated with the hottest gossip posted here.
Thank you for the good writeup. It in fact was a amusement account it.
Look advanced to more added agreeable from you! By the way,
how can we communicate?
Hi there! I’m at work browsing your blog from my new apple iphone!
Just wanted to say I love reading through your blog and
look forward to all your posts! Keep up the superb work!
Good day! I know this is somewhat off topic but I was wondering if you knew where I could locate a captcha plugin for my comment form?
I’m using the same blog platform as yours and I’m having trouble finding
one? Thanks a lot!
Great article.
Hi there everyone, it’s my first pay a visit at this web site, and piece of writing is truly fruitful designed for me, keep up
posting these articles or reviews.
It’s a pity you don’t have a donate button! I’d without a doubt
donate to this excellent blog! I guess for now i’ll settle for bookmarking and adding your RSS feed to
my Google account. I look forward to brand new updates and will talk about this
site with my Facebook group. Talk soon!
My developer is trying to persuade me to move to .net from PHP.
I have always disliked the idea because of the
costs. But he’s tryiong none the less. I’ve been using Movable-type on various websites for about a
year and am concerned about switching to another platform.
I have heard great things about blogengine.net. Is there a way I can import all
my wordpress content into it? Any help would be really
appreciated!
Everything is very open with a really clear clarification of
the issues. It was really informative. Your site is
useful. Thank you for sharing!
Hey there! I know this is kind of off topic but I was
wondering which blog platform are you using for this
site? I’m getting sick and tired of WordPress because I’ve had issues with hackers and I’m looking at options for
another platform. I would be fantastic if you could point me in the direction of
a good platform.
Keep this going please, great job!
Thanks for sharing your info. I really appreciate your efforts and I am waiting for your further write ups thanks once again.
You really make it seem so easy with your presentation but I find this matter to be actually something which I
think I would never understand. It seems too complicated and extremely broad for me.
I am looking forward for your next post, I’ll try to get the hang of it!
That is really fascinating, You are a very professional blogger.
I have joined your feed and stay up for searching for more of your magnificent post.
Additionally, I have shared your website in my social networks
Do you have any video of that? I’d love to find out some additional information.
Fine way of telling, and fastidious post to take data concerning
my presentation topic, which i am going to present
in university.
Hey very cool website!! Man .. Beautiful .. Amazing .. I’ll bookmark your website and take the feeds also…I am happy to find numerous useful info here in the post, we need work out more techniques in this regard, thanks for sharing. . . . . .
Awesome article.
Do you mind if I quote a few of your posts as long as I provide credit and sources back to
your site? My blog site is in the very same niche as yours and my visitors would truly benefit from a
lot of the information you provide here. Please let me know if
this okay with you. Many thanks!
There is certainly a great deal to find out about
this subject. I love all of the points you have
made.
Thanks for finally writing about >【BZOJ 4408】[FJOI2016] 神秘数 – Qizy’s Database <Loved it!
That is really fascinating, You’re a very professional blogger.
I have joined your feed and look ahead to searching for more of your fantastic post.
Also, I’ve shared your web site in my social networks
I quite like looking through an article that can make people think.
Also, thanks for permitting me to comment!
Its like you read my thoughts! You seem to know a lot about this, like you wrote the e book in it or something.
I feel that you simply can do with some % to
drive the message house a bit, however other than that, this is
magnificent blog. An excellent read. I’ll certainly be back.
Hey just wanted to give you a quick heads up. The words in your content
seem to be running off the screen in Safari. I’m not sure
if this is a formatting issue or something to do with internet browser compatibility but I figured I’d post to
let you know. The design look great though!
Hope you get the issue fixed soon. Many thanks
wonderful points altogether, you simply gained a brand new reader. What would you recommend in regards to your post that you made some days ago? Any positive?
Major thanks for the blog article.Really thank you!