__vector__ 的博客本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-08 20:20:17
设 $f(s)$ 为最终 and 的的结果包含 $s$ 中所有的 $1$ 的方案数。
若 $popcount(x)$ 是偶数，那么答案加上这个 $f(x)$，否则减去 $f(x)$。
$f(s)$ 如何计算呢？
考虑求出所有满足 $x$ and $s = x$ 的 $x$，然后这些数可以任意选择，只是至少需要选择一个。
但是这些 $x$ 的数量如何求呢？
可以将这个过程视为一个 20 维的后缀和，每一维大小为 $2$，使用 sosdp 搞定。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-08 21:57:32
这次又没能自己做出来，卡死在了线性筛那一步，参照的这篇题解。
$f(n)$ 代表 $n$ 的质因子的最大幂指数。
假设 $a \le b$。
求 $\sum\limits_{i=1}^a\sum\limits_{j=1}^b f(\gcd(i,j))$。
转化：
$\sum\limits_{d=1}^a\sum\limits_{i=1}^{\lfloor \frac{a}{d}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{b}{d} \rfloor} [(i,j)=1]f((i,j))$
$= \sum\limits_{d=1}^a f(d)\sum\limits_{i=1}^{\lfloor \frac{a}{d}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{b}{d} \rfloor} \sum\limits_{k|(i,j)}\mu(k) $
$=\sum\limits_{d=1}^a f(d)\sum\limits_{k=1}^{\lfloor \frac{a}{d}\rfloor}\mu(k) \lfloor\frac{a}{dk}\rfloor\lfloor\frac{b}{dk}\rfloor$。
为了方便求解，可以将其转化为 Dirchlet 卷积的形式，令 $T =dk$。
原式转化为：$\sum\limits_{T=1}^a \sum\limits_{d|T}f(d)\mu(\frac{T}{d})\lfloor\frac{a}{T}\rfloor\lfloor\frac{b}{T}\rfloor$。
设 $g(i) = \sum\limits_{d|i}f(d)\mu(\frac{i}{d})$，现在只需要找到一个方法快速求出 $g(1),g(2),\cdots,g(a)$，就可以使用整除分块解决本题。
假设线性筛当前筛到了 $x = a_1^{p_1}\cdot a_2^{p_2}\cdot \cdots \cdot a_kp^k$，$\frac{x}{d} = a_1^{q_1}\cdot a_2^{q_2}\cdot \cdots \cdot a_k^{q_k}$。
此时的背景是正在计算 $f(d)\mu(\frac{T}{d})$。
需要注意的是，由于莫比乌斯函数的性质，值若不为 $0$，那么 $q_i$ 只能为 $0$ 或 $1$。
考虑一件事情，如果 $x$ 的某个质数的幂次不等于 $f(x)$，那么这个质数归类于 $d$ 还是 $f(d)$ 不会导致 $f(d)$ 的变化，但是 $\mu(\frac{T}{d})$ 的值却会因此翻转，导致答案变为 $0$。
下面考虑 $x$ 的每个质因数的幂次相同的情况。
对于 "普通" 的情况，还是按照上一种。
特殊情况，就是 $1 \le \forall i \le k, q_i=p_i-1$，不难注意到这种情况不会被抵消掉。
经过上述分类讨论发现，只有这种特殊情况不会被抵消掉，得出结论：
然后就可以快乐的线性筛了。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-09 11:02:14
这题难点子啊与拆开之后怎么整合到一个可以求解的式子。
参考题解 1
参考题解 2
求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m \ arphi(ij)$。
注意到 $n$ 比较小。
设 $s(n,m) = \sum\limits_{i=1}^m \ arphi(ni)$。
令 $n$ 的质因数分解为 $\prod\limits_{i=1}^kd_i^{p_i}$。
令 $a=\prod\limits_{i=1}^kd_i^{p_i-1},b=\frac{n}{a}$。
$S(n,m) = \sum\limits_{i=1}^m \ arphi(iab)$
$=a\sum\limits_{i=1}^m\ arphi(ib)$
$=a\sum\limits_{i=1}^m\ arphi(i\frac{b}{(i,b)}(i,b))$
$=a\sum\limits_{i=1}^m\ arphi(i\frac{b}{(i,b)})(i,b)$
$=a\sum\limits_{i=1}^m\ arphi(i)\ arphi(\frac{b}{(i,b)})(i,b)$
$=a\sum\limits_{i=1}^m\ arphi(i)\ arphi(\frac{b}{(i,b)})\sum\limits_{d|(i,b)}\ arphi(d)$
$=a\sum\limits_{i=1}^m\ arphi(i)\sum\limits_{d|(i,b)}\ arphi(d)\ arphi(\frac{b}{(i,b)})$
$=a\sum\limits_{i=1}^m\ arphi(i)\sum\limits_{d|(i,b)}\ arphi(\frac{b}{\frac{(i,b)}{d}})$
$=a\sum\limits_{i=1}^m\ arphi(i)\sum\limits_{d|(i,b)}\ arphi(\frac{b}{d})$
$=a\sum\limits_{d |b}\ arphi(\frac{b}{d})\sum\limits_{i=1}^{\lfloor\frac{m}{d}\rfloor}\ arphi(di)$
$=a\sum\limits_{d|b}\ arphi(\frac{b}{d})S(d,\lfloor \frac{m}{d}\rfloor)$。
我不会证明复杂度，递归到 $n=1$ 就杜教筛，$m=0$ 就返回 $0$。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-09 11:37:09
我不知道发明者是怎么想到这些的。
假设存在一个积性函数 $f$，给定一个 $n$，要求 $\sum\limits_{i=1}^nf(i)$。
设 $S(n) = \sum\limits_{i=1}^nf(i)$。
考虑另一个积性函数 $g$，它们的 Dirchlet 卷积的前缀和：
$\sum\limits_{i=1}^n (f*g)(i)$
$= \sum\limits_{i=1}^n \sum\limits_{d|i}f(d)g(\frac{i}{d})$
$=\sum\limits_{d=1}^ng(d)\sum\limits_{i=1}^{\lfloor \frac{n}{d}\rfloor}f(\frac{di}{d})$
$=\sum\limits_{d=1}^ng(d)\sum\limits_{i=1}^{\lfloor \frac{n}{d}\rfloor}f(i)$
$=\sum\limits_{d=1}^n f(d)S(\lfloor \frac{n}{d}\rfloor)$。
由此可得，$f(1)S(n) =\sum\limits_{i=1}^n(f*g)(i)- \sum\limits_{d=2}^nf(d)S(\lfloor\frac{n}{d}\rfloor)$。
现在的主要任务在于找到一个函数 $g$，使得 $f*g$ 的前缀和可以快速求出。另外，$\sum\limits_{d=2}^nf(d)S(\lfloor\frac{n}{d}\rfloor)$ 可以使用整除分块计算。
假设 $f*g$ 的前缀和可以 $O(1)$ 计算，那么最后整个算法的复杂度是 $O(n^{\frac{2}{3}})$ 的，前提是使用线性筛预处理出 $f$ 的前 $n^{\frac{2}{3}}$ 的值的前缀和。
Master 定理可以证明复杂度，不写了。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-12 10:04:30
耻辱啊，E 题贪心假掉吃 3 发，F 题没处理跳过区间的 cases，最后 wa 3 个测试点，G 题简单题结果没看，掉大分了。
感觉每道题都弱于 CF 1900，但赛时确实因为各种原因没过 F,G。
我写了 3 种直接贪心的方式，都是错的。
考虑二分答案，设答案为 $k$。
显然选择前 $k$ 个和后 $k$ 个。
较为明显的，$1 \le \forall i \le k$，$i$ 个匹配 $n-(k-i)$ 个。
可以用类似于归纳法证明，第 $1$ 个元素需要匹配第 $n-k+1$ 个元素，如果不能匹配，则第 $[2,k]$ 个元素也不能与其匹配，而即使可以，第 $[2,k]$ 个元素匹配 $n-k+1$ 显然也不优。
随后问题就简化到了 $k-1$ 个元素的，得到证明。
只需要判断能否到达。
首先预处理出每个好区间 $[l,r]$，由于题目保证坏区间两两不相交，这个还是很容易的。
事实上，对于每个好区间 $[l,r]$ ，我们只关心 $[l,l+b]$ 和 $[r-b,r]$ 这个范围的位置能否到达。
如果 $a\neq b$，那么想要行走的距离 $len$ 足够大，就一定能走出这个距离。
那这个阈值如何计算呢？这个阈值小于等于使得 $xa+yb = len$ 无解的最大的 $len$，这刚好在 CCF 原题里面出现过，答案是 $ab-a-b$，代入 $a=19,b=20$ 得到这个无解的 $len$ 最大是 $341$，所以只需要处理 $len$ 在 $[0,341]$ 之间能否走出这个距离就可以。
对于 $a=b$ 的情况，只需要满足想要走的距离 $len$ 是 $a$ 的倍数就可以。
现在，设 $dp_{i,j}$ 代表第 $i$ 个好区间，左端点开始算第 $j$ 个位置能否被到达。设第 $i$ 个好区间是 $[l_i,r_i]$。
转移的话，先计算出 $[r_i-b,r_i]$ 区间哪些点可以到达。
随后，从 $[r_i-b,r_i]$ 区间的可以到达的点出发，枚举单次走的距离，更新后面区间的 $dp$ 值。
需要注意的是，这个过程可能会跳过一些区间。
比如，$3$ 个好区间 $[1,5],[7,10],[12,15]$，$a=b=8$，此时从 $5$ 出发将到达 $13$，跳过第一个区间直接到第 $3$ 个区间。
所以，不能简单的仅仅更新 $i+1$ 区间。
仍然沿用 E 题的 check 方法，仍然二分答案 $k$。
注意到对于第 $i$ 个位置，其作为较大值时，能匹配的位置是数组的一个前缀。
而合法的条件是对于 $(r-k+1) \le \forall i \le r$，第 $i$ 个位置向左最远的不可匹配的距离小于 $r-l+1-k$。
双指针预处理出每个位置作为较大值时，左边最远的不可匹配的距离，每次询问 ST 表就可以了。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-17 21:27:23
模拟赛数据范围看成了 $10^5$，苦战 2h 得以战胜，好像爆标了官方 std？
考虑要维护哪些信息。
首先按照套路，升序枚举每个可能的最大的 $h$，设当前枚举的最大 $h$ 为 $lim$。
现在，需要知道的是，有哪些展板必须翻转，使得不超过最大的 $h$。
如果存在一个展板无论如何，都不能靠翻转使得 $h \le lim$，那么当前无解，判定条件是 $\min(h,w)\gt lim$。
所以，维护一个 set 存储所有尚不合法的展板，第一关键字是 $\min(h_i,w_i)$，每次枚举 $lim$ 都更新这个 set。
当不合法的展板全部清空之后，考虑如何翻转这些展板。
对于一个满足 $w \gt h$ 的展板，如果能将 $w,h$ 交换之后满足 $h \le lim$，那么交换之后，$w$ 将减少 $w-h$，使得当前情况的答案减少 $(w-h)lim$。
但是，很多个展板都可能交换 $h,w$，得考虑哪些是真正需要交换的。
注意到，对于满足 $w \le lim \lt h$ 的展板，属于必须翻转。
对于剩下的名额，则优先给 $w-h$ 更大的展板。
考虑维护一个 set 存储所有可能交换 $h,w$ 的展板（不含强制交换），第一关键字是 $w-h$；再用一个 set 维护所有强制交换的展板，第一关键字是 $h$；再用一个 set 维护所有不允许交换的展板，第一关键字是 $w$。
考虑如何更新这些 set。
每次更新 $lim$ 时，由于对 $h$ 的限制变宽，依次执行下列操作：
注意到，总共出现过 5 个 set，单个元素不可能被加入同一个 set 两次（除了允许交换的集合内部的两个 set，但是新加入一个元素最多造成 $1$ 的影响），所以复杂度 $O(n \log n)$。
#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
a=min(a,b);
}
template<class T>
T gcd(T a,T b){
return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
return a\/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
template<class T>
void wrint(T x){
if(x<0){
x=-x;
pc('-');
}
if(x>=10){
wrint(x\/10);
}
pc(x%10^48);
}
template<class T>
void wrintln(T x){
wrint(x);
pln
}
template<class T>
void read(T& x){
x=0;
int f=1;
char ch=gc;
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=gc;
}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);
ch=gc;
}
x*=f;
}
const int maxn=1005;
int n;
pll nd[maxn];
set<pll> notok;
set<pll> waitswp;\/\/ 交换之后更优，但是不可以交换，关键字 w
multiset<ll> canswp;\/\/ 可以交换，关键字 h-w
multiset<ll> canswp2;
set<pll> noswp;\/\/ 可能不需要交换，但强制交换，关键字 h
int k=n\/2;
ll w=0;
void solve(int id_of_test){
read(n);
vi ableh;
FOR(i,1,n){
read(nd[i].fi);
read(nd[i].se);
ableh.eb(nd[i].fi);
ableh.eb(nd[i].se);
notok.insert(mkpr(min(nd[i].fi,nd[i].se),i));
}
sort(ableh.begin(),ableh.end());
ll ans=1e18;
for(int h:ableh){
while(!noswp.empty()){
if(noswp.begin()->fi<=h){
int id=noswp.begin()->se;
if(nd[id].se>=nd[id].fi){
w-=nd[id].se;
w+=nd[id].fi;
}else{
canswp.insert(nd[id].se-nd[id].fi);
}
noswp.erase(noswp.begin());
}else break;
}
\/\/ puts("???1");
while(!waitswp.empty()){
if(waitswp.begin()->fi<=h){
int id=waitswp.begin()->se;
canswp.insert(nd[id].se-nd[id].fi);
w+=(nd[id].se-nd[id].fi);
waitswp.erase(waitswp.begin());
}else break;
}
\/\/ puts("???2");
while(!notok.empty()){
\/\/ puts("wtf");
if(notok.begin()->fi<=h){
int id=notok.begin()->se;
if(nd[id].se<=h){
w+=nd[id].fi;
if(nd[id].fi>nd[id].se){
if(nd[id].fi>h){
waitswp.insert(mkpr(nd[id].fi,id));
}else{
w+=(nd[id].se-nd[id].fi);
canswp.insert(nd[id].se-nd[id].fi);
}
}
}else{
if(nd[id].fi<=h){
w+=nd[id].se;
noswp.insert(mkpr(nd[id].se,id));
}else{
break;
}
}
notok.erase(notok.begin());
}else break;
}
if(!notok.empty())continue;
while(!canswp.empty()&&canswp.size()+noswp.size()>n\/2){
w-=*prev(canswp.end());
canswp2.insert(*prev(canswp.end()));
canswp.erase(prev(canswp.end()));
}
while(!canswp2.empty()&&canswp.size()+noswp.size()<n\/2){
w+=*canswp2.begin();
canswp.insert(*canswp2.begin());
canswp2.erase(canswp2.begin());
}
\/\/ printf("w %lld\n",w);
if(canswp.size()+noswp.size()>n\/2)continue;
ckmn(ans,w*h);
}
printf("%lld\n",ans);
}
int main()
{
int T;
T=1;
FOR(_,1,T){
solve(_);
}
return 0;
}
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-02-02 18:18:05
第一道自己想出做法的 CF Div.1 F，记录一下它的两种维护方式。
$n$ 个点，每个点的度数最多是 $4$。
求有多少个点对 $(l,r)$ 满足 $1 \le l \le r \le n$，使得 $[l,r]$ 中的点构成的导出子图是一棵树。
考虑编号升序枚举右端点，想一想哪些左端点是符合要求的。
虽然 LCT 常数巨大，但是在这道题可以吊打普通的整体二分。
其中 LCT 维护的时间复杂度是 $O(nm \log nm)$，整体二分多一个并查集的复杂度。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-04 01:27:55
考虑将一个完整的区间拆成两段的贡献是什么。
假设 $[l,r]$ 拆为 $[l,mid],[mid+1,r]$。
那么 $[mid,n]$ 所有鱼的价值加 $1$。
注意到，此时本质上是从 $mid+1$ 开始，每个点的编号加了 $1$。
也就是说，问题转化为：$[2,n]$ 共 $n-1$ 个点，对于每个点，都可以选择是否将从这个点开始的所有点的价值加 $1$。
假设一条鱼如果是 Bob 获得，那么是 $1$，反之 $-1$，设 $p_i$ 代表前 $i$ 个鱼的前缀和。
假设第 $i$ 个点选择将其开始的所有点价值加 $1$，那么 Bob 领先 Alice 的分数将会增加 $p_n-p_{i-1}$。
接下来排序贪心就可以。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-04 01:44:57
有 $n$ 个用户和 $10^9$ 首歌曲，第 $i$ 个用户喜欢的歌曲是编号在 $[l_i,r_i]$ 的一段连续子区间。
用户 $j$ 称为用户 $i$ 的预测者当且仅当 $[l_j,r_j]$ 包含 $[l_i,r_i]$。
对于每个用户 $i$，计算其预测者喜欢的歌曲的并集大小（原题求出结果后需要减去 $r_i-l_i+1$）。
注意到完全包含的对数可以达到 $O(n^2)$ 级别，逐个计算是不可能的。
考虑对于每个人，如何计算其答案。
考虑简化问题，分别考虑对于一个人，其预测者喜欢的音乐的并集区间的左端点和右端点。
假设当前处理用户 $i$ 的答案。
容易注意到，左端点是在 $i$ 的预测者的左端点里面取最大值，右端点是在 $i$ 的预测者的右端点里面取最小值。
能否二分左右端点呢？
由于左右端点的做法是等价的，此处仅讨论左端点的情况。
此时，二分的目的是求出最大的 $l$ 使得 $l$ 是某个预测者的左端点。
注意到，一个左端点是某个预测者的左端点，当且仅当这个左端点能直接到达的最大右端点大于等于 $r_i$，当然，这对左端点右端点的组合不能是 $(l_i,r_i)$ 本身。
那么，二分 check 的时候只需要看从 mid 到 $l_i$ 是否存在一个预测者的左端点就可以了，可以 ST 表维护做到 $O(1)$ 判定。
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-04 02:07:41
注意，本文章中如果提到某个端点没有固定，那么在固定前默认延伸到本区间的末尾
首先需要维护题目要求的答案 $ans$，而有以下几种情况：
首先考虑 $ans2$，此时需要再维护两个值 $premx,sufmx$，分别代表左端点固定，右端点固定（另一个端点一直到区间结束）的最大值。
随后考虑情况 3，此时的两种形式：
....l1....mid....r1...l2....r2.......l1....r1....l2....mid...r2...考虑用 $pre$ 代表左答案区间固定，右答案区间的右端点尚未存在的最大价值，$suf$ 代表右答案区间固定，左答案区间的左端点尚未存在的最大价值。
$pre,suf$ 的计算，经过分析后可知还需要维护一个值，代表存在两个答案区间，左答案区间的右端点固定，右答案区间的左端点固定的最大价值。
本题我调了很久也没调出来，看了题解发现思路和题解完全一致。
我总算是查出了错，原因在于我在 SGT 的信息里使用了前缀和，但是我忘了 $a$ 数组的修改会改变一整个后缀的前缀和，导致 SGT 的信息出错。
以往我写线段树，通常只是将区间合并写死为树上左右子区间合并，而忽略了特殊情况下，查询的时候没法直接使用简单的加法乘法等操作将查询过程中找到的不同查询区间的子区间的答案合并，此时就需要使用 pushup 操作将它们逐个合并为整个查询的区间。
以后写线段树的时候需要注意这一点，防止类似情况再次被坑。
鲁ICP备2025150228号