首页 > 其他分享 >异或与区间加题解

异或与区间加题解

时间：2024-05-01 16:11:06浏览次数：22  
标签：10 ch int 题解 三元组 cc 异或 le 区间

异或与区间加题解

简要题意

给定 \(n,m,K,a_{1...n}\)，和 \(m\) 个三元组 \((x_i,y_i,z_i)\)，定义 \(calc(l,r)=a_l \bigoplus a_{l+1}\bigoplus ...\bigoplus a_r\)。对于每个三元组 \((x,y,z)\) ，对所有满足 \(x\le l\le r\le y\ ,\ calc(l,r)=K\) 的区间 \((l,r)\) 内的每个数 \(b_i\) 加上 \(z\)，其中 \(b_{1..n}\)​​ 初始全为 0。输出对 \(2^{30}\) 取模。

\(0\le K,a_i<2^{30},1\le x\le y\le n,0\le z\le 10000\)

10 10 3//n m K
2 0 3 0 1 0 0 2 1 2//a[i]
1 10 1//x y z
3 10 9
10 10 5
4 10 10
9 10 8
7 7 8
3 5 10
7 8 9
7 9 7
7 8 7

1 4 54 53 52 72 99 126 114 39

题解

先来一个暴力的方法。首先容易想到对 \(a\) 求一遍前缀和，将 \(calc(l,r)=K\) 转化为 \(sum_r\bigoplus sum_{l-1}=K\)。将每个三元组按关键字排序（先x后y），然后从前往后扫描每一个区间。然后开一个树状数组，令 \(c_{x..y}\) 加上 \(z\)。\(c_{pos}\) 表示：对于每个右端点位于 \(pos\) 的区间 \((l,r)\)，应对的 \(b_{l...r}\) 需要加上 \(c_{pos}\)。但是这样可能会把 \(l<x\) 的区间也进行操作，所以我们应该从前往后扫描每一个位置。在扫描到位置 \(l\) 的时候，如果发现存在三元组满足 \(x=l\)，那么我们令 \(c_{x..y}\) 加上 \(z\)。处理完 \(c\) 以后，找到满足 \(sum_r\bigoplus sum_{l-1}=K\) 的 \(r\)（可以利用map找），然后再将 \(b_{l...r}\) 加上 \(c_{r}\)，这一个区间加可以用差分处理。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int mod=1<<30;
int n,m,K,a[150010],sum[150010];
LL c[150010],cc[150010];
unordered_map<int,vector<int>>mp;
struct SYZ
{int x,y,z;}syz[150010];
inline int read()
{
	int x=0,w=0;char ch=0;
	while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return w?-x:x;
}
bool cmp(SYZ n1,SYZ n2)
{
	if(n1.x^n2.x)return n1.x<n2.x;
	return n1.y<n2.y;
}
void change(int x,int y)
{for(;x<=n;x+=x&-x)c[x]+=y;}
int ask(int x,int y=0)
{for(;x;x-=x&-x)y+=c[x];return y;}
int main()
{
	n=read();m=read();K=read();
	mp[0].push_back(0);
	for(int i=1;i<=n;i++)
		mp[sum[i]=sum[i-1]^(a[i]=read())].push_back(i);
	for(int i=1;i<=m;i++){
		int x=read(),y=read(),z=read();
		syz[i]=(SYZ){x,y,z};
	}
	sort(syz+1,syz+1+m,cmp);
	for(auto&x:mp)//x.first是键，x.second是值
		reverse(x.second.begin(),x.second.end());
	for(int i=1,j=1;i<=n;i++){//i是左端点
		while(j<=m&&syz[j].x==i)
			change(1,syz[j].z),change(syz[j].y+1,-syz[j].z),j++;
		for(int x:mp[sum[i-1]^K]){//x是右端点
			if(x<i)break;
			int temp=ask(x);
			cc[i]+=temp;
			cc[x+1]-=temp;
		}
	}
	for(int i=1;i<=n;i++)
		printf("%lld%c",(cc[i]+=cc[i-1])%=mod," \n"[i==n]);
}

这里的 \(cc\) 是 \(b\) 的差分数组。

此方法的瓶颈在于：对于一个 \(l\) ，满足条件的 \(r\) 可能会非常多。

我们可以在当 \(r\) 的数量小于 \(\sqrt{n}\) 时用上述方法，当 \(r\) 数量过多时需要换一种方法。值得注意的是，这样不同的 \(sum_r\) 不会超过 \(\sqrt{n}\) 个。

我们不妨对每一个这样的 \(sum_r\) 单独处理，我们先暴力找到所有的 \(l\) 和 \(r\) ，利用前缀和可以计算出区间 \(xx,yy\) 内有多少个 \(l\) 或 \(r\)。

