【DP】 [COCI2017-2018#3] Dojave

题意：

给出一个长为$2^m$得排列a
求满足以下条件的区间$[l,r]$的数量
1、交换排列a中两个元素的位置。（交换操作不保留）
2、令$a_l\otimes a_{l+1}\otimes a_{l+2}\otimes ……\otimes a_r=2^m-1$

分析：

首先，设一个区间中的某个值为$x$
若换出x，再换入一个数$y$，使得整个序列的xor和为$2^m-1$
那么就必须满足条件：$sum\otimes x\otimes y=2^m-1$（sum表示$[l,r]$的xor和）
显然，x与y是一一对应的。

如果这个y不在$a[l,r]$中，那么直接换这个就可以了。

讨论y也在$a[l,r]$中的情况：
那么$sum_{去掉x去掉y}=2^m-1$

如果对于整个区间的数，只要有一个x，其对应的y不在这个区间内，那么就可以换这个值。

如果找不到，那么整个区间就可以用许多对(x,y)填满。

这时，很容易发现：每对(x,y)满足$x\otimes y$是定值（因为去掉任意一对，剩下的xor和都等于$2^m-1$）。

那么这个$sum$就可以看作是数个相同的值的xor和，那么必然满足：如果是奇数个，那么xor和为这个数本身，偶数个，xor和为0。

由于$sum_{去掉x去掉y}=2^m-1≠0$，所以每对$(x,y)$都满足：$x\otimes y=2^m-1$

综上，一个区间非法的条件是：长度为4的倍数，且对于区间中任意一个数$x$，满足$(2^m-1\otimes x)$也在这个区间中。

如果对每个$x$，把它向$2^m-1\otimes x$连一条边
然后要求的无非就是：长度为4的倍数的区间$[l,r]$，且没有边从内部跨过l,r的数量。

然后就有个性质，对每个位置$p$而言，假设覆盖了它的边有$cnt_p$条。
那么若以其为右端点，最近的非法区间左端点位置$i$必然满足：$cnt_i=cnt_p$且不存在一个数$j\in (i,p),满足cnt_j=cnt_p$（说白了就是上一个覆盖数相同的位置）。当然，若其没有非法左端点，仍然可能找到一个位置，所以要用线段树之类的东西check一下。

然后用dp转移就行了
$dp(i,0/1)$表示以i为右端点，长度len%4=0,len%4=2的区间各有多少个。
$dp(i,0)=dp(go_i,0\otimes (\frac {len} 2\%2))+1$（+1表示空区间）
$dp(i,1)=dp(go_i,1\otimes (\frac {len} 2\%2))$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN ((1<<20)+10)
#define INF 0x3FFFFFFF
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int a[MAXN],pos[MAXN],t[MAXN],las[MAXN],go[MAXN];
int cnt;
int n,m;
int dp[MAXN][2];
pair<int,int> tree[MAXN*4];
void build(int l,int r,int id){if(l==r){tree[id]=make_pair(t[l],t[l]);return ;}int mid=(l+r)>>1;build(l,mid,id*2);build(mid+1,r,id*2+1);tree[id].first=max(tree[id*2].first,tree[id*2+1].first);tree[id].second=min(tree[id*2].second,tree[id*2+1].second);
}
pair<int,int> que(int l,int r,int id,int pl,int pr){if(l>=pl&&r<=pr)return tree[id];int mid=(l+r)>>1;pair<int,int> res=make_pair(0,INF);if(pl<=mid){pair<int,int> res1=que(l,mid,id*2,pl,pr);res.first=max(res.first,res1.first);res.second=min(res.second,res1.second);}if(pr>mid){pair<int,int> res1=que(mid+1,r,id*2+1,pl,pr);res.first=max(res.first,res1.first);res.second=min(res.second,res1.second);}return res;
}
bool check(int l,int r){pair<int,int> q=que(1,m,1,l,r);return q.first<=r&&q.second>=l;
}
int main(){SF("%d",&n);if(n==1){PF("2");return 0;}m=(1<<n);for(int i=1;i<=m;i++){SF("%d",&a[i]);pos[a[i]]=i;}for(int i=1;i<=m;i++)t[i]=pos[(m-1)^a[i]];for(int i=1;i<=m;i++){if(t[i]<i){cnt--;go[i]=las[cnt];las[cnt]=i;}else{cnt++;las[cnt]=i;}}ll ans=1ll*(m+1ll)*m/2ll;build(1,m,1);dp[0][0]=1;for(int i=1;i<=m;i++){dp[i][0]=max(1,dp[i][0]);if(t[i]>i)continue;if(check(go[i]+1,i)){int len=((i-go[i])%4)/2;ans-=dp[go[i]][len];dp[i][0]=dp[go[i]][0^len];dp[i][1]=dp[go[i]][1^len];dp[i][0]++;//PF("[%d %d %d %lld]\n",go[i]+1,i,len,ans);}}PF("%lld",ans);
}