为什么打表就我看不出规律！！！
定式思维太严重了T_T
纯智障分块题，不知道为什么 B = 100 B=100 B=100 比理论最优 B = 300 B=300 B=300 更优（快了 3 倍），看来分块还是要学习一些卡常技巧的
菜死了，不会
菜死了，不会
神奇的式子，考虑打表
打表！！！
可以发现一下两个规律：
考虑证明：
考虑
x
+
y
x+y
x+y 必须为偶数因为一直循环下去
x
+
y
x+y
x+y 的值不变
f
(
x
,
y
)
=
f
(
x
d
,
y
d
)
f(x,y)=f(\frac{x}{d},\frac{y}{d})
f(x,y)=f(dx,dy) 是易得的
我们只需要考虑
x
,
y
x,y
x,y 都为奇数的情况，因为
x
,
y
x,y
x,y 为偶数时
2
∣
gcd
(
x
,
y
)
2|\gcd(x,y)
2∣gcd(x,y)
令
x
>
y
x>y
x>y，则
f
(
x
,
y
)
=
f
(
2
y
,
x
−
y
)
+
1
f(x,y)=f(2y,x-y)+1
f(x,y)=f(2y,x−y)+1
因为
2
y
,
x
−
y
2y,x-y
2y,x−y 都为偶数，所以
f
(
x
,
y
)
=
f
(
y
,
x
−
y
2
)
+
1
f(x,y)=f(y,\frac{x-y}{2})+1
f(x,y)=f(y,2x−y)+1
这样
x
′
+
y
′
x'+y'
x′+y′ 的值就除了
2
2
2，且因为
gcd
(
x
,
y
)
=
1
\gcd(x,y)=1
gcd(x,y)=1，所以
gcd
(
y
,
x
−
y
2
)
=
1
\gcd(y,\frac{x-y}{2})=1
gcd(y,2x−y)=1
所以
x
+
y
x+y
x+y 只有当是
2
2
2 的次幂时，
x
′
=
y
′
x'=y'
x′=y′，且操作次数为
l
o
g
2
(
x
+
y
)
log_2(x+y)
log2(x+y)
我们发现这有值的点对个数是
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) 级别的
所以我们可以把所有有值的点对找出来，然后询问就相当于二维数点了
离线询问 + 扫描线 + 树状数组即可
时间复杂度
O
(
n
l
o
g
2
n
)
O(nlog^2n)
O(nlog2n)
#include 不说了，思想比较简单，就是分块 + 块内用优先队列维护
时间复杂度
O
(
n
m
l
o
g
n
)
O(n\sqrt mlogn)
O(nmlogn)，
m
m
m 为修改操作个数
块长设为
100
100
100 实测最优
#pragma GCC optimize(3)
#include 感觉是到有点 nb 的题
不考虑翻转，如何求
l
i
s
lis
lis？
考虑枚举分界点
i
i
i，那么答案
=
max
{
i
前面
0
的个数
+
i
后面
1
的个数
}
=\max\{i前面0的个数+i后面1的个数\}
=max{i前面0的个数+i后面1的个数}
这等价于
s
1
+
max
i
=
1
n
s
u
m
i
s1+\max\limits_{i=1}^{n} sum_i
s1+i=1maxnsumi，其中
s
1
s1
s1 为序列中
1
1
1 的个数，
s
u
m
i
sum_i
sumi 为把
0
0
0 的权值设为
1
1
1，
1
1
1 的权值设为
−
1
-1
−1 的前缀和
考虑翻转操作
我们可以把这个问题等价地看成选出一段前缀和与
m
m
m 段不相交子区间（不能与前缀相交）的和的最大值
这一步感觉很难想，也很难理解
具体我也不会证，只能自己画图感性理解
然后就是经典的反悔贪心操作了，找最大的区间，然后区间取反，用线段树维护即可
时间复杂度
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
#include 考虑暴力是 f i , j f_{i,j} fi,j 表示当前在 i i i，前一个选 j j j 的最大长度，因为 p i ≠ k p_i\neq k pi=k 的限制很松，所以直接记录最大值和次大值就可以维护，时间复杂度 O ( n 3 ) O(n^3) O(n3)
于是我们可以猜测需要保留的转移状态不会太多，事实上是真的
我们令三元组
(
l
e
n
t
h
,
p
r
e
,
i
)
(lenth,pre,i)
(lenth,pre,i) 表示当前在
i
i
i，上一个在
p
r
e
pre
pre，长度为
l
e
n
t
h
lenth
lenth 的状态
我们考虑用这个东西转移
每次答案，我们需要把
a
j
<
a
i
a_j
结论1：对于
i
i
i 只需要保留
l
e
n
t
h
lenth
lenth 最长的两个且满足
j
p
≠
j
q
j_p\neq j_q
jp=jq 的状态
首先
j
j
j 相等的状态只需要保留一个，那么后面最多只会排除掉
1
1
1 个状态，所以只需要暴力
2
2
2 个状态
结论2：只需要取出
(
l
e
n
t
h
,
p
r
e
,
j
)
(lenth,pre,j)
(lenth,pre,j) 的前
5
5
5 大
l
e
n
t
h
lenth
lenth，且对于
p
r
e
pre
pre 相同的，我们只保留最大的
2
2
2 个
为什么，考虑如果前两个的
p
r
e
pre
pre 都和
i
i
i 一样，那么后两个必然有两个
p
r
e
pre
pre 不相同的，是可以更新出
2
2
2 个有效答案的
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)（但常数有点大，我稍微卡了一下常）
#pragma GCC optimize(3)
#include