大佬教程收集整理的这篇文章主要介绍了[GXOI/GZOI2019]与或和，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

[GXOI/GZOI2019]与或和

很显然在2进制每一位做出的贡献是可以分别计算的，那么我们考虑单独计算这31位

与运算和或运算的计算过程显然是一模一样的，与运算就是找右多少个全都是1的矩阵

而或运算就是所有的矩阵减去全部都是0的矩阵，所以操作起来是一模一样的

我们看如何实现，首先，我们预处理出(S_{i,j})表示(i,j)这个点的正上方有多少个1

那么我们处理一排的时候，很多点都是没有用的

例如在处理2的时候A部分是没有用的，在处理4的时候B部分也是没用的，那么我们可以建立一个单调递增的栈

来计算那些没用但是被计算了的区间，也就是在弹栈的时候让统计的答案减去((stk_{top}-stk_{top-1})(S_{i,stk[top]}-S_{i,j}))就好了

复杂度(O(n^2log(max(a_{i,j}))))

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int mod=1e9+7;
int bo[1001][1001],bit[40];
int a[1001][1001],s[1001][1001],n;
int stk[1001],top,ans1,ans2;
signed main()
{
	n=read();bit[0]=1;for(int i=1;i<=30;i++)bit[i]=bit[i-1]*2;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=read();
	for(int k=0;k<=30;k++)
	{
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
		if(a[i][j]&bit[k]) bo[i][j]=1; else bo[i][j]=0;
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
		s[i][j]=bo[i][j]*s[i-1][j]+bo[i][j];
		for(int i=1;i<=n;i++) 
		{
			top=0;int ans=0;
			for(int j=1;j<=n;j++)
			{
				ans+=s[i][j];
				while(top&&s[i][stk[top]]>=s[i][j])
				{ans-=(stk[top]-stk[top-1])*(s[i][stk[top]]-s[i][j]); top--;}
				ans1+=ans*bit[k];stk[++top]=j;
			}ans1%=mod;
		}
	}
	printf("%lld ",ans1);
	for(int k=0;k<=30;k++)
	{
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
		if(a[i][j]&bit[k]) bo[i][j]=0; else bo[i][j]=1;
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
		s[i][j]=bo[i][j]*s[i-1][j]+bo[i][j];
		for(int i=1;i<=n;i++) 
		{
			top=0;int ans=0;
			for(int j=1;j<=n;j++)
			{
				ans+=s[i][j];
				while(top&&s[i][stk[top]]>=s[i][j])
				{ans-=(stk[top]-stk[top-1])*(s[i][stk[top]]-s[i][j]); top--;}
				ans2+=(i*j-ans)*bit[k];stk[++top]=j;
			}ans2%=mod;
		}
	}
	printf("%lldn",ans2);
}

大佬总结

以上是大佬教程为你收集整理的[GXOI/GZOI2019]与或和全部内容，希望文章能够帮你解决[GXOI/GZOI2019]与或和所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。