CF1511G Chips on a Board （倍增）
题面
转化方便版题意：
有
n
n
n 堆石子，第
i
i
i 堆有
c
i
∈
[
1
,
m
]
c_i\in [1,m]
ci∈[1,m] 个石子，有
q
q
q 次询问，每次询问给出
L
i
,
R
i
L_i,R_i
Li,Ri ，先把
c
i
∉
[
L
i
,
R
i
]
c_i\not\in [L_i,R_i]
ci∈[Li,Ri] 的石堆都扔掉，然后把每堆石子减少
L
i
L_i
Li 个，最后用剩下的若干堆石子做
N
i
m
Nim
Nim 游戏，先手必胜输出
A
\tt A
A ，后手必胜输出
B
\tt B
B 。
1
≤
n
,
m
,
q
≤
2
⋅
1
0
5
1\leq n,m,q\leq2\cdot10^5
1≤n,m,q≤2⋅105.
题解
官方题解，是
O
(
N
N
log
N
)
O(N\sqrt{N\log N})
O(NNlogN
) 的做法。
对每个询问暴力求解，是
O
(
N
2
)
O(N^2)
O(N2) 的。或者，如果记录每一种
c
i
c_i
ci 值的出现次数的话，也可以是
O
(
N
M
)
O(NM)
O(NM) 的。后者可以优化：
c
i
c_i
ci 的二进制表示有
18
\tt18
18 位，我们把前面九位和后面九位分开算，这样，分别就只有
2
9
=
512
2^9=512
29=512 种取值，也就是
M
\sqrt{M}
M
种取值了，这就增加了暴力的可能性。同时，只管前九位和后九位都是能比较方便地处理加减法的，因此这样刚好是可行的，要是分成前六位、中六位、后六位就及其不好做了。
但是，处理后九位数字还是比较麻烦的。而且，这个时间复杂度也不优。
不如看看下面又易懂又好写还在时间复杂度上暴踩官解的做法。
真是妙蛙种子吃着妙脆角，妙进了米奇妙妙屋，妙到家了
真的就不能每一位分开来做了吗？
加减法固然会对二进制表示产生不好计量的影响，但是我们有这么一条很容易发现的结论：
- 若
A
<
2
k
A<2^k
A<2k ，则
A
+
2
k
=
A
x
o
r
2
k
A+2^k=A~xor~2^k
A+2k=A xor 2k
这种情况下，加法是等同于异或的！
那我们不妨就想个办法，能不能把减法变成加法，然后把要加的部分按位拆分开来，利用上面的结论一步一步异或进去呢？
有！那就是倍增。倍增可以把减法换成加法，而且不难发现，倍增刚好是从高位往低位考虑的，前面要加的数的 lowbit 一定比后面的数都大。
我们定义
f
[
i
]
[
j
]
f[i][j]
f[i][j] 为询问
L
=
i
,
R
=
i
+
2
j
−
1
L=i,R=i+2^j-1
L=i,R=i+2j−1 时的答案，不难发现
f
[
i
]
[
0
]
=
0
f[i][0]=0
f[i][0]=0。
计算
f
[
i
]
[
j
]
f[i][j]
f[i][j] 的时候，先异或上
f
[
i
]
[
j
−
1
]
f[i][j-1]
f[i][j−1] ，然后由于
f
[
i
+
2
j
−
1
]
[
j
−
1
]
f[i+2^{j-1}][j-1]
f[i+2j−1][j−1] 中的每堆石子个数
<
2
j
−
1
< 2^{j-1}
<2j−1 ，我们把这些石堆加上
2
j
−
1
2^{j-1}
2j−1 时，等价于异或
2
j
−
1
2^{j-1}
2j−1，因此我们只需要再知道
[
i
+
2
j
−
1
,
i
+
2
j
−
1
]
[i+2^{j-1},i+2^j-1]
[i+2j−1,i+2j−1] 区间之内石堆的个数，就可以转移了。令
c
t
[
i
]
[
j
]
ct[i][j]
ct[i][j] 表示
c
i
∈
[
i
,
i
+
2
j
−
1
]
c_i\in[i,i+2^j-1]
ci∈[i,i+2j−1] 的石堆的个数，则：
f
[
i
]
[
j
]
=
f
[
i
]
[
j
−
1
]
x
o
r
f
[
i
+
2
j
−
1
]
[
j
−
1
]
x
o
r
(
2
j
−
1
⋅
(
c
t
[
i
+
2
j
−
1
]
[
j
−
1
]
%
2
)
)
c
t
[
i
]
[
j
]
=
c
t
[
i
]
[
j
−
1
]
+
c
t
[
i
+
2
j
−
1
]
[
j
−
1
]
f[i][j]=f[i][j-1]~{\tt xor}~f[i+2^{j-1}][j-1]~{\tt xor}~\Big( 2^{j-1}\cdot(ct[i+2^{j-1}][j-1]\,\%\,2) \Big)\\ ct[i][j]=ct[i][j-1]+ct[i+2^{j-1}][j-1]
f[i][j]=f[i][j−1] xor f[i+2j−1][j−1] xor (2j−1⋅(ct[i+2j−1][j−1]%2))ct[i][j]=ct[i][j−1]+ct[i+2j−1][j−1]
询问的时候，类似的。由于是倍增，每次访问到的
f
[
i
]
[
j
]
f[i][j]
f[i][j] 的
j
j
j 都会变小，也就是说它所代表的这个区间内的石堆
c
i
c_i
ci 都小于先前的
2
j
2^j
2j ，都可以把加法换成异或，再通过
c
t
[
i
]
[
j
]
ct[i][j]
ct[i][j] 补到
f
[
i
]
[
j
]
f[i][j]
f[i][j] 中。
代码也很好理解，基本是标准的预处理倍增。时间复杂度只有
O
(
N
log
N
)
O(N\log N)
O(NlogN) 。
CODE
比解说还短的倍增代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 200005
#define ENDL putchar('\n')
#define LL long long
#define DB double
#define lowbit(x) ((-x) & (x))
LL read() {
LL f = 1,x = 0;char s = getchar();
while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
return f * x;
}
int n,m,i,j,s,o,k;
int c[MAXN],dp[MAXN][20],ct[MAXN][20];
int main() {
// Input
n = read();m = read();
for(int i = 1;i <= n;i ++)
c[i] = read(),ct[c[i]][0] ++;
// Init
for(int i = m;i > 0;i --) {
for(int j = 1;i+(1<<j)-1 <= m;j ++) {
ct[i][j] = ct[i][j-1] + ct[i+(1<<(j-1))][j-1];
dp[i][j] = dp[i][j-1] ^ dp[i+(1<<(j-1))][j-1] ^ ((ct[i+(1<<(j-1))][j-1] & 1) ? (1<<(j-1)):0);
}
}
// Query
int q = read();
while(q --) {
s = read();o = read();
int xr = 0,as = 0;
for(int j = 18;j >= 0;j --) {
if(s+(1<<j)-1 <= o) {
as ^= dp[s][j]^((ct[s][j] & 1) ? xr:0);
xr ^= (1<<j); s += (1<<j);
}
}
printf(as ? "A":"B");
}
return 0;
}
最新文章
- 基础笔记（三）：网络协议之Tcp、Http
- UIImageView 自带动画+N张图片实现很炫的动画
- vue.common.js?e881:433 TypeError: Cannot read property 'nodeName' of undefined
- linux命令：du
- Python学习（基础简绍）
- 中国式IT的项目
- requireJS的使用_API（1）
- [PHP-Socket] Socket Programming in PHP
- codeforces 712A A. Memory and Crow(水题)
- 状态压缩 + 暴力 HDOJ 4770 Lights Against Dudely
- oracle 存储过程基础
- windows core audio apis
- 【转】MTK Android Driver知识大全
- 【细说Java】揭开Java的main方法神秘的面纱
- URAL 1728. Curse on Team.GOV（STL set）
- 简单的mvc之一：简单的开始
- win10 uwp json
- 史上最简单的MySQL安装教程之Linux(CentOS6.8)下安装MySQL5.6
- canvas 水波纹
- js的一些总结
热门文章
- CF908D New Year and Arbitrary Arrangement 题解
- Mac Book安装Windows发烫的问题
- BI与SaaS碰撞，让数据处理更加轻松（下）
- Java-调用R语言和调用Python（前后端展示）
- 我熬夜开发了一款简约实用、支持多平台的Markdown在线编辑器（开源）
- 『现学现忘』Docker基础 — 38、COPY指令和ADD指令
- SAP Web Dynpro - 个性化和配置
- Python程序入口 __name__ == ‘__main__‘ 有重要功能（多线程）而非编程习惯
- Linux编辑shell脚本快速启动jar包
- 异构图神经网络笔记-Heterogeneous Graph Neural Network(KDD19)