「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\)，其中 \(P(a)\) 表示 \(a\) 的二进制表示中 \(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\)

于是上述限制转化为 \(\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;
}