P3987 我永远喜欢珂朵莉~ 题解
_HMZ_
·
·
题解
在太阳西斜的这个世界里，置身天上之森。等这场战争结束之后，不归之人与望眼欲穿的众人， 人人本着正义之名，长存不灭的过去、逐渐消逝的未来。我回来了，纵使日薄西山，即便看不到未来，此时此刻的光辉，盼君勿忘。——世界上最幸福的女孩 珂朵莉
注：感谢wxw大佬提供的hack数据，这题数据实在很奇葩。
解题思路：
这道题需要维护区间除法，普通的线段树肯定是做不到的，可是像wxw大佬那样的卡常又不会。
但！是！这可是一道信仰题，怎么可以轻易放弃！
于是我们发挥瞎搞精神，线段树能做到的得做，不能做到的也得给我做（线段树：我招谁惹谁了我）。
既然区间除法不行，那单点除法肯定是行的，现在问题就转化为了在一个区间内如何快速找到 x 的倍数。
暴力肯定不可行，那么我们就可以预处理一下，开 n 个动态数组 e。
每次遇到除法，就在 $e_x$ 里头找第一个大于等于 $l$ 和最后一个小于等于 $r$ 的数字，在这个区间内暴力单点修改。
但是有个问题，修改完之后有可能就不是 $x$ 的倍数了，所以这里要引进一个玄学优化。
每次记录操作 $1$ 除以 $x$ 的次数，如果次数很多，每操作一次就将不是 $x$ 的倍数的删除掉，这样以后暴力修改能快点。
事实上 $500000$ 大概除个 $19$ 次 $2$ 就差不多到 $1$ 了，时间复杂度上完全能接受。
## AC代码：
```cpp
#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
#define int long long
namespace in { //快读模板
#ifdef faster
char buf[1 << 21], * p1 = buf, * p2 = buf;
inline int getc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++; }
#else
inline int getc() { return getchar(); }
#endif
template <typename T>inline void read(T& t) {
t = 0; int f = 0; char ch = getc(); while (!isdigit(ch)) { if (ch == '-')f = 1; ch = getc(); }
while (isdigit(ch)) { t = t * 10 + ch - 48; ch = getc(); }if (f)t = -t;
}
template <typename T, typename... Args> inline void read(T& t, Args&... args) { read(t); read(args...); }
}
vector<int> e[500005];
int n, m, a[500005], t[500005], tree[2000005];
struct node
{
int op, u, v, w;
}s[500005];
inline int find1(int now, int x)//二分
{
int l = 0, r = e[x].size() - 1, ans = -1, mid;
while (l <= r)
{
mid = (l + r) >> 1;
if (e[x][mid] >= now)
{
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
return ans;
}
inline int find2(int now, int x)
{
int l = 0, r = e[x].size() - 1, ans = -1, mid;
while (l <= r)
{
mid = (l + r) >> 1;
if (e[x][mid] <= now)
{
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
return ans;
}
inline void cf(int now, int x)//这里是预处理，将符合条件的数放进动态数组里
{
for (register int i = 1; i * i <= now; ++i)
{
if (now % i == 0)
{
e[i].push_back(x);
if (i * i != now)
e[now / i].push_back(x);
}
}
}
inline void build(int now, int l, int r)//线段树基本操作
{
if (l == r)
{
tree[now] = a[l];
return;
}
int mid = (l + r) / 2;
build(now * 2, l, mid);
build(now * 2 + 1, mid + 1, r);
tree[now] = tree[now * 2] + tree[now * 2 + 1];
}
inline void update(int now, int l, int r, int k, int x)
{
if (l > k || r < k)
return;
if (l == k && r == k)
{
tree[now] /= x;
return;
}
int mid = (l + r) / 2;
update(now * 2, l, mid, k, x);
update(now * 2 + 1, mid + 1, r, k, x);
tree[now] = tree[now * 2] + tree[now * 2 + 1];
}
inline int query(int now, int l, int r, int x, int y)
{
if (l > y || r < x)
return 0;
if (x <= l && r <= y)
return tree[now];
int mid = (l + r) / 2, res;
res = query(now * 2, l, mid, x, y) + query(now * 2 + 1, mid + 1, r, x, y);
return res;
}
inline void divide(int l, int r, int x)
{
int head = find1(l, x), tail = find2(r, x);
if (head == -1)
return;
for (register int i = head; i <= tail; ++i)
{
int now = e[x][i];
if (a[now] % x == 0)
a[now] /= x, update(1, 1, n, now, x);
else if (t[x] >= 10000)//这里就是玄学优化
e[x].erase(e[x].begin() + i), --i,--tail;
}
}
signed main()
{
in::read(n, m);
for (register int i = 1; i <= n; ++i)
{
in::read(a[i]);
cf(a[i], i);
}
build(1, 1, n);
for (register int i = 1; i <= m; ++i)
{
in::read(s[i].op);
if (s[i].op == 1)
{
in::read(s[i].u, s[i].v, s[i].w);
++t[s[i].w];
}
else
in::read(s[i].u, s[i].v);
}
for (register int i = 1; i <= m; ++i)
{
if (s[i].op == 1)
{
if (s[i].w == 1)
continue;
divide(s[i].u, s[i].v, s[i].w);
--t[s[i].w];
}
else
printf("%lld\n", query(1, 1, n, s[i].u, s[i].v));
}
return 0;
}
```