【BZOJ5502】[GXOI/GZOI2019]与或和（单调栈）

题面

题解

看到位运算就直接拆位，于是问题变成了求有多少个全\(0\)子矩阵和有多少个全\(1\)子矩阵。

这两个操作本质就是一样的，不妨考虑有多少个全\(1\)子矩阵。

预处理出每个元素向上能够找的最多的\(1\)的个数，对于每一行从做往右扫一遍，拿一个单调栈维护一下，这样子就可以计算出以每个元素为右下角时的贡献了。

时间复杂度\(O(n^2logV)\)，在BZOJ上因为常数太大T了QwQ。

#include<iostream>

#include<cstdio>

using namespace std;

#define MAX 1010

#define MOD 1000000007

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n,a[MAX][MAX],b[MAX][MAX],u[MAX][MAX];

int Q[MAX],h,t,ans1=0,ans2=0;

int main()

{

	n=read();

	for(int i=1;i<=n;++i)

		for(int j=1;j<=n;++j)a[i][j]=read();

	for(int k=0;k<31;++k)

	{

		for(int i=1;i<=n;++i)

			for(int j=1;j<=n;++j)b[i][j]=(a[i][j]>>k)&1;

		for(int i=1;i<=n;++i)

			for(int j=1;j<=n;++j)

				if(!b[i][j])u[i][j]=0;

				else u[i][j]=u[i-1][j]+1;

		for(int i=1;i<=n;++i)

		{

			Q[h=t=1]=0;int now=0;

			for(int j=1;j<=n;++j)

			{

				while(h<t&&u[i][Q[t]]>=u[i][j])now=(now+MOD-1ll*(Q[t]-Q[t-1])*u[i][Q[t]]%MOD)%MOD,--t;

				now=(now+1ll*(j-Q[t])*u[i][j])%MOD;Q[++t]=j;

				ans1=(ans1+1ll*now*(1<<k))%MOD;

			}

		}

		for(int i=1;i<=n;++i)

			for(int j=1;j<=n;++j)b[i][j]^=1;

		for(int i=1;i<=n;++i)

			for(int j=1;j<=n;++j)

				if(!b[i][j])u[i][j]=0;

				else u[i][j]=u[i-1][j]+1;

		ans2=(ans2+1ll*(1<<k)%MOD*(1ll*n*(n+1)/2*n*(n+1)/2%MOD)%MOD)%MOD;

		for(int i=1;i<=n;++i)

		{

			Q[h=t=1]=0;int now=0;

			for(int j=1;j<=n;++j)

			{

				while(h<t&&u[i][Q[t]]>=u[i][j])now=(now+MOD-1ll*(Q[t]-Q[t-1])*u[i][Q[t]]%MOD)%MOD,--t;

				now=(now+1ll*(j-Q[t])*u[i][j])%MOD;Q[++t]=j;

				ans2=(ans2+MOD-1ll*now*(1<<k)%MOD)%MOD;

			}

		}

		continue;

	}

	printf("%d %d\n",ans1,ans2);

	return 0;

}

巴特西

【BZOJ5502】[GXOI/GZOI2019]与或和（单调栈）

【BZOJ5502】[GXOI/GZOI2019]与或和（单调栈）

题面

题解

最新文章

热门文章