GZOI2019 与或和

单调栈板子题..?

首先按位拆分，然后转变为统计一个01矩阵中所有全1的子矩阵（按位与）以及所有全0的子矩阵（用总矩阵数减掉即为按位或的答案）。

打表可知$n\times n$的矩阵有$(\frac{n(n+1)}2)^2$个子矩阵。

统计全1矩阵和全0矩阵本质一样，故我们先考虑统计全0矩阵。

考虑处理出来$f(i,j)$，表示如果第i行第j列的元素时0，那么往上到什么位置的元素也全都是0。对于是1的位置，$f(i,j)=-1$。

然后我们枚举一个下界$low$，表示现在我们要统计下边缘在$low$上的矩形个数。

然后从左到右扫，维护一个单调栈，单调栈内的元素是列，设$S_i$为栈中自底向上第$i$个元素，那么满足$f(low,i+1)>f(low,i)$。

先不考虑出栈，考虑入栈。

处理右下角为$(i,j)$时的答案时，设$x$表示合法的矩形数量

假设第i列的元素$i$入栈的时候，我们设$S_{-1}$表示栈内最后一个元素，$S_{-2}$以此类推。

如果加入元素i不会使得任何元素出栈，那么我们可以得到以$(i,j)$为右下角的所有合法的矩形数量为$x+f(low,i)$。

由于加入i不会导致元素出栈，故$f(low,i)$一定大于栈中其他元素的值，所以第i列较低的$S_{-1}$列可以和前面的拼起来，比$S_{-1}$高的部分可以自己成一个宽度为1的矩形。

如果导致了元素出栈呢？

左侧到$S_{-2}$，上边界到$f(low,S_{-1})$的矩形不可能再次被取到，减掉即可。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <inttypes.h>
#define debug(x) std::cout << #x << " = " << x << std::endl;
/*
°´Î»ÌÖÂÛ
ANDֵΪ1->¾ØÕóÈ«²¿Îª1
ORֵΪ1->¾ØÕóÖÁÉÙÓÐÒ»¸ö1
ͳ¼ÆÈ«0ºÍÈ«1µÄ¾ØÕó¸öÊý£¬ÖÁÉÙÓÐÒ»¸ö1µÈ¼ÛÓÚ×Ü×Ó¾ØÕóÊý-È«0¾ØÕó¡£
*/
typedef int int_t;

using std::cin;
using std::endl;
using std::cout;
const int_t mod = 1e9 + 7;
const int_t LARGE = 1e3+3;
int_t mat[LARGE+1][LARGE+1];

//last:ij¸öλÖÃÉÏ·½µÄµÚÒ»¸ö1µÄλÖÃ
int_t count[LARGE+1][LARGE+1],last[2][LARGE+1][LARGE+1];
int_t resultAnd,resultOr;
int_t n;
int_t C2(int_t n) {
	return ((int64_t)n*(n-1)/2)%mod;
}
void countFor(int_t bit) {
	//ö¾ÙÁÐ
	for(int_t i=1; i<=n; i++) {
		last[0][0][i]=last[1][0][i]=1;
		for(int_t j=1; j<=n; j++) {
			for(int_t k=0; k<=1; k++) {
				if(count[j-1][i]!=k) {
					last[k][j][i]=j;
				} else {
					last[k][j][i]=last[k][j-1][i];
				}
				if(count[j][i]!=k) last[k][j][i]=-1;
			}
		}
	}
	int_t zero=0,one=0;
	//ö¾Ùµ×
	for(int_t low=1; low<=n; low++) {
		static int_t val[2][LARGE+1];
		for(int_t i=1; i<=n; i++) {
			for(int_t j=0; j<=1; j++) {
				if(last[j][low][i]==-1) val[j][i]=0;
				else val[j][i]=low-last[j][low][i]+1;
			}
		}
		const auto count=[&](int_t bit) {
			int_t result=0;
			int_t count = 0;
			//´Ó×óÍùÓÒɨ
			std::vector<int_t> stack;
			stack.push_back(0);
			val[bit][0]=-1;
			for(int_t i=1; i<=n; i++) {
				//ºÍÇ°ÃæÁ¬µ½Ò»ÆðµÄ & ×Ô¼ºµÄ
				count += val[bit][i];
				while(stack.size() >= 1 && val[bit][stack.back()]>=val[bit][i]) {
					count -= (stack.back() - stack[stack.size() - 2]) * (val[bit][stack.back()] - val[bit][i]);
					stack.pop_back();
				}
				stack.push_back(i);
				result += count;
			}
			return result;
		};
		zero=(zero+count(0))%mod;
		one=(one+count(1))%mod;
	}
	resultAnd=(resultAnd+(int64_t)one*(1ll<<bit)%mod)%mod;
	const auto pow2=[](int64_t x) {
		x%=mod;
		return x*x%mod;
	};
	int_t least = (pow2((int64_t)n*(n+1)/2) - zero + mod) % mod;
	resultOr=((int64_t)resultOr+least*(1ll<<bit)%mod)%mod;
}
namespace SimpleIO{
    const int_t LARGE = 5e7;
    char buf[LARGE + 1];
    char* used = buf;
    void init(){
        fread(buf,1,LARGE,stdin);
    }
    template<class T>
    void nextInt(T& x){
        x = 0;
        while(isdigit(*used) == false) used++;
        while(isdigit(*used)){
            x = x * 10 + (*used) - '0';
            used++;
        }
    }
}
int main() {
//	scanf("%d",&n);
    SimpleIO::init();
    SimpleIO::nextInt(n);
	int_t maxval=0;
	for(int_t i=1; i<=n; i++) {
		for(int_t j=1; j<=n; j++) {
//			scanf("%d",&mat[i][j]);
            SimpleIO::nextInt(mat[i][j]);
			maxval=std::max(maxval,mat[i][j]);
		}
	}
	for(int_t i=0; (1ll<<i)<=maxval; i++) {
		for(int_t j=1; j<=n; j++) {
			for(int_t k=1; k<=n; k++) {
				count[j][k]=(mat[j][k]&(1ll<<i))!=0;
			}
		}
		countFor(i);
	}
	cout << resultAnd << " " << resultOr << endl;
	return 0;
}