# 【BZOJ 4785】[ZJOI 2017] 树状数组

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = 30000000;
const int MOD = 998244353;
const int REV = 499122177;

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;
}

int n,m,tot;
class Segment_Tree{
int cnt,root,AnsTmp,ch[M][2],prod[M][2];
public:
inline void modify(int x, int y, int v, bool t) {
modify(root, 1, n, x, y, v, t);
}
inline int query(int x1, int x2, int y1, int y2, bool t) {
if (x1 > x2 || y1 > y2) return 1;
AnsTmp = 1;
query(root, 1, n, x1, x2, y1, y2, t);
return (AnsTmp+MOD)%MOD;
}
private:
void modify(int &w, int l, int r, int x, int y, int v, bool t) { //X
if (!w) w = ++cnt; modify(prod[w][0], 1, n, y, v, t);
if (l < r) {
int mid = l + r + 1 >> 1;
if (x < mid) modify(ch[w][0], l, mid-1, x, y, v, t);
else modify(ch[w][1], mid, r, x, y, v, t);
}
}
void modify(int &w, int l, int r, int p, int v, bool t) { //Y
if (!w) w = ++cnt, prod[w][0] = prod[w][1] = 1;
prod[w][t] = (LL)prod[w][t] * v % MOD;
if (l < r) {
int mid = l + r + 1 >> 1;
if (p < mid) modify(ch[w][0], l, mid-1, p, v, t);
else modify(ch[w][1], mid, r, p, v, t);
}
}
void query(int w, int l, int r, int L, int R, int y1, int y2, bool t) { //X
if (!w) return;
if (L <= l && r <= R) query(prod[w][0], 1, n, y1, y2, t);
else {
int mid = l + r + 1 >> 1;
if (L < mid) query(ch[w][0], l, mid-1, L, R, y1, y2, t);
if (mid <= R) query(ch[w][1], mid, r, L, R, y1, y2, t);
}
}
void query(int w, int l, int r, int L, int R, bool t) { //Y
if (!w) return;
if (L <= l && r <= R) AnsTmp = (LL)AnsTmp * prod[w][t] % MOD;
else {
int mid = l + r + 1 >> 1;
if (L < mid) query(ch[w][0], l, mid-1, L, R, t);
if (mid <= R) query(ch[w][1], mid, r, L, R, t);
}
}
}SGT;

inline int Pow(int w, int t) {
int ret = 1;
for (;t;t>>=1,w=(LL)w*w%MOD)
if (t&1) ret=(LL)ret*w%MOD;
return ret;
}

int main() {
for (int i=1,l,r,len,ret;i<=m;i++) {
len = Pow(r-l+1, MOD-2); ++tot;
SGT.modify(l, r, (1 - (len * 2ll)) % MOD, 0);
SGT.modify(l, r, (1 - (len * 4ll)) % MOD, 1);
} else {
ret = (LL)ret * SGT.query(1, l, l, r - 1, 0) % MOD;
ret = (LL)ret * SGT.query(l+1, r, r, n, 0) % MOD;
ret = (LL)ret * SGT.query(1, l, r, n, 1) % MOD;
ret = (ret + 1ll) * REV % MOD;
if (!l&&(tot&1)) ret = (1 - ret) % MOD;
printf("%d\n",(ret+MOD)%MOD);
}
}
return 0;
}


## 87 thoughts to “【BZOJ 4785】[ZJOI 2017] 树状数组”

1. Woah! I’m really digging the template/theme of this website.
It’s simple, yet effective. A lot of times it’s very hard to get that “perfect balance” between superb usability and visual appearance.
I must say that you’ve done a excellent job with this.
Superb Blog!

2. I am genuinely grateful to the holder of this web site who has
shared this wonderful paragraph at here.

3. Nice blog here! Also your web site loads up very fast!
I wish my website loaded up as quickly as
yours lol

4. Hmm is anyone else encountering problems with the pictures
on this blog loading? I’m trying to determine if its a problem
on my end or if it’s the blog. Any feedback would be
greatly appreciated.