设 \(prez_i\) 表示：满足 \(x\le i\le y\) 的所有三元组的 \(z\) 的和，利用差分可以快速求出。

我们要分别扫描所有的 \(l\),\(r\) ，扫描 \(l\) 时，让 \(cc_l\) 加上一些东西；扫描 \(r\) 时，让 \(cc_{r+1}\) 减去一些东西。

我们不妨先考虑一个弱化版本，即：\(y=n\)。如果此方法可行的话，我们可以试图将 \((x,y,z)\) 拆分成 \((x,n,z)\) 和 \((y+1,n,-z)\)。注意，直接拆分会错误地统计上这样的区间：\(x\le l\le y<r\)。我们需要额外的操作减去这样的贡献。

显然，对于 \((x,y,z)\) 只需要 \(l\ge x\) 即可。我们可以扫描每一个 \(l\) ，计算 \(x\le l\) 的 \(z\) 的和，以及 \(r\) 的数量。前者即是 \(prez_l\)，后者用差分统计即可。有：\(cc_l+=cnt(r)*prez_l\)。同样地，对于 \(r\) 我们沿用类似的方法，但稍微麻烦点。对于 \(cc_{r+1}\) 我们要减去的是：每一个 \(x\le l\) 对应的 \(z\)。这个可以一遍扫描一遍统计，初始令 \(temp=0\) ，从左往右扫描时，如果 \(pos\) 是左端点，则令 \(temp+=prez_{pos}\)。当扫描到一个右端点 \(r\) 时，令 \(cc_{r+1}-=temp\)。意思是遇到一个左端点 \(l\)，那么它后面的右端点统统加上它左边的三元组的 \(z\) （即 \(prez_l\)）。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int mod=1<<30;
int n,m,K,B,a[150010],sum[150010];
int sX[150010],sY[150010];
LL c[150010],cc[150010],prez[150010];
unordered_map<int,vector<int>>mp;
struct SYZ
{int x,y,z;}syz[150010];
inline int read()
{
	int x=0,w=0;char ch=0;
	while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return w?-x:x;
}
bool cmp(SYZ n1,SYZ n2)
{
	if(n1.x^n2.x)return n1.x<n2.x;
	return n1.y<n2.y;
}
void change(int x,int y)
{for(;x<=n;x+=x&-x)c[x]+=y;}
int ask(int x,int y=0)
{for(;x;x-=x&-x)y+=c[x];return y;}
void solve(int Y)//Y=sum[r]
{
	int X=K^Y;//X=sum[l-1]
	for(int i=1;i<=n;i++){
		sX[i]=sX[i-1]+(sum[i-1]==X);
		sY[i]=sY[i-1]+(sum[i]==Y);
	}
	for(int i=1;i<=n;i++)
	if(sum[i-1]==X)
		cc[i]+=prez[i]*(sY[n]-sY[i-1]);
	LL temp=0;
	for(int i=1;i<=n;i++){
		if(sum[i-1]==X)temp+=prez[i];
		if(sum[i]==Y)cc[i+1]-=temp;
	}
}
int main()
{
	n=read();m=read();K=read();B=sqrt(n);
	mp[0].push_back(0);
	for(int i=1;i<=n;i++)
		mp[sum[i]=sum[i-1]^(a[i]=read())].push_back(i);
	for(int i=1;i<=m;i++){
		int x=read(),y=read(),z=read();
		syz[i]=(SYZ){x,y,z};
		prez[x]+=z;prez[y+1]-=z;
	}
	for(int i=1;i<=n;i++)
		prez[i]+=prez[i-1];
	sort(syz+1,syz+1+m,cmp);
	for(auto&x:mp)//x.first是键，x.second是值
		reverse(x.second.begin(),x.second.end());
	for(int i=1,j=1;i<=n;i++){//i是左端点
		while(j<=m&&syz[j].x==i)
			change(1,syz[j].z),change(syz[j].y+1,-syz[j].z),j++;
		if(mp[sum[i-1]^K].size()<B)
		for(int x:mp[sum[i-1]^K]){//x是右端点
			if(x<i)break;
			int temp=ask(x);
			cc[i]+=temp;
			cc[x+1]-=temp;
		}
	}
	for(auto&x:mp)
	if(x.second.size()>=B)
		solve(x.first);
	for(int i=1;i<=n;i++)
		printf("%lld%c",(cc[i]+=cc[i-1])%=mod," \n"[i==n]);
}

现在我们考虑怎么样拆分一个三元组，以及如何处理错误统计的 \(l,r\) 。

