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

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4785
出题人传送门:http://jiruyi910387714.is-programmer.com/posts/209073.html
官方题解:https://pan.baidu.com/s/1dFGHFfr

解题报告

我们发现正常的代码是统计的前缀和
但劼的写法实际是统计后缀和
然后画一画发现,只有$l-1,r$这两个点被改到的时候才会影响答案

我们考虑询问区间是$[l,r]$,一个修改区间是$[a,b]$
那么如果$l,r \in [a,b]$则这个修改区间有$\frac{2}{b-a+1}$的可能影响到答案
如果$l,r$只有一个$\in [a,b]$那么这个修改区间有$\frac{1}{b-a+1}$的可能影响到答案
如果两个都不属于,其显然不会影响到答案

于是我们把修改操作看成二维平面上的点的话
每一个询问操作可以拆成三个矩阵的询问
这个是经典问题,可以用树套树/分治/K-d Tree来解决

至于怎么维护标记,直接做的话,我们可以看成矩阵乘法
因为这个转移矩阵非常特殊,搞一搞发现其不但满足结合律,还满足交换律,所以可以标记永久化
但还有更妙的做法:

我们可以搞一个类似生成函数的东西
设第$i$个操作有$p_i$的可能影响到当前询问,设两个端点被改变偶数次的概率为$a$,奇数次为$b$
那么最后$a-b=\prod\limits_{i}{(1-p_i)-p_i}$
为什么是对的呢?因为只有改变奇数次才会为奇数,而$-1$的奇数次方等于$-1$偶数次方等于$1$,所以刚好对上
又因为我们还知道$a+b=1$,所以$a = \frac{1+\prod\limits_{i}{(1-p_i)-p_i}}{2}$

另外的话,这题有一个坑点:如果$l-1=0$的话,我们需要特判
因为之前我们的推导基于$l-1$那个点记录的是一个后缀
而实际算法中我们我们默认$l-1$那个点的值为$0$,所以需要判断一下总操作次数奇偶
考试的时候就这一点没想到,血wa三小时,最后这题挂零

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;

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

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() {
	n = read(); m = read();
	for (int i=1,l,r,len,ret;i<=m;i++) {
		if (read() == 1) {
			l = read(); r = read(); 
			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 {
			l = read() - 1; r = read(); ret = 1;
			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;
}

89 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.
    In addition, the blog loads super quick for me on Firefox.
    Superb Blog!

  2. Nice 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 website loaded up as quickly as
    yours lol

  3. 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.

  4. 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.

  5. 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!

  6. 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.

  7. 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!

  8. 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.

  9. 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!

  10. 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.

  11. Hey there would you mind letting me know which hosting company you’re
    utilizing? I’ve loaded your blog in 3 completely different browsers and
    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!

  12. Hello, i read your blog occasionally and i own a
    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.

  13. 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.

  14. Have you ever thought about adding a little bit more than just your articles?
    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!

  15. 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.

  16. 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!

  17. 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

  18. 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!!

  19. 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

  20. Its like you read my mind! You appear to know so much about this, like you wrote the
    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.

  21. 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.

  22. 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

  23. 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.

  24. Hello there! This post couldn’t be written any better!
    Reading through this post reminds me of my old room
    mate! He always kept chatting about this. I will forward this
    write-up to him. Pretty sure he will have a good read.
    Thanks for sharing!

  25. 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?

  26. 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?

  27. 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.

  28. 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.

    P.S Apologies for getting off-topic but I had to ask!

  29. 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!

  30. That is a very good tip particularly to those fresh to the blogosphere.
    Simple but very accurate information… Many thanks for sharing this one.
    A must read post!

  31. 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!!

  32. 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!

  33. 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.

  34. 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
    subject. Well with your permission allow me to grab your RSS
    feed to keep up to date with forthcoming post. Thanks
    a million and please continue the enjoyable work.

  35. 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 😉

  36. 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?

  37. 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!

  38. 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!

  39. 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!

  40. Hello There. I found your blog the use of msn. This is a really smartly written article.
    I’ll be sure to bookmark it and come back to learn more of your helpful information. Thank you for the post.

    I will definitely comeback.

  41. 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.

  42. What you published was actually very reasonable.
    However, think about this, what if you were to write a awesome post title?

    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.
    You should peek at Yahoo’s home page and watch how
    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.

  43. 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.

  44. Admiring the dedication you put into your site and detailed
    information you provide. It’s awesome to come across a blog
    every once in a while that isn’t the same old rehashed material.
    Fantastic read! I’ve bookmarked your site and I’m adding your RSS feeds to my Google account.

  45. Hi fantastic blog! Does running a blog like
    this take a massive amount work? I’ve no understanding of programming but
    I had been hoping to start my own blog in the near future.
    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!

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

  47. 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
    people think about worries that they just don’t know about.
    You managed to hit the nail upon the top as well as defined out the whole thing without having side effect , people
    could take a signal. Will likely be back to get more.
    Thanks

发表评论

电子邮件地址不会被公开。 必填项已用*标注