首页 > 其他分享 >P10856 【MX-X2-T5】「Cfz Round 4」Xor-Forces题解

P10856 【MX-X2-T5】「Cfz Round 4」Xor-Forces题解

时间:2024-11-13 15:11:23浏览次数:1  
标签:le Xor int 题解 T5 lst mid 异或 区间

题意:
给定一个长度为 \(n=2^k\) 的数组 \(a\),下标从 \(0\) 开始,维护 \(m\) 次操作:

  1. 给定 \(x\),设数列 \(a'\) 满足 \(a'_i=a_{i\oplus x}\),将 \(a\) 修改为 \(a'\)。其中 \(\oplus\) 表示按位异或运算。
  2. 给定 \(l,r\),查询 \(a\) 的下标在 \(l,r\) 之间的子数组有多少颜色段。不保证 \(\bm {l\le r}\),若 \(\bm{l > r}\),请自行交换 \(\bm{l,r}\)。

其中,一个极长的所有数都相等的子数组称为一个颜色段。
强制在线。
\(T \in \{ 0, 1 \}\),\(0\le k\le 18\),\(n=2^k\),\(1\le m\le 2\times 10^5\),\(1\le a_i\le n\),\(\mathit{op} \in \{ 1, 2 \}\),\(0\le x,l,r < n\)。

思路

  • 乍一看操作1几乎完全无法操作。但是自己手动模拟几组数据或者打表可以发现一些有趣的事实:
  1. 操作1有结合律,因此询问事实上等价于询问一个区间根据操作1操作后的颜色段数,其中操作1的 \(x\) 是之前所有操作的前缀异或和。

  2. 以2的次幂为长度的区间(即类似于线段树各层上的区间)无论异或的数是多少,这个区间内的数一定仍在长度相等的区间里,只是顺序可能变动。
    这个结论是比较好感性理解的。对于线段树上的一段区间,其区间的序号的二进制一定是一段高位相等而剩下的低位连续。
    这些序号同时异或上一个数后高位仍然对位相同而低位仍覆盖一段相对应的区间。

  3. 对于一段区间,其异或上的值只有小于其长度的才有用。这里的“有用”指的是没办法在线 \(O(1)\) 算出来区间对应的地方,必须预处理的。
    因为仍然考虑类似于2的想法,对于区间里的所有序号,如果改变其高位,那么实际上与另一段高位改变后的区间异或上低位的值是等同的。
    因此只需要对于每个区间预处理出其 \(0\) 到 \(len-1\) 的异或后的答案,就可以 \(O(1)\) 回答询问了。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int T,k,m,a[N],n;
vector <int> f[N<<2];
struct node
{
	#define ls (u<<1)
	#define rs ((u<<1)|1)
	void build(int u,int l,int r)
	{
		int len=r-l+1,mid=(l+r)>>1;f[u].resize(len);
		if(l==r){f[u][0]=0;return;}
		build(ls,l,mid),build(rs,mid+1,r);
		for(int x=0;x<len;x++)
		f[u][x]=f[ls][x%(len/2)]+f[rs][x%(len/2)]+(a[mid^x]==a[(mid+1)^x]?1:0);
	}
	int query(int u,int l,int r,int ql,int qr,int x)
	{
		int mid=(l+r)>>1,len=r-l+1,ceng=__lg(r-l+1),newl=l^(x>>ceng<<ceng),newu=u+(newl-l)/len,newx=x%len,res=0;
		if(ql<=l&&qr>=r) return f[newu][newx];
		if(ql<=mid) res+=query(ls,l,mid,ql,qr,x);
		if(qr>mid) res+=query(rs,mid+1,r,ql,qr,x);
		if(ql<=mid&&qr>mid) res+=a[mid^x]==a[(mid+1)^x]?1:0;
		return res;
	}
}ds;
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>T>>k>>m;n=1<<k;
	for(int i=0;i<n;i++) cin>>a[i];
	ds.build(1,0,n-1);
	int lst=0,sumx=0;
	for(int i=1,op,l,r,t;i<=m;i++)
	{
		cin>>op;if(op==1) {cin>>t,t=t^(T*lst),sumx=sumx^t;continue;}
		cin>>l>>r;l=l^(T*lst),r=r^(T*lst);if(l>r) swap(l,r);lst=r-l+1-ds.query(1,0,n-1,l,r,sumx);cout<<lst<<'\n';
	}
}

