[GXOI/GZOI2019]与或和(单调栈)

最新推荐文章于 2021-10-28 20:21:28 发布

weixin_33874713

最新推荐文章于 2021-10-28 20:21:28 发布

阅读量140

点赞数

原文链接：http://www.cnblogs.com/rikurika/p/gxoi2.html

版权

想了想决定把这几题也随便水个解题报告...

bzoj luogu

思路：

首先肯定得拆成二进制30位啊

此后每一位的就是个01矩阵

Q1就是全是1的矩阵个数

Q2就是总矩阵个数减去全是0的矩阵个数

玉蟾宫警告

就是单调栈乱搞对吧

本题完结

事实上有了思路其他的都是多余的对吧所以就不要介意代码了

 1 #include<cstdio>
 2 #define mo 1000000007
 3 const int N=1011;
 4 template<typename tp>inline void read(tp &tar)
 5 {
 6     tp ret=0,f=1;char ch=getchar();
 7     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 8     while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
 9     tar=ret*f;
10 }
11 int n,ai[N][N],a1[N][N],a0[N][N];
12 int ans1,ans0;
13 int sta1[N],sta0[N];
14 int main()
15 {
16     read(n);
17     for(int i=1;i<=n;i++)
18     {
19         for(int j=1;j<=n;j++)
20         {
21             read(ai[i][j]);
22         }
23     }
24     for(int k=0,o=1;k<31;k++,o<<=1)
25     {
26         for(int i=1;i<=n;i++)
27         {
28             for(int j=1;j<=n;j++)
29             {
30                 if(ai[i][j]&o)
31                     a1[i][j]=a1[i-1][j]+1,a0[i][j]=0;
32                 else
33                     a0[i][j]=a0[i-1][j]+1,a1[i][j]=0;
34             }
35         }
36         for(int i=1;i<=n;i++)
37         {
38             int hop1=0,hop0=0,tmp1=0,tmp0=0;
39             for(int j=1;j<=n;j++)
40             {
41                 tmp1+=a1[i][j];
42                 while(hop1&&a1[i][j]<a1[i][sta1[hop1]])
43                 {
44                     tmp1+=(sta1[hop1]-sta1[hop1-1])*(a1[i][j]-a1[i][sta1[hop1]]);
45                     hop1--;
46                 }
47                 ans1=(ans1+((1ll*tmp1)<<k)%mo)%mo;
48                 sta1[++hop1]=j;
49                 tmp0+=a0[i][j];
50                 while(hop0&&a0[i][j]<a0[i][sta0[hop0]])
51                 {
52                     tmp0+=(sta0[hop0]-sta0[hop0-1])*(a0[i][j]-a0[i][sta0[hop0]]);
53                     hop0--;
54                 }
55                 ans0=(ans0+((1ll*(i*j-tmp0))<<k)%mo)%mo;
56                 sta0[++hop0]=j;
57             }
58         }
59     }
60     printf("%d %d\n",ans1,ans0);
61     return 0;
62 }