「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)\)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#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;
}
0%