【BZOJ 4540】[HNOI2016] 序列

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4540
数据生成器:http://paste.ubuntu.com/23631812/
神犇题解-线段树:http://blog.csdn.net/qq_34637390/article/details/51313126
神犇题解-莫队:https://blog.sengxian.com/solutions/bzoj-4540

解题报告

这题好神啊!莫队和线段树的做法都好神啊!

1. 莫队做法

我们只需要考虑如何O(1)进行转移。
因为是转移,所以一端是固定的,不妨设固定的是左端。
现在从左向右考虑右端点,不难发现:最小值不增(如下图所示)

通过观察我们还可以发现:除了第④段,其他几段的长度都是固定的
于是我们先预处理一下相关信息,对于第④段这种进行特殊处理。
因为第④段这货是l~r中的最小值,所以我们搞一个RMQ就可以特殊处理啦!
这样一来,转移就可以做到O(n),于是就可以上O(n^1.5)的莫队辣!

2. 线段树做法

因为此题和BZOJ_4262 一毛一样,所以就不单独写了。
这里有一份很好的题解,强烈推荐:http://blog.csdn.net/qq_34637390/article/details/51313126

Code (莫队version)

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

const int N = 100000+9;
const int INF = 2e9;

struct Query{
	int l,r,blk,num;
	inline bool operator < (const Query &B) const {
		return blk < B.blk || (blk == B.blk && r < B.r);
	}
}q[N];
int n,m,sqr,top,val[N],stk[N],pos[N],lft[N],rit[N];
LL vout[N],sum_right[N],sum_left[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 Sparse_Table{
	#define ST Sparse_Table
	int sur[N*3][20],arr[N*3][20],POW[20],log[N];
	
	inline void init() {
		POW[0] = 1;
		for (int i=1;i<=17;i++) 
			POW[i] = POW[i-1] << 1;
		for (int i=1,w=1;i<=n;w=1,++i) 
			while (w * 2 <= i) w <<= 1, log[i]++;
		
		for (int i=1;i<=n;i++) {
			arr[i][0] = val[i];
			sur[i][0] = i;
		}
		for (int j=1,cur=1;j<=17;j++,cur<<=1) {
			for (int i=1;i<=n;i++) {
				if (arr[i][j-1] < arr[i+cur][j-1]) {
					arr[i][j] = arr[i][j-1];
					sur[i][j] = sur[i][j-1];
				} else {
					arr[i][j] = arr[i+cur][j-1];
					sur[i][j] = sur[i+cur][j-1];
				}
			}
		}
	}
	
	inline int query(int l, int r) {
		int w = log[r-l+1];
		if (arr[l][w] < arr[r-POW[w]+1][w]) return sur[l][w];
		else return sur[r-POW[w]+1][w];
	}
};

inline LL move_right(int l, int r) {
	int p = ST::query(l, r);
	return sum_left[r] - sum_left[p] + (LL)val[p] * (p - l + 1);
}

inline LL move_left(int l, int r) {
	int p = ST::query(l, r); 
	return sum_right[l] - sum_right[p] + (LL)val[p] * (r - p + 1);
}

inline void prework() {
	stk[top = 0] = -INF;
	for (int i=1;i<=n;i++) {
		while (stk[top] > val[i]) top--;
		lft[i] = pos[top];
		sum_left[i] = sum_left[pos[top]] + (LL)(i-pos[top]) * val[i]; 
		stk[++top] = val[i];
		pos[top] = i;
	}
	
	pos[top = 0] = n+1;
	for (int i=n;i;i--) {
		while (stk[top] >= val[i]) top--;
		rit[i] = pos[top];
		sum_right[i] = sum_right[pos[top]] + (LL)(pos[top]-i) * val[i];
		stk[++top] = val[i];
		pos[top] = i;
	}
	
	ST::init();
}

int main(){
	n = read(); m = read();
	sqr = sqrt(n);
	for (int i=1;i<=n;i++)
		val[i] = read();
	prework();
	for (int i=1;i<=m;i++) {
		q[i].num = i;
		q[i].l = read(); 
		q[i].r = read();
		q[i].blk = q[i].l / sqr;
	}
	sort(q+1, q+1+m);
	
	LL cur = val[1];
	for (int k=1,l=1,r=1;k<=m;k++) {
		while (r < q[k].r) cur += move_right(l,r+1), r++;
		while (r > q[k].r) cur -= move_right(l,r), r--;
		while (l < q[k].l) cur -= move_left(l,r), l++;
		while (l > q[k].l) cur += move_left(l-1,r), l--;
		vout[q[k].num] = cur;
	}
	
	for (int i=1;i<=m;i++) 
		printf("%lld\n",vout[i]);
	return 0;
}

ps:这一份代码并不能处理值为负数的情况,至于为什么:我也普吉岛 QwQ

—————————— UPD 2017.2.2 ——————————
这题今天重新想的时候,想到了一个$O(nlog^2n)$的算法
虽然时间复杂度稍高,但思维复杂度和编程复杂度都相对较低

设$l_i$为第i个数离左边第一个比他小的数的距离,$r_i$同理
于是询问整个序列的话,答案就是 $\sum\limits_{i = 1}^n {{a_i} \times {l_i} \times {r_i}} $
然后仍然考虑离线,将询问排序依次做。
对于每一个数,其贡献有三种情况:
1. $l_i$,$r_i$都没有被询问限制
2. 有一个被限制
3. 有两个被限制
于是我们就可以搞一个树套树套树,把这三种情况分别计算即可
复杂度:$O(nlog^3n)$

但我们考虑离线之后,右端点逐渐右移,于是我们搞一个队列什么的维护一下
然后就搞一个树套树维护左端点就好,复杂度$O(nlog^2n)$

318 thoughts to “【BZOJ 4540】[HNOI2016] 序列”

  1. Hi, I believe your website may be having web browser compatibility
    issues. When I take a look at your blog in Safari, it looks fine but
    when opening in IE, it has some overlapping issues. I merely wanted to give you a quick
    heads up! Aside from that, fantastic website!

  2. Hello, i think that i saw you visited my weblog so i came to “return the favor”.I’m attempting to find things to enhance my website!I suppose its ok to use some of your ideas!!

  3. Hi, Neat post. There is a problem with your web site in web explorer,
    may test this? IE nonetheless is the marketplace leader and a big section of other people
    will pass over your great writing due to this
    problem.

  4. Hi, i feel that i noticed you visited my site so i came to go back the
    prefer?.I am trying to find things to enhance my site!I guess its adequate to make use of some of your ideas!!

  5. Wonderful blog! I found it while browsing on Yahoo News.

    Do you have any suggestions on how to get listed in Yahoo News?
    I’ve been trying for a while but I never seem to get there!
    Thanks

  6. We are a group of volunteers and starting a new scheme in our community.
    Your web site offered us with valuable info to work on. You’ve done an impressive job and our entire community will
    be grateful to you.

  7. It’s a pity you don’t have a donate button! I’d
    definitely donate to this excellent blog! I guess for now i’ll settle for book-marking and adding your RSS feed to
    my Google account. I look forward to new updates and will talk about this website with my
    Facebook group. Talk soon!

  8. What’s Happening i am new to this, I stumbled upon this I have discovered It absolutely
    useful and it has aided me out loads. I hope to give a contribution &
    assist different users like its helped me.

    Good job.

  9. I’m impressed, I have to admit. Seldom do I encounter a blog that’s both educative and amusing, 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.
    Now i’m very happy that I came across this during my search
    for something concerning this.

  10. An impressive share! I’ve just forwarded this onto a friend who was conducting a little research
    on this. And he actually bought me lunch simply because I stumbled upon it for
    him… lol. So let me reword this…. Thanks for the meal!!

    But yeah, thanx for spending time to discuss this topic here on your site.

  11. It’s a pity you don’t have a donate button! I’d certainly donate
    to this brilliant blog! I suppose for now i’ll settle for book-marking 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!

  12. you are actually a excellent webmaster. The website loading speed is incredible.
    It seems that you’re doing any distinctive trick. Also, The contents are masterwork.
    you have performed a magnificent activity on this matter!

  13. Hi! This is my first comment here so I just wanted to give a quick shout out and say I really enjoy reading your posts.
    Can you recommend any other blogs/websites/forums that deal with the same subjects?
    Thank you! plenty of fish natalielise

  14. An outstanding share! I have just forwarded this onto a friend
    who had been doing a little homework on this. And he in fact ordered me
    breakfast simply because I found it for him…

    lol. So let me reword this…. Thanks for the meal!!
    But yeah, thanx for spending the time to discuss this subject here on your site.

  15. 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 will try to get the hang of it!

  16. Excellent post. Keep posting such kind of information on your page.

    Im really impressed by your blog.
    Hi there, You’ve performed a great job. I will definitely digg
    it and individually recommend to my friends.
    I’m sure they will be benefited from this web
    site.

  17. Excellent post. I was checking continuously this
    blog and I’m impressed! Very useful information specifically the last part 🙂 I care for such info a
    lot. I was looking for this certain information for a long time.
    Thank you and good luck.

  18. I truly love your website.. Great colors & theme. Did you develop this website yourself?

    Please reply back as I’m hoping to create my very own website and would like to find out where you got this from
    or what the theme is called. Cheers!

  19. you are actually a good webmaster. The web site loading velocity
    is amazing. It seems that you are doing any unique
    trick. In addition, The contents are masterpiece.
    you’ve performed a great activity in this subject!

  20. I believe that is among the so much significant information for me.
    And i am glad studying your article. But wanna observation on some normal issues, The website style is wonderful, the articles
    is actually great : D. Excellent job, cheers

  21. Attractive part of content. I simply stumbled upon your blog and in accession capital to claim that I get in fact enjoyed account your weblog posts.
    Anyway I will be subscribing for your augment and
    even I fulfillment you get admission to constantly quickly.

  22. I’m not that much of a online reader to be honest but
    your sites really nice, keep it up! I’ll
    go ahead and bookmark your website to come back later on. All
    the best

  23. Thanks for some other informative site. The place else could I get that kind of info written in such an ideal approach?
    I have a project that I am simply now working on, and
    I’ve been at the glance out for such information.

  24. I blog often and I really thank you for your information. This great article has truly peaked my interest.
    I am going to bookmark your blog and keep checking for new information about once per
    week. I subscribed to your RSS feed as well.

  25. When I originally commented I seem to have clicked on the -Notify me when new comments are added-
    checkbox and now every time a comment is added I get four emails with the exact
    same comment. Is there a means you are able to remove me from
    that service? Kudos!

  26. I was curious if you ever thought of changing the structure of your site?
    Its very well written; I love what youve got to say. But maybe you could a little more in the way of content so people could connect with it better.
    Youve got an awful lot of text for only having
    one or two images. Maybe you could space it out better?

  27. You are so cool! I don’t think I’ve read anything like this before.
    So nice to find someone with some unique thoughts on this subject.
    Seriously.. thanks for starting this up. This site is something that’s needed on the internet, someone with a bit of originality!

  28. Ahaa, its fastidious dialogue on the topic of this paragraph
    at this place at this weblog, I have read all that, so now me also commenting at this place.

  29. Wonderful blog! I found it while searching on Yahoo News.
    Do you have any tips on how to get listed in Yahoo News?
    I’ve been trying for a while but I never seem to get there!
    Thanks

  30. I was recommended this blog by my cousin. I am not sure whether this post is written by him as no one else know such detailed about my difficulty. You are incredible! Thanks!

  31. Yesterday, while I was at work, my sister stole my iPad and tested to see if it
    can survive a 25 foot drop, just so she can be a youtube sensation.
    My apple ipad is now destroyed and she has 83
    views. I know this is totally off topic but I had to share it with someone!

  32. “4 Songs for the Club” Is a 4 song CD-EP from B-Rock, For Dj’s and Bars and Dance clubs ..”Dance”Features Rockman doing the electronic Vocals on the Chorus. A hand clapping song to get people on tha dance floor ….”Mix It With Tha Water”. Features B-Rocks Team member Pif .. Tha song is an urban street tale with a great Trap Beat….”I Like It Straight” is Bound to be a New Club/ Bar Anthem for the DJ’s to get the crowds up on their feet and to get another drink..LOL…and “Crack Them bottle (Get Fucked Up)” well that’s a story that all party goers live on the weekend! … 4 Dance Hits 4 tha Club.. a great EP for any DJ to have

  33. Hi there! This article could not be written any better!
    Looking at this post reminds me of my previous roommate! He constantly kept preaching about this.
    I’ll send this information to him. Fairly certain he will have
    a very good read. Thanks for sharing!

  34. Hi, I do think this is a great blog. I stumbledupon it 😉 I may return yet again since
    i have saved as a favorite it. Money and freedom is the greatest way to change,
    may you be rich and continue to help others.

  35. Thanks for the good writeup. It actually was a amusement account it.
    Glance advanced to far added agreeable from you! However, how can we keep up a correspondence?

  36. Wow, fantastic blog layout! How long have you been blogging
    for? you make blogging look easy. The overall
    look of your web site is magnificent, as well as the content!

  37. I got what you intend, appreciate it for putting up.Woh I am glad to find this website through google. “Success is dependent on effort.” by Sophocles.

  38. *Hey There. I found your blog using msn. This is an extremely well written article. I’ll be sure to bookmark it and return to read more of your useful info. Thanks for the post. I’ll definitely comeback.

  39. Hello There. I found your blog using msn. This is a very well written article. I’ll be sure to bookmark it and come back to read more of your useful info. Thanks for the post. I’ll certainly return.

  40. You can certainly see your skills within the article you write.The world hopes for even more passionate writers such as you who aren’t afraid tomention how they believe. Always follow your heart.

  41. Hello! I could have sworn I’ve been to this site before but after going through a few of the posts I realizedit’s new to me. Anyhow, I’m certainly happy I stumbled upon it and I’llbe bookmarking it and checking back regularly!

  42. Simply wish to say your article is as astonishing. The clearness to your post is simply spectacular and i could think you are a professional in this subject. Well with your permission allow me to snatch your RSS feed to stay updated with coming near near post. Thank you 1,000,000 and please continue the rewarding work.

  43. Batıkent nakliyat, Batıkent evden eve nakliyat ve Batıkent saatlik nakliyat ihtiyaçlarınızda daima yanınızda olmaktan mutluluk duymaktayız. Bizleri arayarak taşınma talebinizi tarafımıza iletmeniz yeterli olacaktır. Sizlere üst düzey kaliteli hizmet sunacağımızdan hiç kuşkunuz olmasın.

  44. This is very interesting, You’re a very skilled blogger. I have joined your rss feed and look forward to seeking more of your excellent post. Also, I have shared your web site in my social networks!

  45. I will immediately clutch your rss as I can’t to find your e-mail subscription link or e-newsletter service. Do you’ve any? Kindly allow me understand in order that I may just subscribe. Thanks.|

  46. Superb website you have here but I was curious about if you knew of any user discussion forums that cover the same topics discussed here? I’d really love to be a part of community where I can get opinions from other knowledgeable people that share the same interest. If you have any recommendations, please let me know. Thank you!|

  47. Hey there this is kinda of off topic but I was wondering if blogs use WYSIWYG editors or if you have to manually code with HTML. I’m starting a blog soon but have no coding expertise so I wanted to get advice from someone with experience. Any help would be enormously appreciated!|

  48. Hello there! This post couldn’t be written any better! Reading through this post reminds me of my good old room mate! He always kept talking about this. I will forward this page to him. Pretty sure he will have a good read. Thank you for sharing!|

  49. Thanks for any other wonderful article. Where else could anyone get that kind of information in such an ideal means of writing? I have a presentation next week, and I’m on the search for such info.|

  50. Hi there, just turned into aware of your blog through Google, and located that it is truly informative. I am gonna watch out for brussels. I will appreciate if you proceed this in future. Many other people shall be benefited out of your writing. Cheers!|

  51. After I initially commented I appear 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. Is there a means you are able to remove me from that service? Many thanks!|

  52. Greetings from Carolina! I’m bored to tears at work so I decided to browse your site on my iphone during lunch break. I enjoy the knowledge you provide here and can’t wait to take a look when I get home. I’m shocked at how fast your blog loaded on my cell phone .. I’m not even using WIFI, just 3G .. Anyhow, great blog!|

  53. einnahojbuty melissa sklep purple beaded dress vestidos de graduacion cortos para primaria modelos de sandalias plataformas altas mens nike dallas cowboys 22 emmitt smith limited olivecamo 2017 salute to service nfl jersey tenis贸wki lacoste bia艂e damskie sk贸rz…

  54. Just wish to say your article is as amazing. The clarity for your submit is simply cool and i could think you’re a professional on this subject. Well along with your permission allow me to snatch your RSS feed to stay up to date with forthcoming post. Thanks a million and please carry on the gratifying work.|

  55. Simply wish to say your article is as astonishing. The clarity in your post is simply cool and i can assume you are an expert on this subject. Well with your permission allow me to grab your feed to keep up to date with forthcoming post. Thanks a million and please carry on the gratifying work.|

  56. You actually make it seem so easy with your presentation but I find this matter to be really something that I think I would never understand. It seems too complicated and very broad for me. I’m looking forward for your next post, I’ll try to get the hang of it!|

Leave a Reply

Your email address will not be published. Required fields are marked *