「Codeforces 1090H」Linearization

Codeforces 1090H. Linearization

题意

定义一个长度为 $n(n=2^k,k\in N)$ 的 01 串 $s$（从 0 开始标号）是线性的，当且仅当存在整数 $x$ 和 二进制数位 $b$，使得 $\forall i\in [0,n),s_i=P(i{\rm and}x){\rm xor}b$，\mathrm{其}\mathrm{中}$P(a)$\mathrm{表}\mathrm{示}$a$\mathrm{的}\mathrm{二}\mathrm{进}\mathrm{制}\mathrm{表}\mathrm{示}\mathrm{中}$1$ 的数量的奇偶性

定义一个 01 串的线性化难度为，进行最少的取反一个区间的操作，使之成为线性的操作次数

给定一个长度为 $m$ 的 01 串 $t$，$q$ 次询问指定一个子串，要求计算其线性化难度

$m,q\le 2\times {10}^5$

做法

看了 毛子语的试题分析 才会

先考虑一个长度为 $2^k$ 的 01 串 $s$ 是线性的等价条件

把 $s$ 分成两个 $2^{k-1}$ 的串：

• 两部分都是线性的
• 两部分相等或相反

考虑差分，令 $t_i=s_i{\rm xor}s_{i-1},1\le i < 2^k$

于是上述限制转化为 $\mathrm{\forall }i\in [1,2^{k-1}),t_i=t_{i+2^{k-1}}$，并且递归两侧

理性分析一下

• 递归保证了两部分都是线性的
• 两部分相等或相反即最左侧的位置相同或不同，只考虑剩余的位即可

这些限制把 $2^k-1$ 个位置划分为若干联通块，联通块内的位置要全都相等，此时贪心地取 $0$ 和 $1$ 中较少的一个改变即可

假设求出最后最少需要改变的 $t$ 序列中的位置有 $a$ 个，答案即为 $\lfloor \frac{a+1}{2}\rfloor$，因为每次区间取反可以改变 $2$ 个位置

直接做显然无法通过，观察一下联通块可以发现

只有 $k$ 个联通块，第 $i$ 个联通块是以 $2^{i-1}$ 开头的步长为 $2^i$ 的等差数列

直接预处理即可

复杂度 $\mathcal{O}((m+q)\log m)$

代码

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<string.h>
#include<cmath>
#include<vector>

using namespace std;
#define ll long long

inline char read() {
	static const int IN_LEN = 1000000;
	static char buf[IN_LEN], *s, *t;
	return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
	static bool iosig;
	static char c;
	for (iosig=false, c=read(); !isdigit(c); c=read()) {
		if (c == '-') iosig=true;
		if (c == -1) return;
	}
	for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
	if (iosig) x=-x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *ooh=obuf;
inline void print(char c) {
	if (ooh==obuf+OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh=obuf;
	*ooh++=c;
}
template<class T>
inline void print(T x) {
	static int buf[30], cnt;
	if (x==0) print('0');
	else {
		if (x<0) print('-'), x=-x;
		for (cnt=0; x; x/=10) buf[++cnt]=x%10+48;
		while(cnt) print((char)buf[cnt--]);
	}
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }

const int N = 200005, M = 18;
int n, q, f[M][N];
char s[N];
int main() {
	read(n);
	while(isspace(s[0]=read()));
	for(int i=1; i<n; ++i) s[i]=read();
	for(int i=n; --i;) s[i]^=s[i-1];
	for(int i=1; 1<<i<n; ++i){
		for(int j=0; j<1<<i; ++j) f[i][j]=s[j];
		for(int j=1<<i; j<n; ++j) f[i][j]=f[i][j-(1<<i)]+s[j];
	}
	read(q);
	while(q--){
		int l, r, len, now, ans=0;
		read(l), read(r), now=r, len=r-l+1;
		for(int i=1; 1<<i<len; ++i){
			int x=f[i][now]-(now>=len?f[i][now-len]:0);
			ans+=min(x, len/(1<<i)-x), now-=1<<(i-1);
		}
		print((ans+1)/2), print('\n');
	}
	return flush(), 0;
}