5. What’s up, I check your new stuff regularly. Your humoristic style is awesome, keep it up!

A design like yours with a few simple tweeks would really make my
blog stand out. Please let me know where you got your design.
Many thanks

7. I am sure this piece of writing has touched all the internet users,
its really really nice article on building up
new webpage.

8. Hi, Neat post. There’s a problem along with your web site in internet explorer,
may check this? IE nonetheless is the market leader and a large
component to other people will leave out your magnificent writing due to this
problem.

9. Greetings! Very useful advice in this particular article!
It is the little changes that will make the largest changes.
Thanks a lot for sharing!

10. Wow, marvelous blog layout! How long have you been blogging for?

you made blogging look easy. The overall look of your
site is great, as well as the content!

11. Hello, i think that i saw you visited my website thus i
came to “return the favor”.I am attempting to find things to enhance
my site!I suppose its ok to use a few of your ideas!!

12. Greate post. Keep writing such kind of information on your blog.
Im really impressed by your site.
Hey there, You have performed an incredible job.
I’ll certainly digg it and in my opinion recommend to my
friends. I’m confident they’ll be benefited from this web site.

13. Greetings, There’s no doubt that your blog could possibly be having web browser compatibility issues.
Whenever I take a look at your site in Safari, it
looks fine however, when opening in IE, it’s got some overlapping issues.
I merely wanted to provide you with a quick heads up! Besides that,
fantastic blog!

14. We are a group of volunteers and starting a new scheme in our community.
Your website provided us with valuable information to
work on. You have done an impressive job and our entire community will be grateful to you.

15. What i don’t understood is in reality how you’re no
longer really much more neatly-preferred than you may
be right now. You are very intelligent. You recognize thus
significantly when it comes to this topic, made me for my part imagine it
from a lot of various angles. Its like women and men aren’t interested except it’s
something to accomplish with Girl gaga! Your individual stuffs outstanding.
Always take care of it up!

16. Do you have a spam issue on this website; I also am a blogger, and
I was wanting to know your situation; many of us have developed some
nice procedures and we are looking to swap techniques with other
folks, please shoot me an email if interested.

17. This is my first time go to see at here and i am actually pleassant to read everthing at single place.

18. Hey there would you mind letting me know which hosting company you’re
I must say this blog loads a lot faster then most.

Can you suggest a good hosting provider at a honest price?

Thanks, I appreciate it!

similar one and i was just curious if you get a lot of spam comments?
If so how do you protect against it, any plugin or anything you can recommend?
I get so much lately it’s driving me crazy so any help is very
much appreciated.

20. If you desire to take a great deal from this article then you have to apply these techniques to your won blog.

21. This post offers clear idea designed for the new visitors of blogging, that genuinely
how to do blogging and site-building.

22. Very quickly this website will be famous amid all blogging and site-building visitors, due to it’s nice articles
or reviews

pof natalielise

24. Very good post! We will be linking to this great post on our website.
Keep up the great writing.

25. It’s very easy to find out any matter on web as compared to books, as I found this
paragraph at this website.

26. Great blog here! Also your web site loads up very fast!
What web host are you using? Can I get your affiliate link to your
host? I wish my site loaded up as fast as yours lol

27. My relatives every time say that I am wasting my time here at net,
however I know I am getting familiarity all the time by reading thes pleasant posts.

28. Hi there, i read your blog occasionally and i own a similar one and i was just wondering if you get a
lot of spam feedback? If so how do you prevent it,
any plugin or anything you can recommend? I get so much lately it’s driving
me crazy so any assistance is very much appreciated.

I mean, what you say is fundamental and all. Nevertheless think of
if you added some great graphics or videos to give your posts more, “pop”!
Your content is excellent but with pics and videos, this site could undeniably be
one of the most beneficial in its field. Excellent blog!

30. Thank you for the good writeup. It in fact was a amusement
However, how could we communicate? natalielise
pof

