题目传送门：http://codeforces.com/problemset/problem/712/E
官方题解：http://codeforces.com/blog/entry/47050
这个题目想一想，还是挺好玩的
推导过程比较复杂，参见这里吧：http://codeforces.com/blog/entry/47050?#comment-314259
话说这次的官方题解真是辣鸡，还不如评论区容易懂…..
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 200000+9;
int n,m;
double 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 Segment_Tree{
#define SEG Segment_Tree
int ch[N][2],cnt,root,T1,L,R;
double t1[N],t2[N],T2,ans_tmp;
inline void maintain(int w){
t1[w] = t1[ch[w][0]] * t1[ch[w][1]];
t2[w] = t2[ch[w][0]] + t2[ch[w][1]] * t1[ch[w][0]];
}
void Build(int &w, int l, int r) {
w = ++cnt;
if (l == r) {
t1[w] = t2[w] = arr[l];
} else {
int mid = l + r + 1 >> 1;
Build(ch[w][0],l,mid-1);
Build(ch[w][1],mid,r);
maintain(w);
}
}
void modify(int w, int l, int r) {
if (l == r) {
t1[w] = t2[w] = T2;
} else {
int mid = l + r + 1 >> 1;
if (T1 < mid) modify(ch[w][0],l,mid-1);
else modify(ch[w][1],mid,r);
maintain(w);
}
}
inline void modify(int pos, double nv) {
T1 = pos; T2 = nv;
modify(root,1,n);
}
void query(int w, int l, int r) {
if (L <= l && r <= R) {
ans_tmp += t2[w] * T2;
T2 *= t1[w];
} else {
int mid = l + r + 1 >> 1;
if (L < mid) query(ch[w][0],l,mid-1);
if (mid <= R) query(ch[w][1],mid,r);
}
}
inline double query(int l, int r) {
ans_tmp = 0; T2 = 1;
L = l; R = r;
query(root,1,n);
return ans_tmp;
}
};
int main(){
n = read(); m = read();
for (int i=1,a,b;i<=n;i++) {
a = read(); b = read();
double tmp = (double)a/b;
arr[i] = (1 - tmp) / tmp;
}
SEG::Build(SEG::root,1,n);
for (int i=1,a,b,c,ty;i<=m;i++) {
ty = read(); a = read(); b = read();
if (ty == 1) {
c = read();
double tmp = (double)b/c;
SEG::modify(a,(1-tmp)/tmp);
} else {
double tmp = SEG::query(a,b);
tmp = min(1e20,tmp);
printf("%.10lf\n",1/(1+tmp));
}
}
return 0;
}
Attractive section of content. I just stumbled upon your web site and in accession capital to assert that I
get in fact enjoyed account your blog posts.
Any way I’ll be subscribing to your feeds and even I achievement you access consistently fast.
This blog was… how do I say it? Relevant!! Finally I
have found something which helped me. Thanks!
I was able to find good information from your blog posts.
I’ve learn several excellent stuff here. Certainly value bookmarking for revisiting.
I surprise how a lot attempt you place to make such a
great informative site.
Hi, i think that i saw you visited my website so i came to “return the favor”.I am trying to find things to enhance my site!I
suppose its ok to use a few of your ideas!!
I’m really loving the theme/design of your website.
Do you ever run into any browser compatibility issues? A handful
of my blog audience have complained about my blog not working correctly in Explorer but looks great
in Firefox. Do you have any suggestions to help fix this problem?
Hey there, I think your blog might be having browser compatibility
issues. When I look at your blog site in Safari, it looks fine but
when opening in Internet Explorer, it has some overlapping.
I just wanted to give you a quick heads up! Other then that, wonderful blog!
Pretty nice post. I just stumbled upon your weblog and wanted to say that I’ve really enjoyed browsing your blog
posts. After all I’ll be subscribing to your feed and I hope you write again soon!
Pretty great post. I just stumbled upon your weblog and wished to say that I’ve truly loved browsing your weblog
posts. After all I’ll be subscribing on your feed
and I am hoping you write again soon!
Oh my goodness! Incredible article dude! Thank you,
However I am experiencing troubles with your RSS.
I don’t understand why I cannot join it. Is there anybody else having identical RSS issues?
Anyone who knows the solution will you kindly respond? Thanx!!
We’re a group of volunteers and opening a new scheme in our community.
Your website offered us with valuable info to work on. You have done an impressive job and our entire
community will be grateful to you.
always i used to read smaller posts that also clear their motive, and that is also happening with this post which I am reading
here.
I could not refrain from commenting. Perfectly written!
Asking questions are actually good thing if you are not understanding
something totally, but this post offers pleasant understanding even.
It is the best time to make some plans for the long run and it
is time to be happy. I have learn this publish and if I may just I wish to suggest you few fascinating things or tips.
Perhaps you could write subsequent articles regarding this article.
I wish to learn more issues approximately it!
I am genuinely thankful to the owner of this website who has shared
this fantastic post at at this place.
I’m impressed, I have to admit. Rarely do I encounter a blog that’s both educative and entertaining, and without
a doubt, you have hit the nail on the head.
The problem is something that not enough folks are speaking intelligently
about. I’m very happy that I came across this during my search for something
concerning this. plenty of fish natalielise
This piece of writing will help the internet visitors for setting up new
website or even a weblog from start to end.
Excellent items from you, man. I’ve have in mind your stuff prior to and
you are just too excellent. I actually like what you have acquired right here,
certainly like what you are saying and the way
through which you assert it. You’re making it enjoyable
and you still take care of to keep it smart. I can not wait
to read much more from you. This is really a wonderful
site. natalielise pof
Great post but I was wanting to know if you could write a
litte more on this topic? I’d be very thankful if you
could elaborate a little bit further. Bless you!
My brother suggested I would possibly like this website.
He was totally right. This post actually made my day.
You can not consider just how a lot time I had spent for this info!
Thanks!
When some one searches for his required thing, therefore he/she wishes to be
available that in detail, therefore that thing is maintained over here.
Thanks to my father who told me regarding this weblog, this webpage
is in fact remarkable.
I was suggested this blog by my cousin. I am now not
certain whether this post is written through him
as nobody else know such special approximately my difficulty.
You are amazing! Thank you!
My spouse and I stumbled over here by a different page and thought I may as well check things
out. I like what I see so now i’m following you. Look
forward to looking over your web page yet again.
Do you have a spam problem on this website; I also am a blogger, and I was wondering your situation; many of us have created some nice practices and we
are looking to swap methods with others, please shoot me an e-mail if interested.
This is a very good tip especially to those fresh to the
blogosphere. Brief but very accurate information… Appreciate your sharing this one.
A must read article!
Hey very interesting blog!
My brother recommended I would possibly like
this blog. He was entirely right. This post truly made my day.
You cann’t believe just how so much time I had spent
for this information! Thanks!
Hello there! I could have sworn I’ve been to your blog before but after looking at a
few of the articles I realized it’s new to me. Nonetheless, I’m definitely delighted I stumbled upon it and I’ll be bookmarking it and checking back frequently!
I was recommended this web site by my cousin. I’m not sure whether this post
is written by him as nobody else know such detailed about my difficulty.
You are incredible! Thanks!
When I initially commented I seem to have clicked on the -Notify me
when new comments are added- checkbox and now each time a
comment is added I receive 4 emails with the exact same comment.
Perhaps there is an easy method you are able to remove
me from that service? Thanks a lot!
Thankfulness to my father who stated to me concerning this website, this web site is in fact remarkable.
I’m amazed, I have to admit. Seldom do I come across a blog
that’s both equally educative and entertaining, and
without a doubt, you have hit the nail on the head.
The problem is an issue that not enough folks are speaking intelligently about.
I am very happy I found this during my search for something
concerning this.
Good post. I learn something new and challenging on websites I stumbleupon every day.
It will always be useful to read through articles from other authors and use a little something from
other web sites.
Hi Dear, are you really visiting this website on a regular basis, if so
then you will absolutely take fastidious experience.
Why viewers still make use of to read news papers when in this
technological globe the whole thing is presented on net?
I’m gone to tell my little brother, that he should also
go to see this web site on regular basis to get updated from newest
news.
Hi there! I know this is kinda off topic nevertheless I’d figured I’d ask.
Would you be interested in exchanging links or maybe guest authoring a blog post
or vice-versa? My blog goes over a lot of the same topics as yours
and I feel we could greatly benefit from each other. If you
might be interested feel free to shoot me an e-mail.
I look forward to hearing from you! Excellent blog by
the way!
magnificent post, very informative. I ponder why the opposite experts of this sector do not notice this.
You should continue your writing. I am confident, you have a huge
readers’ base already!
Great beat ! I wish to apprentice while you amend your site, how could i subscribe for
a blog website? The account aided me a acceptable deal.
I had been a little bit acquainted of this your
broadcast provided bright clear idea
great post, very informative. I wonder why the other specialists of
this sector don’t realize this. You must proceed your writing.
I’m confident, you have a huge readers’ base already!
Hello! Someone in my Myspace group shared this site with us so I
came to look it over. I’m definitely loving the information. I’m bookmarking and will be tweeting this
to my followers! Exceptional blog and great design and style.
This design is incredible! You most certainly know how
to keep a reader entertained. Between your wit and your videos,
I was almost moved to start my own blog (well, almost…HaHa!) Excellent
job. I really loved what you had to say, and more than that, how you presented it.
Too cool!
It is the best time to make some plans for the future and it
is time to be happy. I’ve read this post and if I could I want to suggest you some
interesting things or advice. Perhaps you could write
next articles referring to this article. I wish to read even more things about it!
Hi, I do believe this is a great web site.
I stumbledupon it 😉 I’m going to come back once again since I saved as a favorite
it. Money and freedom is the best way to change, may you be rich and continue to guide other people.
Hi, of course this post is genuinely nice and I have learned lot of things from it about blogging.
thanks.
Hi there, I enjoy reading through your article. I wanted to write a little comment to support
you.
This is the right webpage for anyone who really wants to find out about this topic.
You realize a whole lot its almost hard to
argue with you (not that I personally will need to…HaHa).
You definitely put a brand new spin on a topic which has been written about
for ages. Wonderful stuff, just excellent!
Thanks for sharing such a pleasant thought, post is nice, thats why i
have read it completely
Today, I went to the beachfront with my children. I found a sea shell and gave it
to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.”
She put the shell to her ear and screamed. There was a hermit crab inside and it pinched her ear.
She never wants to go back! LoL I know this is entirely off topic but I had to tell someone!
Howdy! Someone in my Myspace group shared this site with us so
I came to give it a look. I’m definitely loving the information. I’m book-marking
and will be tweeting this to my followers! Exceptional
blog and wonderful style and design.
I think the admin of this web page is genuinely working hard for his website, as here every material is quality
based material.
Hi there, just wanted to say, I enjoyed this blog post.
It was funny. Keep on posting!
I’m extremely pleased to find this website. I want to to thank you for your
time for this wonderful read!! I definitely enjoyed every little bit of it and I have you bookmarked to look at new
things on your website.
I have been browsing online greater than three hours lately,
but I never found any fascinating article like yours.
It is pretty value enough for me. In my opinion, if all site owners and bloggers made just right content as you did,
the net might be a lot more helpful than ever before.
Woah! I’m really enjoying the template/theme of this blog.
It’s simple, yet effective. A lot of times it’s very difficult to get that “perfect balance” between user friendliness and visual
appeal. I must say that you’ve done a fantastic job with this.
Additionally, the blog loads very quick for
me on Firefox. Superb Blog!
What’s up to all, how is everything, I think every one is getting more from this web site,
and your views are nice designed for new visitors.
What’s up, everything is going fine here and ofcourse every one is sharing facts,
that’s really excellent, keep up writing.
Awesome post.
I know this website gives quality dependent posts and additional information, is there any other site which
gives these stuff in quality?
Good day very nice site!! Guy .. Excellent ..
Superb .. I’ll bookmark your site and take the feeds
also? I am glad to find numerous helpful info here in the submit, we’d like work out more
techniques in this regard, thank you for sharing.
. . . . .
These are genuinely great ideas in on the topic of blogging.
You have touched some good things here. Any way keep
up wrinting.
What’s up i am kavin, its my first time to commenting anywhere, when i read this piece of
writing i thought i could also make comment due to this
sensible paragraph.
If you would like to increase your familiarity just
keep visiting this web page and be updated with the hottest gossip posted here.
I visited several web pages but the audio feature for
audio songs present at this web page is in fact fabulous.
Pretty! This has been an extremely wonderful article. Thank you for providing these details.
The crux of your writing whilst appearing reasonable originally, did not work properly with me personally after some time. Somewhere throughout the paragraphs you were able to make me a believer but just for a short while. I still have a problem with your leaps in assumptions and one might do well to fill in those gaps. In the event that you can accomplish that, I would undoubtedly be fascinated.
My partner and I stumbled over here coming from a different page and
thought I may as well check things out. I like what I see so now i am following you.
Look forward to looking over your web page for a second time.
Thanks for every other informative web site.
Where else may I am getting that type of info written in such a perfect approach?
I have a venture that I am simply now operating
on, and I have been at the look out for such info.
This is really interesting, You’re a very skilled blogger.
I’ve joined your rss feed and look forward to seeking more of your fantastic post.
Also, I’ve shared your site in my social networks!
Does your website have a contact page? I’m having problems locating it but,
I’d like to shoot you an email. I’ve got some suggestions for your blog you might be interested in hearing.
Either way, great blog and I look forward to seeing it grow
over time.
Hi there! I understand this is sort of off-topic but I had to ask.
Does building a well-established website such as yours take a lot of work?
I am completely new to running a blog but I do write in my journal
every day. I’d like to start a blog so I can easily share my own experience and views online.
Please let me know if you have any kind of suggestions or tips for
brand new aspiring blog owners. Appreciate it!
Good information. Lucky me I found your blog by accident (stumbleupon).
I have book-marked it for later!
Hey There. I found your blog using msn. This is a really
well written article. I will make sure to bookmark it and return to read more of your useful information. Thanks for the post.
I will certainly comeback.
Usually I do not read post on blogs, however I wish to say that this write-up very
compelled me to check out and do so! Your writing style has
been amazed me. Thanks, very great article.
Hello mates, pleasant article and fastidious arguments commented
here, I am in fact enjoying by these.
Wow, this post is fastidious, my sister is analyzing these
kinds of things, thus I am going to tell her.
Some truly excellent info , Gladiola I noticed this.
Great, thanks for sharing this blog post. Fantastic.
I cannot thank you enough for the blog article. Cool.