题解 [SEERC2018]Matrix Queries

· · 题解

题目链接

题目分析

这道题目最大的难点就是如何快速求一个矩阵的价值。

不妨认为一个矩阵是合法矩阵，当且仅当在算价值时可能会递归到该矩阵，比如以 (1,1) 和 (1,1) 为两个角的矩阵是合法的，以 (1,5) 和 (2,6) 为两个角的矩阵是合法的。

在原题面中，由于单色矩阵和多色矩阵都会造成贡献，所以价值不太好求，不妨转化一下题面：

  1. 如果矩阵是单色的，则它的价值为 0 金币；
  2. 否则，将矩阵分割成 4 个大小相等的子矩阵，矩阵的价值为子矩阵的价值之和加 4 金币。

最后，整个矩阵的价值还要加一。

这种转化相当于是把传递下去给每个矩阵造成额外的 1 金币的贡献提前算到当前矩阵处，由于整个矩阵一开始额外贡献的 1 金币没有提前算，所以还要加一。

如果一个合法矩阵是异色的，那么一定会递归到该矩阵并造成贡献，因为包含它的合法矩阵肯定都是异色的，所以题目就是要求所有异色的合法矩阵数量乘四加一。

还是不好求，正难则反，考虑求出所有单色的合法矩阵数量，一个合法矩阵单色，当且仅当它所在的行被改变次数奇偶性相同，同时它所在的列被改变次数奇偶性相同，这个比较显然，题目中给出的结构对于行和列都是和线段树很类似的，而且行和列是可以分开考虑的，维护两个线段树同时维护线段树每一层的操作奇偶性相同的数量即可求得答案。

参考代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ch() getchar()
#define pc(x) putchar(x)
template<typename T>inline void read(T&x){
    int f;char c;
    for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f;
    for(x=0;c<='9'&&c>='0';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>inline void write(T x){
    static char q[64];int cnt=0;
    if(!x)pc('0');if(x<0)pc('-'),x=-x;
    while(x)q[cnt++]=x%10+'0',x/=10;
    while(cnt--)pc(q[cnt]);
}
const int maxn=25,saxn=(1<<22)+9;
int c[2][maxn],t[2][saxn];
long long ans=0;
void build(int x,int st,int l,int r){
    ++c[0][st],++c[1][st];
    t[0][x]=t[1][x]=0;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(x<<1,st+1,l,mid);
    build(x<<1|1,st+1,mid+1,r);
}
int op;
void change(int x,int st,int l,int r,int pos){
    ans-=1ll*c[op][st]*c[!op][st];if(t[op][x]!=2)--c[op][st];
    if(l==r)t[op][x]^=1;else{
        int mid=(l+r)>>1;
        if(pos<=mid)change(x<<1,st+1,l,mid,pos);
        else change(x<<1|1,st+1,mid+1,r,pos);
        if(t[op][x<<1]!=2&&t[op][x<<1]==t[op][x<<1|1])
        t[op][x]=t[op][x<<1];else t[op][x]=2;
    }
    if(t[op][x]!=2)++c[op][st];ans+=1ll*c[op][st]*c[!op][st];
}
int main(){
    int n,q;read(n),read(q);build(1,0,1,1<<n);
    long long sum=ans=((1ll<<(2*n+2))-1)/3;
    while(q--){
        int x;
        read(op),read(x);
        change(1,0,1,1<<n,x);
        write((sum-ans)*4+1),pc('\n');
    }
    return 0;
}