OI记录（持续更新
P2568 GCD
题意：
给定正整数 \(n\)，求 \(1\le x,y\le n\) 且 \(\gcd(x,y)\) 为素数的数对 \((x,y)\) 有多少对(\(n\leq10^7\))
题解：
注意，可以不用莫比乌斯反演，单纯的欧拉函数便可以解决，首先列出式子：
\[\sum_{p\in prime}\sum_{i=1}^{n}\sum_{j=1}^{n}(gcd(i,j)=p) \]接着转化式子,gcd里的\(i,j\)同除\(p\),再换元一下：
\[\sum_{p\in prime}\sum_{i=1}^{\lfloor \frac {n}{p} \rfloor}\sum_{j=1}^{\lfloor \frac {n}{p} \rfloor}(gcd(i,j)=1) \]然后我们可以观察到\(gcd(i,j)=1\)代表的是互质，如何转化到可以计算呢，我们假设\(j\)枚举到\(i\)，这样就可以用欧拉函数，然后讨论一下改成这个就只是有序变为无序，然后会有2倍的差距，然后考虑\(i=j\)的时候会被统计两次但是因为\(gcd(i,j)=1\) 只有\(i=j=1\)时有贡献，在\(\sum_{p\in prime}\)这层循环下减个1，于是为：
\[\sum_{p\in prime}(\sum_{i=1}^{\lfloor \frac {n}{p} \rfloor}(2\sum_{j=1}^{i}(gcd(i,j)=1))-1) \]然后发现这个\(\sum_{j=1}^{i}(gcd(i,j)=1)\)就是欧拉函数\(\varphi(x)\)：
\[\sum_{p\in prime}(2\sum_{i=1}^{\lfloor \frac {n}{p} \rfloor}\varphi(i)-1) \]具体在程序中刚开始用欧拉筛预处理出来要用到的欧拉函数值和所有的质数，接着预处理出来一个前缀和。
最后枚举所有的质数，求\(2sumphi[n/p]-1\)。
因为这题始数学题，AC code较为简单：
#include<bits/stdc++.h>
#define int long long
#define N 10000009
using namespace std;
int n;
int phi[N],sumphi[N];
bool pri[N];
int prime[N],cnt;
int answ=0;
void euler()
{
phi[1]=1;
for(int i=2;i<=10000002;i++)
{
if(!pri[i]) prime[++cnt]=i,phi[i]=i-1;
for(int j=1;j<=cnt;j++)
{
if(i*prime[j]>10000002) break;
if(i%prime[j]==0){
pri[i*prime[j]]=1;
phi[i*prime[j]]=phi[i]*prime[j];break;
}
pri[i*prime[j]]=1;
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
for(int i=1;i<=10000002;i++)
sumphi[i]=sumphi[i-1]+phi[i];
}
signed main()
{
scanf("%lld",&n);
euler();
//cout<<cnt;
for(int i=1;i<=cnt;i++)
{
if(prime[i]>n) break;
//cout<<sumphi[n/prime[i]]<<endl;
answ+=(2*sumphi[n/prime[i]]-1);
}
printf("%lld",answ);
}
P1640 [SCOI2010] 连续攻击游戏
题意:
给定\(n\)个物品，每个物品有两个属性值，每种物品只能选取其中一个属性，并且每个物品只能用一次。现在要从属性\(1\)开始，选取物品，问最多能选取多少个。
题解：
二分图忘了，这道题是二分图板子，是用来锻炼二分图的，二分图匹配的匈牙利算法有一个很棒的性质：前面已经被匹配过的点不会失配。然后我们进行套路的建图，每个物品连两条边到他的属性值上，然后以属性值作为右部点，依次跑二分图匹配，直到失配便终止循环。
值得一提的是，这道题有些不适合网络流解法，二分答案跑网络流会超时，但是可以玄学先增广序号在前的点，这样也能得到正确答案。
因为用的是匈牙利算法，所以代码简单：
#include<bits/stdc++.h>
#define N 1145141
using namespace std;
int match[N],n;
vector<int>tu[N];
bool vis[N];
stack<int>V;
bool dfs(int now)
{
//cout<<now<<endl;
for(auto too:tu[now])
{
if(!vis[too])
{
vis[too]=1;
V.push(too);
if(!match[too]||dfs(match[too]))
{
match[too]=now;
return true;
}
}
}
return false;
}
int read()
{
int ans=0;
char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9')
{
ans=10*ans+c-'0';
c=getchar();
}return ans;
/*int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;*/
}
int main(){
n=read();
for(int i=1;i<=n;i++)
{
int x=read(),y=read();
tu[10000+i].push_back(x);
tu[10000+i].push_back(y);
tu[y].push_back(10000+i);
tu[x].push_back(10000+i);
}
for(int i=1;i<=10000;i++)
{
while(!V.empty()){
vis[V.top()]=0;
V.pop();
}
if(!dfs(i)){
printf("%d",i-1);
return 0;
}
}
printf("10000");
}
容器 set 和 multiset
set 和 multiset 代表有序集合和可重有序集合，包含在 set 库中。
关于迭代器：
迭代器就是指向一个元素的指针，例如用 int 类型定义的 set 集合里指向开头元素的迭代器一般表示为：
set<int>::iterator it = s.begin();
it + 1 指向下一个元素，it - 1 指向上一个元素（如果这个集合中存在上一个或下一个元素的话）。
s.begin()是指向s开头元素的迭代器。s.end()是指向s末尾元素的下一个内存位置的迭代器，所以如果要查末尾元素，一般是引用s.end() - 1。
注意这里 +1 和 -1 的时间复杂度都是 O(log n)。
有何作用？除了遍历集合元素外，set 和 multiset 都是有序集合（默认从小到大，可以用定义优先队列的方法定义这个东西），所以这就相当于是一个平衡树了，是不是很棒？平衡树可以干很多事呢。
如何把迭代器换为可以直接输出的该元素的值？加个星号，即 *it。
可以用减法查看当前是第几个。
关于操作：
定义如 int 类型用 set<int> s 或 multiset<int> s。
具有以下基础操作：
s.clear()s.empty()s.size()s.insert(x)代表插入元素x，如果是重复的元素，set不会插入，multiset会插入。s.find(x)表示查找集合里等于该元素的迭代器（返回第一个），不存在返回s.end()。- 具有二分函数
s.lower_bound(x)和s.upper_bound(x)，代表查询大于等于x和大于x的元素里最小的一个，返回迭代器。 s.erase(x)代表删除所有等于x的元素或者删除x迭代器所指的元素。特别注意的是，如果只删去一个等于x的元素，可以执行：
if((it=s.find(x))!=s.end()) s.erase(it);//代表先找指向x的迭代器，如果x存在，就删去
s.count()返回集合中等于x的元素个数。
上面函数的复杂度除了 s.count() 和 s.erase() 是 O(k + log n)，其余都是 O(log n)。
当然，平衡树别写set,时间和正确性都容易炸（时间必炸）。
组合数预处理
先预处理\(C_{i}^{0}=1\)然后根据\(C_{i}^{j}=C_{i-1}^{j-1}+C_{i}^{j-1}\)递推出所有组合数：
for(int i=0;i<=3000;i++) c[i][0]=0;
for(int i=1;i<=3000;i++)
for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j-1]+c[i][j-1])%MOD;
10.23正睿模拟赛T3记录
题意：
给定一张 \(n\)个点，\(m\)条边的有向无环图。
进行 \(q\)次询问，每次询问给定 \(s,t,l,r\)。问若只保留编号在$ [l,r]$ 之间的边，\(s\) 能否到达 \(t\)。
题解：
妙妙题。
先给给询问搞个编号，离线下来做。
首先我们要用\(bitset\)进行辅助记录，首先记录一个\(g[m]\)，单个\(g[i]\)记录的是编号为\(i\)的边在所有询问里的存在情况（\(bitset\)存的）。
具体的计算我们搞一个扫描线，对于每一个询问，在边编号的\(tag\)上记东西，在\(l\)位置记上这个询问编号，\(r+1\)位置也记录这个询问编号，然后就定义一个\(bitset\) \(Q\),扫一遍这个\(tag\),每回先给\(Q\)在所有目前位置上所有询问编号在对应的位置取反，然后把这个\(Q\)赋值给对应的\(g[i]\)。
然后就是\(f[n]\)了，对于每一个结点，单个\(f[i]\)记录的是每一个询问的\(s_i\)在只能有当前询问存在的边时到这个点的连通性（同样用\(bitset\)存）。
首先初始化给每个询问的\(s_i\)的\(f[s_i]\)对应的关于本身\(s_i\)的存在性命名为1（因为自己肯定和自己连通嘛）。
然后考虑是DAG，我们可以转移，有边\((u,v)\)，编号\(i\),可以使得\(f[u]\)贡献给\(f[v]\)一个\(f[u] \and f[v]\)（贡献的形式是或），在拓扑排序的过程中转移，因为在所有通向自己的边处理完后，这个点也处理完了。
但是这样就是询问比较多，空间容易炸，但是因为询问和询问间不打扰，所有我们可以\(B\)个询问\(B\)个询问的处理，这样每个\(bitset\)的长度也就只有\(B\),空间也就不会炸，就处理完了。
最后就对于每个询问输出答案即可。
总结:
- 用\(bitset\)优化时间和运算
- 考虑在拓扑排序上进行\(dp\)转移
- 用扫描线思想处理问题
- 空间炸了如果里面各部分互不相干可以分块计算
- 多个数组联合计算
\(over\)
拉格朗日插值
还没记。
小纪录
关于树上面统计答案时，到了以\(u\)为根的子树上，假如这个统计答案的方式需要是从\(u\)出发的两个不同路径的贡献和的最大值，我们不仅可以把最大和次大的贡献给和一块，还可以不断更新单个从u出发的最大贡献过程中更新这个俩路径合并在一起的最大值，不如现在单个路径最大贡献计算到了\(v\)之前的（不包括\(v\))，我们计算经过\(v\)的单个路径和\(u\)目前单个路径最大贡献的和贡献即可，然后继续更新单个路径最大贡献。
线段树分治记录
更明白的应该说是在线段树上离线查询，适用于那种不支持删除但是支持撤销的东西可以用线段树来辅助，具体来说比如一个东西，你要加进去一个东西，过一段时间再删除这个东西，也就是说不是撤销，不妨为这个时间序列开一个线段树，每回区间操作都记录这个东西存在的区间，这样在线段树上就可以保证这个东西创建和删除可以在一块儿进行。
然后有些题目不会给你明示，就需要各种观察和转化，比如求对于每个元素我们就删除它求剩下的元素的答案，就可以把这些元素当成时间序列排一块，对于不删这个元素的两个（或一个）区间进行标记操作，就可以转化为多次撤销和增加然后求答案。
当然一些题目中那些不要局限在题目中的对哪个东西询问来盲目地进行线段树分治，可能不是对这玩意进行线段树分治，要勤进行转化。
标签：prime,题目,迭代,记录,int,sum,元素,更新,询问 From： https://www.cnblogs.com/huanghezhe/p/18512742