对于 \((x,y,z)\) ，在处理 \(cc_l\) 时，我们不想让 \(y<r\) 的那些区间统计上 \(z\)。我么需要新开一个数组，统计上需要减去的这些 \(z\)。（此时树状数组的 \(c\) 数组已经没用了我们不如再次利用 \(c\)）我们令 \(c_x+=z*cnt(r)\)，这些 \(r\) 要满足 \(r>y\)。同时令 \(c_{y+1}-=z*cnt(r)\)。这个意思是：在扫描到 \(l\ge x\) 的 \(l\) 时，统计的答案要减去 \(c_x\)，因为多出来的 \(r\) 不应该统计上去。统计到 \(y\) 后面的 \(l\) 时，不用减去这些了，因为本来就没有统计上（不明白为什么没统计上的话，可以看一下\(prez\)​）。

在处理 \(cc_{r+1}\) 时，我们应当减去 \(x\le l\le y<r\) 对应的 \(z\)。我们在扫描三元组 \((x,y,z)\) 时，令 \(c[y+1]+=z*cnt(l)\)，这些 \(l\) 满足 \(x\le l \le y\)。意思是，扫描到 \(r\ge y+1\) 的 \(r\) 时，统计的答案要少减去 \(c[y+1]\)。因为，前面对应的那些三元组，贡献要减少 \(c[y+1]\) ，因为 \(r\) 越界了，那些 \(l\) 不会和这个 \(r\) 产生贡献。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int mod=1<<30;
int n,m,K,B,a[150010],sum[150010];
int sX[150010],sY[150010];
LL c[150010],cc[150010],prez[150010];
unordered_map<int,vector<int>>mp;
struct SYZ
{int x,y,z;}syz[150010];
inline int read()
{
	int x=0,w=0;char ch=0;
	while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return w?-x:x;
}
bool cmp(SYZ n1,SYZ n2)
{
	if(n1.x^n2.x)return n1.x<n2.x;
	return n1.y<n2.y;
}
void change(int x,int y)
{for(;x<=n;x+=x&-x)c[x]+=y;}
int ask(int x,int y=0)
{for(;x;x-=x&-x)y+=c[x];return y;}
void solve(int Y)//Y=sum[r]
{
	int X=K^Y;//X=sum[l-1]
	for(int i=1;i<=n;i++){
		sX[i]=sX[i-1]+(sum[i-1]==X);
		sY[i]=sY[i-1]+(sum[i]==Y);
	}
	memset(c,0,sizeof c);
	for(int i=1;i<=m;i++){
		int x=syz[i].x,y=syz[i].y,z=syz[i].z;
		c[x]+=1ll*z*(sY[n]-sY[y]);
		c[y+1]-=1ll*z*(sY[n]-sY[y]);
	}
	for(int i=1;i<=n;i++){
		c[i]+=c[i-1];
		if(sum[i-1]==X)
			cc[i]+=prez[i]*(sY[n]-sY[i-1])-c[i];
	}
	memset(c,0,sizeof c);
	for(int i=1;i<=m;i++){
		int x=syz[i].x,y=syz[i].y,z=syz[i].z;
		c[y+1]+=1ll*z*(sX[y]-sX[x-1]);
	}
	LL temp=0;
	for(int i=1;i<=n;i++){
		c[i]+=c[i-1];
		if(sum[i-1]==X)temp+=prez[i];
		if(sum[i]==Y)
			cc[i+1]-=temp-c[i];
	}
}
int main()
{
	n=read();m=read();K=read();B=sqrt(n);
	mp[0].push_back(0);
	for(int i=1;i<=n;i++)
		mp[sum[i]=sum[i-1]^(a[i]=read())].push_back(i);
	for(int i=1;i<=m;i++){
		int x=read(),y=read(),z=read();
		syz[i]=(SYZ){x,y,z};
		prez[x]+=z;prez[y+1]-=z;
	}
	for(int i=1;i<=n;i++)
		prez[i]+=prez[i-1];
	sort(syz+1,syz+1+m,cmp);
	for(auto&x:mp)//x.first是键，x.second是值
		reverse(x.second.begin(),x.second.end());
	for(int i=1,j=1;i<=n;i++){//i是左端点
		while(j<=m&&syz[j].x==i)
			change(1,syz[j].z),change(syz[j].y+1,-syz[j].z),j++;
		if(mp[sum[i-1]^K].size()<B)
		for(int x:mp[sum[i-1]^K]){//x是右端点
			if(x<i)break;
			int temp=ask(x);
			cc[i]+=temp;
			cc[x+1]-=temp;
		}
	}
	for(auto&x:mp)
	if(x.second.size()>=B)
		solve(x.first);
	for(int i=1;i<=n;i++)
		printf("%lld%c",(cc[i]+=cc[i-1])%=mod," \n"[i==n]);
}

