20260306
T1
线段树套线性基模板。
T2
看了题解，感觉很妙。
首先，注意到题目要支持可持久化的操作，但是没有要求强制在线，于是可以用操作树（个人感觉就相当于把历史状态关系建成了一棵树），大概代码如下。
void dfs(int T){
//操作
//查询
for(int i=head[T];i;i=edge[i].nxt) dfs(edge[i].to);//到下个时间节点
//撤销操作
}
放到这题，类似并查集，又可撤销。只需要用可撤销并查集，用按秩合并即可。
接下来，求第
k
k
k 大，查询。套个分块就行了。用
c
n
t
[
B
l
o
c
k
]
[
i
]
cnt[Block][i]
cnt[Block][i]，表示第
i
i
i 个并查集
a
a
a 数组编号所在块为 Block 的总数。
然而，MLE。20MB？调整块长，卡卡，过了。
在卡常时，还发现了一个卡常小技巧，就比如：
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
dp[i][j]+=dp[i–1][j];
改成
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
dp[j][i]+=dp[j][i–1];
就会变慢，原因是访问地址什么的。
T3
赛时发现好像可以费用流，只用把每个
a
i
a_i
ai 质因数分解，暴力建边？时间复杂度
O
(
玄学
)
O(玄学)
O(玄学)。
打了半个多小时，提交，TLE了，发现质因数分解多带了一只根号。开始脑残，Miller_Rubbin！卡过去了，成功砍下最劣解。
int calc(int x){
int cnt=0;
for(int i=2;i*i<=x;i++)
if(!(x%i)){
bool pd=is_prime_Miller(i);//本来就是质数
while(!(x%i)) x/=i,cnt+=pd;
}
return cnt+is_prime(x)/*其实只用改成x>1就可以了*/;
}
20260307~20260308
GDOI。
Day 1，T1 理解错题意，以为直接用期望长度算概率，再写背包就可以了，小样例一直过不了，卡 2h 才发现。最后
O
(
n
3
)
O(n^3)
O(n3) 都没调出来。
Day 2 脑残了，T1 询问次数
n
+
log
2
n
n+\\log_2n
n+log2n，多加了一个
log
2
n
\\log_2n
log2n 的查询
0
0
0 的位置（其实完全可以用那
n
n
n 个去扫描时判掉）。T3，暴力打挂了。
20260309
T1
不难发现，当一个矩阵被另一个包含时，它一定没用。
然后，赛时只想出一个
O
(
n
2
)
O(n^2)
O(n2) 的方法，设
f
[
i
]
[
j
]
f[i][j]
f[i][j] 表示后
i
i
i 行前
j
j
j 个有放点，转移很容易。但是，就算用前缀和优化也只有
O
(
n
2
)
O(n^2)
O(n2)。
后来，看了题解。注意到，它这
n
n
n 形如阶梯状的方格会将整个图分成
n
×
(
n
−
1
)
n \\times (n-1)
n×(n−1) 个格子，每个格子的大小对应到决策
[
l
,
r
]
[l,r]
[l,r] 只能选一个的方案数。就可以只用设一个一维的状态，
O
(
n
)
O(n)
O(n)。
T2
赛时，想出来了，打起来感觉很麻烦，没打。
其实就是，将它分成左右两边分别去处理，注意到是个凹函数，用三分套个树状数组解决。
T3
没学过线段树分治，先自学了一下，感觉就只利用了线段是将区间
[
l
,
r
]
[l,r]
[l,r] 分成
log
n
\\log n
logn 块的性质，其它跟线段树一点关系都没有。具体实现大致框架如下：
void change(int rt,int l,int r,int L,int R,int x,int y){
if(l==L&&r==R){
v[rt].push_back({x,y});//记录操作
return;
}
int mid=l+r>>1;
if(R<=mid) change(rt<<1,l,mid,L,R,x,y);
else if(mid+1<=L) change(rt<<1|1,mid+1,r,L,R,x,y);
else change(rt<<1,l,mid,L,mid,x,y),change(rt<<1|1,mid+1,r,mid+1,R,x,y);
}
void dfs(int rt,int l,int r){
for(auto i:v[rt]) //do something for i
if(l==r){
// get answer
return;
}
int mid=l+r>>1;
dfs(rt<<1,l,mid),dfs(rt<<1|1,mid+1,r);
for(auto i:v[rt]) //Clear i
}
回到此题。
听了 @BirdenT 大佬的讲题，%%%。
对于这题，可以想到一个贪心策略：先改大的，后改小的（因为会被覆盖）。
对于颜色
x
x
x，即通过若干个
a
i
=
x
a_i=x
ai=x 的点
i
i
i，去将所有的
b
j
=
x
b_j=x
bj=x 的点修改。在
i
i
i 到
j
j
j 的路径上的所有点
k
k
k，我们分两种情况考虑。
- Case 1：
a
k
<
x
a_k<x
ak<x，显然不合法（根据题意）。 - Case 2：
b
k
>
x
b_k>x
bk>x，由贪心策略可知，不合法。
综上，一条边
(
i
,
j
)
(i,j)
(i,j) 出现仅在处理
[
max
(
b
i
,
b
j
)
,
min
(
a
i
,
b
j
)
]
[\\max(b_i,b_j),\\min(a_i,b_j)]
[max(bi,bj),min(ai,bj)] 的颜色时。
对于每个颜色，判断一下所有
b
j
=
x
b_j=x
bj=x 的
j
j
j 是否存在
a
i
=
x
a_i=x
ai=x 的
i
i
i 并且满足
(
i
,
j
)
(i,j)
(i,j) 相互联通，直接用线段树分治即可。
