题解 P3987 【我永远喜欢珂朵莉~】
JRzyh
·
·
题解
BIT做法
一个trick：
每次 a_i\div k，最多需要 \log~a 次 a 就会变成 1。
可以试着自行理解，不理解的看这：
所以说修改的复杂度最多就 $O(n\log a_i)$ 。
所以说只要把查询复杂度控制在单次 $O(\log n)$ 就行。
区间求和，单次 $O(\log n)$ ，想到了什么？
**树状数组！**
可是……修改到底怎么改呢？
前文说过，修改的复杂度最多就 $O(n\log a_i)$ ，所以我们可以直接找到要修改的数，**单点修改**（而不是区间）
最大的问题，如何找到要修改的数？
开 $500000$ 个 vector，第 $i$ 个 vector 表示包含因数 $i$ 的元素的下标，可以使其有序，使用二分法（STL里的lower_bound和upper_bound）找到起点和终点，暴力遍历其间的元素，暴力除，暴力在BIT中修改即可。
但是要注意：**删除已经不包含因数 $i$ 的元素**
怕什么，直接暴力找用erase函数。
思路没了。
---
**别着急去写代码** ~~（您还没点赞呢）~~
erase正向删数会出现问题！
删除一个数后后面的数下标都会 $-1$，所以删第二个的时候那里已经不是要删的数了。
处理方法简单，反向删数，不会影响到之后删的数。
ACcode:
```cpp
#include<bits/stdc++.h>
using namespace std;
//
long long read()
{
long long in=0;short f=1;
char c=getchar();
while (c>'9'||c<'0')
{if(c=='-') f=-1;c=getchar();break;}
while (c>='0'&&c<='9')
{in=in*10+c-'0';c=getchar();}
return in*f;
}
void write(long long x)
{
if (x==0){putchar('0');return;}
if(x<0) {putchar('-');x=-x;}
if(x<10) {putchar(x+'0');return;}
short num=0; char c[30];
while(x) c[++num]=(x%10)+48,x/=10;
while(num) putchar(c[num--]);
}
//快读快写
#define lowbit(x) (x&(-x))
long long tree[100008];
int n;
long long get_sum(int wh)
{
long long ans=0;
for(;wh;wh-=lowbit(wh)) ans+=tree[wh];
return ans;
}
void add(int wh,long long v)
{
for(;wh<=n;wh+=lowbit(wh)) tree[wh]+=v;
}
//树状数组
#define vit vector<int>::iterator
int a[100008],m;
vector<int>ys[500008];
vector<vit>t;
int main()
{
n=read();m=read();
for(register int i=1;i<=n;i++)
{
a[i]=read();
for(register int j=1;j*j<=a[i];j++)
{
if(a[i]%j==0)
{
ys[j].push_back(i);
if(a[i]!=j*j) ys[a[i]/j].push_back(i);
}
}
add(i,a[i]);
}
while(m--)
{
short opt=read();
switch(opt)
{
case 1:
{
int l=read(),r=read(),x=read();
t.clear();
if(x==1||ys[x].empty()) continue;
vit l2=lower_bound(ys[x].begin(),ys[x].end(),l);
vit r2=upper_bound(ys[x].begin(),ys[x].end(),r);
if(l2==ys[x].end()) continue;
for(vit it=l2;it!=r2;it++)
{
if(a[*it]%x!=0) continue;
add(*it,-(a[*it]-a[*it]/x));
a[*it]/=x;
if(a[*it]%x!=0) t.push_back(it);
}
if(!t.empty())
{
for(int i=t.size()-1;i>=0;i--) ys[x].erase(t[i]);
}
break;
}
case 2:
{
int l=read(),r=read();
write(get_sum(r)-get_sum(l-1));
putchar('\n');
break;
}
}
}
return 0;
}
```
快去AC加强版：[P5610](https://www.luogu.com.cn/problem/P5610)
[My solution](https://www.luogu.com.cn/blog/242524/solution-p5610)
~~点赞，点赞，一定要点赞~~