标签：10,ch,int,题解,三元组,cc,异或,le,区间
From： https://www.cnblogs.com/zYzYzYzYz/p/18169412

相关文章

  • CF1967B2 Reverse Card (Hard Version) 题解
    题意：求有多少对\((a,b)\)满足\(b\times\gcd(a,b)\equiv0\pmod{a+b},1\lea\len,1\leb\lem\)。首先我们设\(\gcd(a,b)=G,a=i\timesG,b=j\timesG\)，显然有\(\gcd(i,j)=1\)。那么可以把原条件转化为\(j\timesG\)是\((i+j)\)的倍数。因为\(\gcd(i+......
  • Codeforces Round 942 Div.2 题解
    蹭个热度，挽救一下cnblogs蒸蒸日上的阅读量。Q:你是手速狗吗？A:我觉得我是。2A因为选的\(w\)一定可以让它合法，一次操作可以看作\(a\)数组向右平移一位。枚举操作次数后暴力判断即可。#include<bits/stdc++.h>voidwork(){ intn; std::cin>>n; std::vector<......
  • 【题解】 量化交易5
    题目描述applepi训练了一个可以自动在股票市场进行量化交易的模型。通常来说，applepi写出的模型，你懂得，就好比一架印钞机。不过为了谨慎起见，applepi还是想先检查一下模型的效果。applpie收集了“塞帕思股份(surpass)”在最近的连续N天内的价格。在每一天中，他可以做如下事情之一：......
  • Educational Codeforces Round 165 (Rated for Div. 2) 题解
    A对于\(i\top_i\)连边。如果存在二元环，则答案为2。否则答案为3。B非降序排序：0全部在1前面。令0的个数为z。从左往右，将前z个全部填上0。填第\(i\)位时，每次填的最小代价为：若第\(i\)位为1，第\(i\)位右边的第一个0到\(i\)之间的字符个数。（贪心）......
  • 【题解】 量化交易4
    题目描述applepi训练了一个可以自动在股票市场进行量化交易的模型。通常来说，applepi写出的模型，你懂得，就好比一架印钞机。不过为了谨慎起见，applepi还是想先检查一下模型的效果。applpie收集了“塞帕思股份(surpass)”在最近的连续N天内的价格。在每一天中，他可以做如下事情之一：......
  • 【题解】 量化交易3
    题目描述applepi训练了一个可以自动在股票市场进行量化交易的模型。通常来说，applepi写出的模型，你懂得，就好比一架印钞机。不过为了谨慎起见，applepi还是想先检查一下模型的效果。applpie收集了“塞帕思股份(surpass)”在最近的连续N天内的价格。在每一天中，他可以做如下事情之一：......
  • CF1765C Card Guessing 题解
    考虑期望的线性性，求每种情况猜对的概率和，最终再除掉\({4n\choosen,n,n,n}\)。考虑枚举最少的出现次数\(mn\)，记四种卡的出现次数分别为\(c_1,c_2,c_3,c_4\)，\(c_1+c_2+c_3+c_4=i\lek\)，则这种情况的方案数为：\[{i\choosec_1,c_2,c_3,c_4}{4n-i\choosen-c_1,n-c_2,n-c_3,n-c_......
  • 题解 CF1965E【Connected Cubes】
    场切了1E，第一次上IGM，纪念一下。多图警告。我们称题目中的一个方块为“某色混凝土”。感受一下，发现本题主要的难点在于这些混凝土方块排布得太紧密了，导致容易出现互相遮挡的现象，进而难以构造。于是，我们先思考能否通过一些操作使得这些混凝土互相分离。如下图的方式可以将每两......
  • CF1956F Nene and the Passing Game 题解
    题目链接点击打开链接题目解法首先答案为连边之后连通块的个数把限制中的\(i,j\)分开，则\(i,j\)能传球当且仅当\(i+l_i\lej-l_j\)且\(j-r_j\lei+r_i\)这是一个二维偏序的形式先考虑怎么暴力做，考虑将\((i+l_i,0),\;(i-l_i,1)\)排序，然后按顺序加入如果碰到操作\(......
  • npm下载包时报错 Unexpected token '.'问题解决
    1.出现问题当通过nvm切换nodejs版本为16以上时，npminstall[package]报错：Unexpectedtoken'.'2.问题原因该问题不是npm的问题，也不是nodejs的问题，是nvm-windows的问题。3.解决问题nvm-windows已经更新版本解决了这个问题我是通过更新nvm-windows到版本1.19解决了这个问题......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99