P4443 [COCI2017-2018#3] Dojave 题解
Blueqwq
·
·
题解
P4443 [COCI2017-2018#3] Dojave 题解
更好的阅读体验
前言：
不知道为什么都用的哈希，我的优化暴力全都均摊了，直接最优解（
简要题意：
给定 m 和 0\sim 2^m-1 的全排列 a_i，问有多少子区间满足交换两个不同位置后，整个区间异或和为 2^m-1。
---
分析：
正难则反，考虑求出不合法的区间个数。
以下记 $n=2^m-1$。
结论：
若区间内异或和为 $0$，并且可以两两配对使得两两异或和为 $n$，则这个区间不合法。
证明：
首先如果区间异或和已经为 $n$，那么只需要交换区间内或区间外的两个数即可。
否则，设区间 $S$ 的异或和为 $t$。
那么就是找一对 $i,j$ 使得 $i\oplus j=t\oplus n(i\in S,j\notin S)$，不难看出 $i,j$ 一定是成对出现的，那么若想要不合法，唯一的可能是集合内两两配对的异或和为 $t\oplus n$。
问题转化为找到这种情况。
奇数长度的一定合法，因为一定能找到一个数，和它配对的在区间外。
对于偶数长度的情况，如果配对数量为奇数，不妨以三个为例，有：
$$
(t\oplus n)\oplus (t\oplus n)\oplus (t\oplus n)=t\oplus n\ne t
$$
由于 $n\ne 0$，显然不存在这种情况。
配对数量为偶数的，不妨以两个为例，有：
$$
(t\oplus n)\oplus (t\oplus n)=0=\!\!\!\!?\ \ t
$$
也就是说，当 $t=0$ 时这个区间不合法，那么两两配对的异或和就是 $n$ 了。
至此证毕，下面考虑统计。
定义 $link_i$ 表示与 $a_i$ 配对的数的位置，即 $pos_{n\oplus a_i}$。
对于区间 $[l,p]$ 和 $[p+1,r]$，如果这两个区间都不合法，则 $[l,r]$ 也一定不合法，这点通过结论不难看出，那么我们只需要找对于每个点最近的不合法位置在哪里即可。
考虑一个最暴力的拓展方法，枚举一个左端点 $l$，那么右端点 $r$ 至少应在 $link_l$，下面判断这个区间是否合法。
- 如果 $\exists\,p\in[l,r],link_p<l$，即区间内存在一个数，与其配对的数在 $l$ 左边，那么直接跳出，因为我们钦定了 $l$ 为左端点。
- 如果 $\exists\,p\in[l,r],link_p>r$，那么更新 $r=link_p$，再重复这个过程，直到跳出或者 $\forall\, p\in[l,r],l\le link_p\le r$，即区间内两两配对。
这样的暴力做法可以找到每个最短的不合法区间，利用双指针可以在 $O(n^2)$ 的时间内求出，下面考虑优化。
注意到我们暴力跳右端点的时候，跳出或者更新答案的点都是区间 $link$ 最小值或最大值，那么就可以在 $O(mn)$ 的时间内预处理出 $link$ 的 ST 表实现 $O(1)$ 更新。
之后对于每个点暴力跳的复杂度就变成了均摊 $O(1)$ 的，简要证明如下：
对于每一对匹配 $(i,link_i)$，设 $i<link_i$，那么当左端点枚举到 $i$ 的时候看起来会很暴力的一直跳过去，极限状态下单次 $O(n)$，但当左端点枚举到 $link_i$ 的时候，右端点 $i<link_i$ 会直接跳出，所以实际上每一对匹配只会跳一次，均摊 $O(1)$。
统计同理，暴力枚举左端点，暴力跳最近的不合法区间，由于我们要计算的区间长度必须为 $4$ 的倍数，那么只需要统计一路上 $\bmod 4$ 同余的个数即可，为了防止算重，对于每个跳到的点标记一下，如果枚举到了标记点直接跳过即可，每个点的时间复杂度同样是均摊 $O(1)$。
总时间复杂度为 $O(mn+n+n)=O(mn)=O(m\times 2^m)$。
此外注意特判 $m=1$ 的情况，因为 $0$ 和 $1$ 一定交换，所以单独一个 $1$ 是不合法的，最终答案应该为 $2$。
代码如下：
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1050000;
//此处为快读快写
int n,m;
ll ans;
int a[N],pos[N],link[N],nxt[N];
int md[5],stn[21][N],stx[21][N],pw[N];
bool vis[N];
//ST 表
void init(){
for(int i=2;i<=n;i++)
pw[i]=pw[i>>1]+1;
for(int i=1;i<=n;i++)
stn[0][i]=stx[0][i]=link[i];
for(int i=1;i<=m-1;i++)
for(int j=1;j+(1<<i)-1<=n;j++)
stn[i][j]=min(stn[i-1][j],stn[i-1][j+(1<<(i-1))]),
stx[i][j]=max(stx[i-1][j],stx[i-1][j+(1<<(i-1))]);
}
int querymin(int l,int r){
int k=pw[r-l];
return min(stn[k][l],stn[k][r-(1<<k)+1]);
}
int querymax(int l,int r){
int k=pw[r-l];
return max(stx[k][l],stx[k][r-(1<<k)+1]);
}
signed main(){
m=read();n=(1<<m);
if(m==1) return puts("2"),0;
ans=1ll*n*(n+1)/2;
for(int i=1;i<=n;i++)
a[i]=read(),pos[a[i]]=i;
for(int i=1;i<=n;i++)
link[i]=pos[n-a[i]-1];
init();
for(int i=1;i<=n;i++){
int l=i,r=link[i];
Find:;
if(querymin(l,r)<i) continue;//左端点小于钦定的 l，就跳出。
int mx=querymax(l,r);
if(mx>r){r=mx;goto Find;}//有更远的右端点，重复这个过程。
nxt[i]=r;//记 nxt 表示最近的不合法右端点。
}
for(int i=1;i<=n;i++){
if(vis[i]||!nxt[i]) continue;//标记过这个点或区间不存在就跳过。
for(int j=0;j<=3;j++)
md[j]=0;
int nw=i;md[i&3]++;
//暴力跳 nxt 并统计。
while(nxt[nw]){
nw=nxt[nw]+1;
ans-=md[nw&3];
md[nw&3]++;
vis[nw]=true;
}
}
write(ans);
return 0;
}
```