首页 > 其他分享 >洛谷P9533 区间翻转区间异或和 题解

洛谷P9533 区间翻转区间异或和 题解

时间:2023-08-14 09:15:03浏览次数:40  
标签:洛谷 题解 sum bigoplus 区间 oplus 翻转 灵异

原题:洛谷P9533

一道性质题

不难发现,区间翻转操作是没有用的(虽然比赛的时候想了好久www)

首先,区间翻转要想对答案有贡献,一定是下边这种情况:

三个连续的区间:\(A~|~B~|~C\)

满足:\(B \oplus C=0,A \oplus C=0\)。

将 \(B∪C\) 这个灵异区间进行翻转,使 \(A\) 和 \(C\) 合并到一起,会增加一个灵异区间 \(A∪C\)。

但是,如果 \(B \oplus C=0,A \oplus C=0\) ,那么 也有\(A \oplus B=0\)。

因为:若 \(B \oplus C=0,A \oplus C=0\),则 \(\bigoplus B=\bigoplus C,\bigoplus A=\bigoplus C\)。

所以 \(\bigoplus A=\bigoplus B\),即 \(A \oplus B=0\)。

所以翻转前 \(A∪B\) 也是灵异区间,而反转后这个灵异区间就没有了。

所以区间翻转实际上是没用的。


然后就好写了,统计原数组的灵异区间即可

原理很简单:维护一个异或前缀和 \(sum\),并用 \(cnt_i\) 记录前缀和为 \(i\) 出现的次数。

比如如果 \(sum_i=sum_j=x\),则区间 \([i+1,j]\) 的异或和为0,即为灵异区间。

且 若也有 \(sum_k=x(i<j<k)\),则区间 \([i+1,k]\) 中共有 \(2+1=3\) 个灵异区间(\([i+1,j],[j+1,k],[i+1,k]\))。

即若前缀和 \(x\) 出现了 \(m\) 次,则灵异区间有 \(1+2+3+...+m=m(m-1)/2\) 个

我们再用 \(a\) 数组记录每种不同的前缀和,遍历 \(a\) 数组计算并统计灵异区间数量即可。

还要特殊处理一下 \(0\),很简单,\(sum\) 的初值是 \(0\),我们把这个 \(0\) 也计入计算即可

n=read();
cnt[0]=1;a[++tot]=0;
while(n--)
{
    sum^=read();
    if(!m[sum])	a[++tot]=sum;
    cnt[sum]++;
}
for(reg int i=1;i<=tot;i=-~i)	ans+=cnt[a[i]]*(cnt[a[i]]-1)/2;
printf("%lld",ans);

标签:洛谷,题解,sum,bigoplus,区间,oplus,翻转,灵异
From: https://www.cnblogs.com/sorato/p/17627729.html

相关文章

  • 华为OD机试-区间叠加
       importjava.util.ArrayList;importjava.util.TreeMap;importjava.util.stream.IntStream;publicclassMain{publicstaticvoidmain(String[]args){Integer[][]lines=newInteger[5][2];lines[0]=newInteger[]{1,4};......
  • 2023年多校联训NOIP层测试7+【LGR-149-Div.3】洛谷基础赛 #2 & qw Round -1
    2023年多校联训NOIP层测试7,集训欢乐赛,绝对欢乐,童叟无欺赛时在回家的路上+睡觉,所以没打。\(T1\)近似ybtOJ2049:【例5.19】字符串判等本题少了对空格的判断,水题。PS:题面和题解中都写了文件输入输出,测评时没有文件输入输出是几个意思,艹。#include<bits/stdc++.h>usingname......
  • 【题解】Educational Codeforces Round 146(CF1814)
    而且怎么感觉E,F比D要简单很多,大概是因为比较套路吧[惊恐]A.Coins题目描述:本题一共有\(t\)组数据。每组数据包含两个整数\(n\)和\(k\),如果存在两个非负整数\(x,y\),满足\(2\timesx+k\timesy=n\),输出YES,否则输出NO(yes,Yes,NO,nO均可)。题目分析:注意到\(y\)可......
  • CF992E 题解
    CF992E题解传送门更好的阅读体验简化题意:单点修改,设序列的前缀和序列是$s_i$,查询是否存在一个$i$满足$a_i=s_{i-1}$。思路:观察满足条件的数的个数。在不考虑$0$的情况下,如果一个$a_i$满足条件,那么对于一个比他小的满足条件的数$a_j$,一定会有$a_j=s_{j-1}$,而$......
  • AtCoder Beginner Contest 314 A - Ex题解
    AtCoderBeginnerContest314A-3.14嗯,你可以用string存小数点后的...B-Roulette对于每一个金额,用个vector存pair<>存一个人赌了多少,以及是哪一个人。C-RotateColoredSubsequence每种数用个双向链表记下来。D-LOWER我们观察到,对于2,3操作,只有最后一次有用,且......
  • 为什么会变成这样呢? #3(并查集维护区间)
    给定长度为\(n\)的字符串\(S\)以及\(m\)个区间\([l_i,r_i]\),记\(T=S[l_1,r_1]+\cdots+S[l_m,r_m]\),其中\(S[x,y]\)表示从第\(x\)个字符到第\(y\)个字符的子串。求如何重新排列\(S\)中字符的顺序使得\(T\)的字典序尽可能大。期望复杂度:近似\(O(n)\)。czy's......
  • 杂题题解
    UOJ21缩进优化题目链接记\(M=\max(a_i)\)从反面考虑,考虑\(x\)让答案减小的量。即为$\sum_{i=1}^n\lfloor\frac{a_i}{x}\rfloor\times(x-1)=(x-1)\sum_{i=1}^n\lfloor\frac{a_i}{x}\rfloor$。只需要快速计算$S=\sum_{i=1}^n\lfloor\frac{a_i}{x}\rfloor$。可以......
  • ABC 314 F 题解
    原题传送门题意有n支队伍进行比赛,起初,第i支队伍只有选手i一个人。总共要进行n-1场比赛,每次给出p和q,意为让p所在的队伍与q所在的队伍进行比赛(数据保证此时p和q不在同一支队伍),设p所在的队伍有\(siz_p\)个人,q所在的队伍有\(siz_q\)个人,则此次比赛中p......
  • 【KMP】border 题解
    题目描述输入输出样例输入abaabaa样例输出17样例解释:f[2][a]=1f[3][a]=1f[4][a]=1f[4][b]=2f[5][a]=1f[5][b]=2f[6][a]=3f[7][a]=4f[7][b]=2以上为>0的f[][],求和=17数据范围限制这一篇同上一篇,都是从以前博客搬过来的,所以真的是......
  • 猴子拆房 题解
    题目描述输入输出样例输入【样例输入1】22345【样例输入2】3242513【样例输入3】6353417174241样例输出【样例输出1】3【样例输出2】0【样例输出3】10数据范围限制提示这个是我的,是我的QWQ,我没有转载,只是把以前的博客搬运......