既然求的是二进制运算的和，那么我们按位考虑，这样就将矩阵变成了一个$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);
}
[LOJ3083][GXOI/GZOI2019]与或和——单调栈
原文：https://www.cnblogs.com/Khada-Jhin/p/10716530.html