31. Thank you for some other magnificent article. The place else could anybody get
that kind of information in such an ideal manner of writing?
I’ve a presentation next week, and I’m at the search for such info.

32. Today, I went to the beach front with my kids. 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 totally off topic but I had to tell someone!

33. Definitely believe that which you stated. Your favorite reason seemed to be on the web the easiest thing to be aware of.
I say to you, I certainly get irked while people think about worries that they just do not know
about. You managed to hit the nail upon the top and also defined out the
whole thing without having side effect , people could take a signal.

Will probably be back to get more. Thanks

34. An intriguing discussion is worth comment. I believe that you need to publish more about
this subject matter, it might not be a taboo subject
but generally people don’t talk about these subjects.
To the next! All the best!!

35. When some one searches for his vital thing, so he/she needs to be available that in detail, thus that thing
is maintained over here.

36. What’s up to all, how is the whole thing, I think every one is getting more
from this website, and your views are fastidious in support of
new users.

37. Undeniably believe that which you stated. Your favorite reason seemed to
be on the web the simplest thing to be aware of. I say to you, I definitely get irked while people consider
worries that they plainly do not know about.
You managed to hit the nail upon the top as well as
defined out the whole thing without having side-effects , people
can take a signal. Will probably be back to get more.
Thanks

book in it or something. I think that you could do with
some pics to drive the message home a little
bit, but instead of that, this is excellent blog. A great read.
I will definitely be back.

39. Thanks for sharing such a fastidious opinion, paragraph
is fastidious, thats why i have read it entirely

40. Howdy, i read your blog from time to time and i own a similar one
and i was just wondering if you get a lot of spam responses?
If so how do you prevent it, any plugin or anything you can advise?

I get so much lately it’s driving me mad so any help is very much appreciated.

41. Excellent beat ! I would like to apprentice whilst you amend your site, how can i subscribe for
a weblog site? The account aided me a applicable deal.
I have been a little bit acquainted of this your broadcast offered shiny transparent idea

42. I am regular reader, how are you everybody? This paragraph posted at
this web page is truly fastidious.

43. Hi, I do believe this is an excellent website. I stumbledupon it 😉 I
am going to revisit once again since i have saved as a favorite it.

Money and freedom is the best way to change, may you be rich and continue
to help other people.

44. Hello there! This post couldn’t be written any better!
Reading through this post reminds me of my old room
write-up to him. Pretty sure he will have a good read.
Thanks for sharing!

45. I am curious to find out what blog system you’re using?
I’m having some minor security issues with my latest site
and I’d like to find something more safe. Do you have any solutions?

46. I’m really loving the theme/design of your blog.
Do you ever run into any web browser compatibility issues?
A few of my blog readers have complained about my site not working correctly in Explorer but
looks great in Opera. Do you have any solutions to help fix this problem?

47. whoah this weblog is great i love studying your posts.
Stay up the good work! You know, lots of individuals are hunting round for this information, you could help
them greatly.

48. I have read so many content on the topic of
the blogger lovers but this piece of writing is actually a
fastidious paragraph, keep it up.

49. Hey 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 selecting between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your design seems different then most blogs and I’m looking for something unique.

50. I do not even know the way I ended up here, however I believed this post was once good.
I do not recognise who you are but definitely you are going to a well-known blogger should you aren’t already.
Cheers!

51. That is a very good tip particularly to those fresh to the blogosphere.
Simple but very accurate information… Many thanks for sharing this one.

52. Right now it looks like Expression Engine is the preferred blogging
platform available right now. (from what I’ve read)
Is that what you are using on your blog?

53. Hello, 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!!

54. Thanks to my father who stated to me regarding this webpage, this webpage is actually remarkable.

55. Hurrah! At last I got a web site from where I know
how to really obtain useful facts concerning my study and knowledge.

56. Greetings! I know this is kind of off topic but I was wondering if you knew where I could get 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!

