题解 P5610 【[Ynoi2013]大学】
rui_er
2020-09-17 18:39:28
本题的难点主要在于如何快速找到需要修改的数。
看到这题，容易想到平衡树，用很多平衡树维护每个位置的质因数即可。
> 很遗憾，被我卡掉了——lxl
听大佬说这东西过不去，就想其他常数小的方法。
---
我们可以使用并查集来维护对于每个质数我们需要修改的数的位置等信息，快速求出需要修改的最左侧，然后通过一种类似于指针的结构依次遍历，即可完成修改。
我们还需要一个数据结构来维护整串序列，并且因为有修改，需要支持单点改和区间查，可以使用常数小还好写的树状数组。
至此，我们便得出了一种解法。在此基础上再卡亿点点常数即可。
---
总结一下：我们维护并查集和树状数组，并查集用来快速求出所有需要修改的点，树状数组进行修改。
因为我们在程序最开始需要对所有数进行分解质因数，因此我们的复杂度为 $O(n\sqrt{x}+n\log{n}\times\alpha(n))$。
---
主要代码（已删除调试部分）：
```cpp
namespace BIT {
ll s[N];
void modify(int u, int x) {for(;u<=n;u+=u&(-u)) s[u] += x;}
ll query(ll u) {ll res = 0; for(;u;u-=u&(-u)) res += s[u]; return res;}
}
namespace DSU {
vector<int> fa[N], fa2[N];
int find(int u, int v) {return (v == ll(fa2[u].size()) || v == fa2[u][v]) ? v : fa2[u][v] = find(u, fa2[u][v]);}
}
using DSU::fa;
using DSU::fa2;
void init() {
n = read(); m = read();
for(int i=1;i<=n;i++) {
a[i] = read();
int _ = sqrt(a[i]);
for(int j=1;j<=_;j++) {
if(!(a[i] % j)) {
fa[j].push_back(i);
fa2[j].push_back(fa2[j].size());
if(j * j < a[i]) {
fa[a[i]/j].push_back(i);
fa2[a[i]/j].push_back(fa2[a[i]/j].size());
}
}
}
BIT::modify(i, a[i]);
}
}
void modify(int l, int r, int x) {
int pos = lower_bound(fa[x].begin(), fa[x].end(), l) - fa[x].begin();
for(int i=DSU::find(x,pos);i<ll(fa[x].size())&&fa[x][i]<=r;i=DSU::find(x,i+1)) {
if(!(a[fa[x][i]] % x)) {
int _ = fa[x][i];
BIT::modify(_, a[_]/x-a[_]);
a[_] /= x;
}
if(a[fa[x][i]] % x) fa2[x][i] = i + 1;
}
}
ll query(int l, int r) {return BIT::query(r) - BIT::query(l-1);}
```