标签:le,Xor,int,题解,T5,lst,mid,异或,区间
From: https://www.cnblogs.com/allforgod/p/18543948

相关文章

  • [题解]P3225 [HNOI2012] 矿场搭建
    P3225[HNOI2012]矿场搭建挖煤点坍塌相当于把该点和与其相连的边在图上删掉。借用wjyyy的题解,我们定义“叶子连通块”为“只包含\(1\)个割点的点双连通分量”,“非叶子连通块”为“包含\(\ge2\)个割点的点双连通分量”。如下图,橙色点是割点,红色框圈出的是点双,加粗的是叶子连通......
  • P2612 [ZJOI2012] 波浪 题解
    前置知识:连续段dp题目链接:P2612[ZJOI2012]波浪随机一个\(1\)到\(n\)的排列\(P_{1...n}\),问以下式子的值\(\lem\)的概率是多少?\[|P_1-P_2|+|P_2-P_3|+|P_3-P_4|+...+|P_{n-1}+P_n|\]输出一个答案表示概率。保留\(k\)位小数。对于\(40%\)......
  • P11071 「QMSOI R1」 Distorted Fate题解
    题意:给定一个序列,给定两种操作:将一个区间异或上一个给定的值。给定\(l,r\)求\[{\large(\sum_{i=l}^r\bigcup_{j=l}^iA_j)\bmod2^{30}}\]\(0\lea_i,x<2^{30}\),\(1\lel\ler\len\)思路由于操作数以及区间过大,一位一位地去模拟肯定是不行的。因此考虑去离线......
  • [题解]CF1407D Discrete Centrifugal Jumps
    思路注意到第二个条件和第三个条件本质相似,可以用相同的维护方式处理,因此这个只讨论第二个条件的维护方式。定义\(dp_i\)表示走到\(i\)的最少步数。第一个条件的转移显然为\(dp_i\leftarrowdp_{i-1}\)。对于第二个条件,\(i\)能向\(j\)转移,当且仅当\(h_{i+1\sim......
  • Codeforces Round 985 div1+2 个人题解(A~E)
    CodeforcesRound985div1+2个人题解(A~E)Dashboard-Refact.aiMatch1(CodeforcesRound985)-Codeforces火车头#include<bits/stdc++.h>usingnamespacestd;#defineftfirst#definesdsecond#defineyescout<<"yes\n"#definenoc......
  • Python 第三方库 PyQt5 的安装
    目录前言PyQt5安装不同操作系统PyQt5安装一、Windows系统二、macOS系统三、Linux系统(以Ubuntu为例)安装PyQt5可能会遇到的问题一、环境相关问题二、依赖问题三、网络问题四、安装工具问题五、运行时问题六、环境配置问题七、安装源问题八、检查错误信息......
  • [CF1935E] Distance Learning Courses in MAC 题解
    [CF1935E]DistanceLearningCoursesinMAC难度正常的一道题。首先我们发现“挑选若干个区间”就是一句废话,因为按位或只会贡献答案而不会减小答案。所以我们需要在\([L,R]\)的每个区间都挑一个数,使得最终的按位或最大。想办法让尽可能多的二进制位都变成\(1\),且越是高......
  • [USACO06NOV] Corn Fields G 题解
    题目链接[USACO06NOV]CornFieldsG题解这是一道典型的状压dp,对于\(M\)行\(N\)列的图,由于每个点只有\(1\)和\(0\)两种状态,我们将其压缩为一个长度为\(M\)的数组,数组(\(g\))的每一项\(g_{i}\)表示状态的二进制表示法表示的数(如\(101\)表示为\(5\)),我们预先处......
  • [CEOI2023] A Light Inconvenience 题解
    Description今年CEOI的开幕式上有一场精彩的火炬表演。表演者们站成一排,从\(1\)开始从左往右编号。每个表演者举着一根火炬,初始只有一个举着点燃的火炬的表演者。表演分为\(Q\)幕。在第\(a\)幕开始之前,要么\(p_a>0\)个表演者从右侧加入表演,他们的火炬是熄灭的;要么最......
  • gym103102H AND = OR 题解
    非常巧妙的一个题。我们首先考虑单组询问该怎么做。首先需要注意到一个结论,即设答案为\(x\),那么对于\(\forally<x\),\(y\)都应该放在与组;同样的,对于\(\forally>x\),\(y\)都应该放在与组。进一步的,我们观察在\(\text{popcount}\)上也有同样的性质,即对于\(\forally,......