题解：P14431 [JOISC 2013] 有趣的图像收集 / Collecting Images is Fun
dyc2022
·
·
题解
更好的阅读体验
我们可以用四分树的性质来看这个问题。不会也没关系。
考虑一个树形结构，每个节点代表一个正方形。
- 如果当前节点代表的正方形全黑或全白，那么这个节点是叶子节点。
- 否则将这个正方形分割成四个小正方形，作为这个节点的 4 个子节点。
答案就是树上节点个数。
显然的性质就是每个点有 0 / 4 个儿子。所以我们可以把一个点的贡献挂在他的父亲上，然后再加上整棵树的根节点。所以假设有 k 个非叶子节点，那么答案就是 4 \cdot k + 1。
容易发现，一个正方形在若干次翻转行列的操作后全黑或全白，当且仅当：每行被翻转次数的奇偶性相同，并且每列被翻转的奇偶性相同。
证明非常简单。假设有两列翻转次数的奇偶性不同，那么在每一行上，这两列对应的格子颜色都是相反的，不满足题意。
我们又发现，行和列是相互独立的。所以可以单独算行和列的答案，然后乘起来。
所以问题就转化为单点修改，求线段树上同色的节点数量。由于单点修改是一个叶子的到根链的修改，所以直接做就好了。
然后这道题就做完了。复杂度 $O(2^n n)$。
```cpp
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 1200006
using namespace std;
int n,sz,q,cnt[2][26],all;
struct Segtree {
struct Node {
int flag,col;
friend Node operator +(Node x,Node y)
{
Node ret={0,0};
if(x.flag&&y.flag&&x.col==y.col)ret=x;
return ret;
}
} tree[N<<2];
void build(int p,int l,int r,int dep,int *c)
{
if(l==r)return tree[p]={1,0},(void)0;
int mid=l+r>>1; build(p<<1,l,mid,dep+1,c),build(p<<1|1,mid+1,r,dep+1,c);
tree[p]=tree[p<<1]+tree[p<<1|1];
c[dep]+=tree[p].flag;
}
void update(int p,int l,int r,int k,int dep,int *c)
{
if(l==r)return tree[p].col^=1,(void)0;
c[dep]-=tree[p].flag; int mid=l+r>>1;
k<=mid?update(p<<1,l,mid,k,dep+1,c):
update(p<<1|1,mid+1,r,k,dep+1,c);
tree[p]=tree[p<<1]+tree[p<<1|1];
c[dep]+=tree[p].flag;
}
} T[2];
main()
{
scanf("%lld%lld",&n,&q),sz=1ll<<n;
for(int i=1,num=1;i<=n;i++,num<<=2)all+=num;
for(int i=0;i<2;i++)T[i].build(1,1,sz,1,cnt[i]);
while(q--)
{
int opt,k,c=0; scanf("%lld%lld",&opt,&k);
T[opt].update(1,1,sz,k,1,cnt[opt]);
for(int i=1;i<=n;i++)c+=cnt[0][i]*cnt[1][i];
c=all-c,printf("%lld\n",c*4+1);
}
return 0;
}
```