[GXOI/GZOI2019]与或和——单调栈

Dear 丶 2022-01-13 04:21 150阅读 0赞

# 题目链接： #

[\[GXOI/GZOI2019\]与或和][GXOI_GZOI2019]

既然求的是二进制运算的和，那么我们按位考虑，这样就将矩阵变成了一个$01$矩阵。

对于或运算，就是求有多少个子矩形中有$1$。

直接求不好办，考虑有多少个矩形只有$0$。

我们统计以每个$0$为矩形右下角的矩形有多少个。

对于第$i$行的每一列维护出从这一行开始往上有多少个连续的$0$。

现在问题就变成了对于第$i$行的每一列，之前有多少个格子能作为矩形的左上角和它匹配。

用单调栈维护一个单调递增的序列对每行分别统计答案即可。

对于与运算，就是将总子矩形数$-$包含$0$的子矩形数，对$0$再做一遍即可。

#include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<vector>
    #include<bitset>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define ll long long
    #define pr pair<int,int>
    using namespace std;
    const int mod=1e9+7;
    ll ans1,ans2;
    int a[1010][1010];
    int b[1010][1010];
    int n;
    int mx[1010];
    int top;
    pr st[1010];
    ll sum;
    ll find1()
    {
    	memset(mx,0,sizeof(mx));
    	ll res=0;
    	for(int i=1;i<=n;++i)
    	{
    		ll num=0;
    		top=0;
    		for(int j=1;j<=n;++j)
    		{
    			mx[j]=b[i][j]?mx[j]+1:0;
    			int len=1;
    			while(top&&st[top].first>=mx[j])
    			{
    				num-=st[top].first*st[top].second;
    				len+=st[top].second;
    				top--;
    			}
    			num+=mx[j]*len;
    			res=(res+num)%mod;
    			st[++top]=make_pair(mx[j],len);
    		}
    	}
    	return res;
    }
    ll find2()
    {
    	memset(mx,0,sizeof(mx));
    	ll res=0;
    	for(int i=1;i<=n;++i)
    	{
    		ll num=0;
    		top=0;
    		for(int j=1;j<=n;++j)
    		{
    			mx[j]=(!b[i][j])?mx[j]+1:0;
    			int len=1;
    			while(top&&st[top].first>=mx[j])
    			{
    				num-=st[top].first*st[top].second;
    				len+=st[top].second;
    				top--;
    			}
    			num+=mx[j]*len;
    			res=(res+num)%mod;
    			st[++top]=make_pair(mx[j],len);
    		}
    	}
    	return res;
    }
    int main()
    {
    	scanf("%d",&n);
    	sum=1ll*n*(n+1)/2*n*(n+1)/2;
    	sum%=mod;
    	for(int i=1;i<=n;++i)
    	{
    		for(int j=1;j<=n;++j)
    		{
    			scanf("%d",&a[i][j]);
    		}
    	}
    	for(int k=0;k<=31;++k)
    	{
    		for(int i=1;i<=n;++i)
    		{
    			for(int j=1;j<=n;++j)
    			{
    				if(a[i][j]&(1<<k))
    				{
    					b[i][j]=1;
    				}
    				else
    				{
    					b[i][j]=0;
    				}
    			}
    		}
    		ans1+=(1ll<<k)%mod*find1()%mod,ans1%=mod;
    		ans2+=(1ll<<k)%mod*(sum-find2()+mod)%mod,ans2%=mod;
    	}
    	ans1=(ans1%mod+mod)%mod,ans2=(ans2%mod+mod)%mod;
    	printf("%lld %lld",ans1,ans2);
    }

转载于:https://www.cnblogs.com/Khada-Jhin/p/10716530.html

[GXOI_GZOI2019]: https://loj.ac/problem/3083