题目传送门：http://uoj.ac/problem/213
原厂题解：http://c_sunshine.blog.uoj.ac/blog/1860
我发现这道题目，我写了30分的暴力，60分的乱搞，100分的乱搞QAQ
说一说100分的乱搞O(nlogn):
考虑每一个区间的右端点右移一格，左端点不动
那么区间mx要么变成最右边那个，要么不动
考虑计算最右边那货对于答案的贡献，实际上就是区间加减
于是线段树维护一下
其实搞到这里，O(n)的做法就很明显了
因为线段树那里，只需要区间加减，不需要支持中途询问
于是搞一个差分就可以把线段树给去掉
#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;
const int MAXN = 1000000+9;
const int MOD = 998244353;
int n,arr[MAXN],vout,que[MAXN],lft[MAXN],MX[MAXN],BUF[MAXN];
inline int read(){
char c=getchar(); int buf=0,f=1;
while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
return buf*f;
}
inline void prework(){
int tot = 0;
for (int i=1;i<=n;i++) {
while (tot && arr[que[tot]] < arr[i]) tot--;
BUF[1] = (BUF[1]+arr[i])%MOD;
BUF[i-que[tot]+1] = ((BUF[i-que[tot]+1] - arr[i]) % MOD + MOD ) %MOD;
lft[i] = i-que[tot]; que[++tot] = i;
} tot = 0; que[0] = n+1;
for (int i=n;i;i--) {
while (tot && arr[que[tot]] <= arr[i]) tot--;
if(tot) {
BUF[que[tot]-i+1] = ((BUF[que[tot]-i+1]-arr[i]) % MOD + MOD) % MOD;
BUF[que[tot]-i+lft[i]+1] = (BUF[que[tot]-i+lft[i]+1] + arr[i]) % MOD;
} que[++tot] = i;
}
for (int i=n;i;i--) MX[i] = max(MX[i+1], arr[i]);
}
inline void solve(){
int tmp = 0, delta = 0;
for (int i=1;i<=n;i++) {
delta = ((delta + BUF[i]) % MOD + MOD) % MOD;
tmp = ((tmp + delta) % MOD + MOD) % MOD;
vout ^= tmp;
tmp -= MX[n-i+1];
}
}
int main(){
n = read();
for (int i=1;i<=n;i++) arr[i] = read();
prework(); solve();
printf("%d\n",vout);
return 0;
}
好文章！666，学习了
Can I simply say what a comfort to discover somebody who genuinely knows what they are discussing on the web.
You actually realize how to bring an issue to light
and make it important. More and more people ought to check this out and understand this side of your story.
I can’t believe you are not more popular since you most certainly possess
the gift.
It is in reality a great and useful piece of info.
I’m glad that you just shared this useful information with us.
Please keep us informed like this. Thanks for sharing.
Hello! Do you use Twitter? I’d like to follow you if that would be okay.
I’m definitely enjoying your blog and look forward to new updates.
An impressive share! I have just forwarded this onto a coworker who has been conducting a little homework on this.
And he in fact ordered me dinner because I stumbled
upon it for him… lol. So let me reword this…. Thank YOU for the meal!!
But yeah, thanx for spending the time to talk about this issue
here on your internet site.
What’s up, its nice article concerning media print, we all be familiar
with media is a impressive source of facts.
No matter if some one searches for his vital thing, therefore he/she wants to be available that in detail, therefore that thing is maintained over here.
When I originally left a comment I appear to have clicked on the
-Notify me when new comments are added- checkbox and now every
time a comment is added I get 4 emails with the same comment.
Is there an easy method you are able to remove me from that service?
Thanks a lot!
Magnificent web site. Lots of helpful info here. I’m sending it to some friends ans also sharing in delicious.
And obviously, thanks in your effort!
Hi, i believe that i saw you visited my weblog so i came to go back the prefer?.I am attempting to to find things to improve my site!I
suppose its ok to make use of a few of your ideas!!
Howdy! This post could not be written any better! Reading through this post reminds me
of my previous room mate! He always kept talking about this.
I will forward this post to him. Fairly certain he will have
a good read. Thank you for sharing!
you are actually a good webmaster. The website loading velocity is amazing.
It seems that you are doing any distinctive trick. Also,
The contents are masterwork. you’ve done a great task on this matter!
After study a few of the blog posts on your website now, and I truly like your way of blogging. I bookmarked it to my bookmark website list and will be checking back soon. Pls check out my web site as well and let me know what you think.
Good blog you have got here.. It’s hard to find good quality writing
like yours nowadays. I seriously appreciate individuals
like you! Take care!!
Heya i am for the first time here. I found this board and I find It really useful & it helped me out a
lot. I hope to give something back and help others like you helped me.
Hi there, just wanted to tell you, I liked this post.
It was inspiring. Keep on posting!
Hi there would you mind letting me know which hosting company you’re using?
I’ve loaded your blog in 3 completely different browsers
and I must say this blog loads a lot quicker then most.
Can you suggest a good web hosting provider at a reasonable price?
Thanks, I appreciate it!
It’s difficult to find experienced people on this subject, but you seem like you know what you’re talking about!
Thanks
Good response in return of this difficulty with genuine arguments and explaining
everything concerning that.
I every time used to study paragraph in news papers but now as I am a user of web so from now I am using net
for articles, thanks to web.
bookmarked!!, I like your web site!
you’re actually a just right webmaster. The web site loading
pace is amazing. It kind of feels that you’re doing any unique trick.
Also, The contents are masterwork. you have performed a
excellent activity on this topic!
Heya just wanted to give you a quick heads up and
let you know a few of the pictures aren’t loading properly.
I’m not sure why but I think its a linking issue. I’ve tried it in two different browsers and both show the same outcome.