57. Hey there! I know this is kind of off topic but I was wondering which blog platform are you
using for this website? I’m getting fed up of WordPress because I’ve
had problems 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.

58. Just want to say your article is as surprising. The clarity in your post is
simply excellent and i can assume you’re an expert on this
feed to keep up to date with forthcoming post. Thanks
a million and please continue the enjoyable work.

59. Hi, yup this piece of writing is genuinely fastidious and I have learned lot of things from
it on the topic of blogging. thanks.

60. I have to thank you for the efforts you have put
in penning this blog. I really hope to view the same high-grade content by you later on as well.

In fact, your creative writing abilities has encouraged me
to get my own site now 😉

61. Appreciate this post. Will try it out.

62. I’m really enjoying the theme/design of your web site.

Do you ever run into any browser compatibility problems?
A handful of my blog audience have complained about my website
not working correctly in Explorer but looks great in Chrome.
Do you have any suggestions to help fix this issue?

63. This text is invaluable. Where can I find out more?

64. Do you mind if I quote a few of your posts as long as I provide credit and sources back to your site?
My website is in the exact same niche as yours and my
users would really benefit from some of the information you provide here.
Please let me know if this okay with you. Many thanks!

65. For the reason that the admin of this web site is working,
no question very rapidly it will be renowned,
due to its feature contents.

66. If you are going for best contents like myself,
only go to see this site everyday as it provides quality
contents, thanks

67. What i don’t understood is if truth be told how you’re now not actually a lot more smartly-favored than you might be now.
You are very intelligent. You know thus significantly in relation to this matter, made me
individually believe it from numerous numerous
angles. Its like women and men aren’t involved except it’s one
thing to do with Girl gaga! Your own stuffs excellent. At all
times take care of it up!

68. Pretty! This was a really wonderful post. Thank you for supplying
this information.

69. Thanks for sharing such a good thinking, post is fastidious,
thats why i have read it fully

70. Hurrah, that’s what I was searching for, what a information! present here
at this web site, thanks admin of this web page.

71. Those are yours alright! . We at least need to get these people stealing images to start blogging! They probably just did a image search and grabbed them. They look good though!

72. I’m gone to inform my little brother, that he should also
pay a visit this website on regular basis to get updated
from hottest news update.

73. This post will help the internet visitors for creating new blog or even a blog from start to end.

74. Hello There. I found your blog the use of msn. This is a really smartly written article.

I will definitely comeback.

75. Hi to every one, it’s actually a fastidious
for me to go to see this site, it consists
of important Information.

76. I constantly emailed this web site post page to
all my associates, since if like to read it after that my contacts
will too.

77. Hey! Someone in my Facebook group shared this site with
us so I came to take a look. I’m definitely loving the information. I’m bookmarking and will be tweeting this to
my followers! Exceptional blog and excellent design and style.

78. What you published was actually very reasonable.

I am not suggesting your information isn’t good., however what if you added something to maybe grab folk’s attention? I mean 【BZOJ 4785】[ZJOI 2017] 树状数组 – Qizy's Database is kinda vanilla.
they create article headlines to get viewers to click.
You might add a related video or a picture or two to get readers interested about everything’ve written.
Just my opinion, it would make your posts a little livelier.

79. I like what you guys tend to be up too. Such clever work
and reporting! Keep up the amazing works guys I’ve included you guys to my own blogroll.

information you provide. It’s awesome to come across a blog
every once in a while that isn’t the same old rehashed material.

81. Hi fantastic blog! Does running a blog like
this take a massive amount work? I’ve no understanding of programming but
Anyhow, if you have any ideas or techniques for
new blog owners please share. I know this is off topic but
I simply wanted to ask. Kudos!

82. Thanks for sharing your thoughts. I truly appreciate your efforts and I am waiting for your further
post thanks once again.

What host are you using? Can I get your affiliate

84. Undeniably believe that which you said. Your favorite
reason seemed to be on the internet the easiest thing
to be aware of. I say to you, I definitely get irked while