相关链接
题目传送门：http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-statements.pdf
官方题解：http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-solutions.pdf
解题报告
这题又是一道多算法互补的题目
通过分类处理使复杂度达到$O((n+m)\sqrt{n})$
具体来讲是将以下两个算法结合：
1. 枚举右端点的值，若左端点的合法位置超过$\sqrt{n}$个
考虑每一个左右端点应该加减多少，使用前缀和技巧将复杂度优化到$O(n + m)$
具体细节不想写了，有点麻烦_(:з」∠)_
然后因为合法位置超过了$\sqrt{n}$个，所以这种情况至多出现$\sqrt{n}$个，复杂度符合要求2. 其他情况
因为左端点不超过$\sqrt{n}$个，所以可以排序之后依次处理
使用分块来维护左端点的值，单次修改是$\sqrt{n}$的，单次查询是$O(1)$的
Code
#include<bits/stdc++.h>
#define LL long long
#define UI unsigned int
using namespace std;
const int N = 150009;
const int MOD = 1073741824;
const int blk_sz = 800;
int n, m, k, a[N];
UI a1[N], ans[N], blk_tag[N], tag[N];
vector<int> num, pos_list[N];
vector<pair<int, int> > left_list[N], right_list[N];
struct Query{
int l, r, w;
inline bool operator < (const Query &QQQ) const {
return r > QQQ.r;
}
}q[N];
inline int read() {
char c = getchar();
int ret = 0, f = 1;
while (c < '0' || c > '9') {
f = c == '-'? -1: 1;
c = getchar();
}
while ('0' <= c && c <= '9') {
ret = ret * 10 + c - '0';
c = getchar();
}
return ret * f;
}
inline int find(int x) {
int l = 0, r = num.size() - 1, mid;
while (l <= r) {
mid = l + r >> 1;
if (num[mid] == x) {
return mid;
} else if (num[mid] < x) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return -1;
}
inline void solve(int A, int B) {
static UI a2[N], cur;
memset(a2, 0, sizeof(a2));
for (int i = 1; i <= n; i++) {
a2[i] = a2[i - 1] + (a[i] == num[B]);
}
cur = 0;
for (int i = n; i; i--) {
if (a[i] == num[B]) {
cur += a1[i];
}
if (a[i - 1] == num[A]) {
ans[i] += cur;
}
for (int j = 0; j < (int)left_list[i].size(); ++j) {
cur -= (UI)left_list[i][j].second * (a2[left_list[i][j].first] - a2[i - 1]);
}
}
memset(a2, 0, sizeof(a2));
for (int i = 1; i <= n; ++i) {
a2[i] = a2[i - 1] + (a[i - 1] == num[A]);
}
cur = 0;
for (int i = 1; i <= n; i++) {
if (a[i - 1] == num[A]) {
cur -= a1[i];
}
if (a[i] == num[B]) {
ans[i + 1] += cur;
}
for (int j = 0; j < (int)right_list[i].size(); ++j) {
cur += (UI)right_list[i][j].second * (a2[i] - a2[right_list[i][j].first - 1]);
}
}
}
int main() {
freopen("xor.in", "r", stdin);
freopen("xor.out", "w", stdout);
n = read(); m = read(); k = read();
num.push_back(0);
for (int i = 1; i <= n; ++i) {
a[i] = a[i - 1] ^ read();
num.push_back(a[i]);
}
sort(num.begin(), num.end());
num.resize(unique(num.begin(), num.end()) - num.begin());
for (int i = 0; i <= n; i++) {
int pp = find(a[i]);
pos_list[pp].push_back(i);
}
for (int i = 1, l, r, w; i <= m; ++i) {
l = q[i].l = read();
r = q[i].r = read();
w = q[i].w = read();
left_list[l].push_back(make_pair(r, w));
right_list[r].push_back(make_pair(l, w));
a1[l] += w;
a1[r + 1] -= w;
}
sort(q + 1, q + 1 + m);
for (int i = 1; i <= n; ++i) {
a1[i] += a1[i - 1];
}
for (int i = 0; i < (int)num.size(); i++) {
int r = i, l = find(num[i] ^ k);
if (l != -1 && (int)pos_list[l].size() > blk_sz) {
solve(l, r);
}
}
for (int r = n, cur = 0; r; r--) {
while (cur < m && q[cur + 1].r >= r) {
++cur;
for (int i = q[cur].l, lim = min(q[cur].r, (q[cur].l / blk_sz + 1) * blk_sz - 1); i <= lim; ++i) {
tag[i] += q[cur].w;
}
for (int i = q[cur].l / blk_sz + 1, lim = q[cur].r / blk_sz - 1; i <= lim; ++i) {
blk_tag[i] += q[cur].w;
}
for (int i = max(q[cur].r / blk_sz, q[cur].l / blk_sz + 1) * blk_sz; i <= q[cur].r; ++i) {
tag[i] += q[cur].w;
}
}
int t = find(a[r] ^ k);
if (t != -1 && (int)pos_list[t].size() <= blk_sz) {
for (int tt = 0; tt < (int)pos_list[t].size(); ++tt) {
int l = pos_list[t][tt] + 1;
if (l <= r) {
ans[l] += tag[l] + blk_tag[l / blk_sz];
ans[r + 1] -= tag[l] + blk_tag[l / blk_sz];
} else {
break;
}
}
}
}
for (int i = 1; i <= n; i++) {
ans[i] += ans[i - 1];
printf("%d ", ans[i] % MOD);
}
return 0;
}
978766 754514very good post, i undoubtedly enjoy this wonderful internet site, persist with it 82950
12972 719260Excellent post, thanks so a lot for sharing. Do you happen to have an RSS feed I can subscribe to? 260774
278904 24093Was koche ich heute – diese Frage stellen sich tag fuer tag viele Menschen. Und wir haben tag fuer tag die perfeckte Antwort darauf! Besuchen Sie uns auf unserer Webseite und lassen Sie sich von uns beraten . Wir freuen uns auf Sie! 515530
It’s a shame you don’t have a donate button! I’d certainly donate
to this superb blog! I suppose for now i’ll settle for bookmarking and adding your RSS feed to my Google
account. I look forward to new updates and will share this site with my Facebook group.
Chat soon!
Hello there, just became aware of your blog through Google, and found that it’s really informative.
I am going to watch out for brussels. I will appreciate if you continue this in future.
Lots of people will be benefited from your writing. Cheers!
Hey just wanted to give you a quick heads up. The text in your content seem to
be running off the screen in Ie. I’m not sure if this is
a formatting issue or something to do with web browser
compatibility but I figured I’d post to let you know.
The style and design look great though! Hope you get the problem fixed soon. Many
thanks
872834 569221You completed various good points there. I did a search on the theme and identified the majority of folks will consent along with your blog. 997855
909147 589792You got a extremely great internet site, Gladiola I discovered it via yahoo. 328112
347892 583205Thanks for the post, was an fascinating read. Curious as to how you came about that solution 514561
178150 258816Beging with the entire wales properly before just about any planking. Our own wales can easily compilation of calculated forums those thickness analysts could be the comparable to some of the shell planking along with a lot more significant damage so that they project soon after dark planking. planking 328942
2745 533555What cell phone browser is this website page optimized for Internet explorer? 651130
450394 515701Hey i just visited your web site for the first time and i genuinely liked it, i bookmarked it and is going to be back 150314
860157 349427i was just browsing along and came upon your internet site. just wantd to say fantastic job and this post actually helped me. 580852
230128 490675I think this web internet site has got quite fantastic indited written content articles . 477262
954419 480908You got a extremely excellent site, Glad I noticed it by means of yahoo. 556876
Helpful information. Lucky me I discovered your
web site unintentionally, and I am shocked why
this accident didn’t took place earlier! I bookmarked it.
Hola! I’ve been following your web site for some
time now and finally got the bravery to go ahead and give
you a shout out from Atascocita Texas! Just wanted to say keep up the good job!
Keep this going please, great job!
Hi there, after reading this amazing paragraph i am too cheerful to share my know-how here with
mates.
Hi! I’ve been reading your site for a while now and finally got the courage to go ahead and
give you a shout out from Lubbock Tx! Just wanted to say keep up the great work!
Write more, thats all I have to say. Literally, it seems as though you relied on the video to make your
point. You obviously know what youre talking about, why waste your intelligence on just posting videos to your weblog when you could
be giving us something informative to read?
I pay a quick visit everyday some websites and websites to read articles or reviews,
but this webpage gives feature based writing.
What’s up to every body, it’s my first go to see of this website; this web site carries awesome and truly excellent stuff
designed for readers.
Thanks very interesting blog!
I couldn’t resist commenting. Perfectly written!
Thanks in favor of sharing such a fastidious opinion, article
is nice, thats why i have read it completely
Hey, you used to write great, but the last several posts have been kinda boring… I miss your great writings. Past several posts are just a bit out of track! come on!
Thanks for finally writing about >【日常小测】异或与区间加 – Qizy’s Database <Loved it!
I’m now not sure where you’re getting your info, however great topic.
I must spend some time studying more or working out more. Thanks
for magnificent information I was on the lookout for this info for my mission.
Hello! I could have sworn I’ve visited this website before but after
looking at a few of the posts I realized
it’s new to me. Regardless, I’m certainly delighted I discovered it and I’ll be bookmarking it and checking back frequently!
Thanks for your marvelous posting! I seriously enjoyed reading it,
you may be a great author. I will be sure to bookmark your blog and will come
back very soon. I want to encourage yourself to continue your great
job, have a nice holiday weekend!
I visit day-to-day some sites and sites to read content, except this web
site provides quality based content.
This post is in fact a good one it assists new net viewers, who are wishing in favor of
blogging.
An impressive share! I have just forwarded this onto a friend who was doing a
little homework on this. And he in fact bought me lunch
simply because I discovered it for him… lol. So allow me to reword this….
Thank YOU for the meal!! But yeah, thanx for spending some time
to talk about this issue here on your blog.
I read this article fully concerning the resemblance of latest and preceding technologies, it’s
remarkable article.
My brother suggested I might like this blog.
He was entirely right. This post truly made my day.
You cann’t imagine simply how much time I had
spent for this information! Thanks!
This is a topic which is close to my heart… Best wishes!
Exactly where are your contact details though?
Howdy! Do you know if they make any plugins to protect against hackers?
I’m kinda paranoid about losing everything I’ve worked hard on. Any recommendations?
Hi there would you mind sharing which blog platform you’re using?
I’m planning to start my own blog soon but I’m having a tough time making
a decision between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your design and style seems
different then most blogs and I’m looking for something completely unique.
P.S Sorry for getting off-topic but I had to ask!
Greetings I am so grateful I found your webpage, I really found you
by accident, while I was researching on Askjeeve for something else, Nonetheless I am
here now and would just like to say thanks a lot for a remarkable
post and a all round interesting blog (I also love the theme/design), I don’t
have time to read through it all at the minute but I have book-marked
it and also included your RSS feeds, so when I have time I
will be back to read much more, Please do keep up the superb jo.
I am typically to blogging and i actually appreciate your content. The article has really peaks my interest. I am going to bookmark your web site and preserve checking for new information.