题解 P3987 【我永远喜欢珂朵莉~】
题目传送门：
https://www.luogu.org/problemnew/show/P3987
一道神仙毒瘤珂学卡常题。。。交了 $17$发终于 $A$了
（但是死活找不到哪里被我改对了）
写完之后为了纪念一下，就发了这篇题解
（感觉我的思路很多都和楼下一样QAQ）
先来扯一点没用的
其实本来学长打算下午给我们考一套模拟赛题目的。。。
题目一发下来就发现 $T1$是这个题，于是机房同学们集体鸽掉了学长的模拟赛（雾）
但是作为珂学家的我没有鸽！还是依然写掉了这个题（结果写了一下午，也是醉了）
很早以前就想写掉这个题，但是一看平衡树的标签就吓得不轻。。。
但是现在还不会平衡树的我终于用非平衡树做法写完了！
咳咳。。。不说没用的，直接开讲！
前面的 $5$个点(# $1$~# $5$)都是给的暴力分，乱搞一下就好了，这里不讲
直接来讲满分做法好了（这里用的是 $vector$做法）
操作 $1$每次都要找出操作区间中 $x$的倍数并除掉 $x$
emmm。。。发现如果再用暴力的做法来朴素的查找，效率十分低下
不妨换个思路
想必有人肯定已经做过这道题了吧：P4168 [Violet]蒲公英
（没有做过的同学可以先往下看，以后再做）
做这题之前，我先做掉了这题，因此想到了下面的xjb写算法
蒲公英这题的第二种做法就和本题有着异曲同工之妙
什么意思呢？
在《蒲公英》那道题中，第二种做法的思想是将元素的所有出现位置都按升序存在一个数组中，之后回答每次询问 $[l,r]$只需要在每个元素对应的数组中二分出那些恰好在 $l$和 $r$内的元素，从而得到该元素 $A[i]$在区间 $[l,r]$内的出现次数，即 $num=upper$ $bound(A[i],r)-lower$ $bound(A[i],l)$
那么到了这道题上，我们也可以这样来做
不妨对于每一个元素 $A[i]$，我们若干个数组，这若干个数组的键值都是 $A[i]$的因子，即数组 $T[i]$存的是所有是 $i$的倍数的数在原数组中的下标
同时我们保证每一个 $T$数组内部都是有序（升序）的
对于每一个操作 $1$ $l$ $r$ $x$，都有如下的操作：
我们直接在 $x$对应的 $T$数组内部进行二分查找，找到那些恰好处于 $[l,r]$的元素，直接将他们除掉 $x$(即 $A[*it]/=x$)，同时对于这些除掉 $x$的新数，如果发现它不再是 $x$的倍数(也可以理解成 $x$不再是新 $A[*it]$的因子)就将新 $A[*it]$从 $x$所对应的 $T$数组中删去
但是现在问题又来了，如何从 $x$所对应的 $T$数组中删去一个数呢？
别忘了我们使用的是一个非常神奇的东西，叫做 $vector$。 $vector$内部自带了一个函数叫做 $vector.erase()$，它可以将一个数从该 $vector$数组中删去
那好了，现在问题就解决了，我们可以开始水掉解决这道题了（雾）
还没完！哪能那么简单让你这么 $A$掉一道紫题？？？
$vector.erase()$函数的神奇之处在于，不仅可以帮你删掉一些数，还可以把你卡死
如果直接正向删数，就会像我一样 $WA$好多次
$Why?$
$vector.erase()$函数删掉一个数之后原其后剩下的数回会整体向 $0$方向平移一个单位
这又是什么意思呢？
其实最开始我也是错了很多次，最后乱改才 $A$掉的
写完之后来翻了一下题解，发现楼下的一位神仙给出了一个例子：
（引用楼下的例子）
如果我们的某一个 $T$数组中存的是这样的序列：
$1$ $2$ $7$ $5$
假设现在我们要删掉 $7$和 $5$
那么对应的删除下标为 $1$和 $0$
正向来删除数的话，我们应该先删掉 $0$位置的元素，即 $5$
那么现在变成了 $1$ $2$ $7$，此时我们还要删掉 $7$
但是如果删掉 $1$位置的元素，那么就会删掉 $2$，而不是 $7$
因此正向删数就会出问题
但是再回来考虑这道题，我们已经保证了每一个 $T$数组内部都是有序（升序）的
因此我们不能正向删数，但是反向删数就没问题
（如果还是不懂，可以按照上面的例子模拟一下）
那么到了这里操作 $1$也就算讲完了吧
操作 $2$嘛。。。就是查询区间和，用树状数组和线段树都可以搞
同时注意一下，每个数 $A[i]$在除掉 $x$之后，要直接在线段树或树状数组对应的位置进行单点修改，由于 $A[i]$除掉了 $x$，因此修改 $A[i]$贡献就是 $-(A[i]-A[i]/x)$
那么就没啥了吧，下面放一波代码
PS：请忽略一些奇怪的变量名，比如树状数组BLT，应为BIT
（因为我最开始学的时候就记错了 $233$）
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#define re register
using namespace std;
typedef long long ll;
char IN[1<<17],*SS=IN,*TT=IN;
inline char gc(){return (SS==TT&&(TT=(SS=IN)+fread(IN,1,1<<17,stdin),SS==TT)?EOF:*SS++);}
inline int read()//fread一发入魂
{
int now=0,f=1;re char c=gc();
for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now*f;}
const int maxn=100003;
const int maxk=500003;
int n,Q,A[maxn];
vector<int> T[maxk];
vector<int>::iterator pos1,pos2,it;
vector<vector<int>::iterator > be_to_del;
namespace BLT//树状数组
{
ll tr[maxn];
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int k){while(x<=n)tr[x]+=k,x+=lowbit(x);}
inline ll sum(int x,ll s=0){while(x)s+=tr[x],x-=lowbit(x);return s;}
inline ll query(int l,int r){return sum(r)-sum(l-1);}
}
using namespace BLT;
inline void work(int pos,int x)//把x的位置存入其因子的对应T数组中
{
for(re int i=1;i<=sqrt(x);i++)
{
if(x%i)continue;
T[i].push_back(pos);
if(x/i!=i)T[x/i].push_back(pos);
//注意平方数的判断
}
}
inline void Clean()
{
vector<vector<int>::iterator> tmp;
swap(tmp,be_to_del);
}
inline void change(int l,int r,int k)
{
if(k==1||T[k].empty())return ;
pos1=lower_bound(T[k].begin(),T[k].end(),l);
pos2=upper_bound(T[k].begin(),T[k].end(),r);
Clean();
for(it=pos1;it!=pos2;++it)//暴力更新
{
if(A[*it]%k)continue;
add(*it,-(A[*it]-A[*it]/k)),A[*it]/=k;
if(A[*it]%k)be_to_del.push_back(it);
//把不再是k的倍数的数都丢进待删除数组
}
if(be_to_del.empty())return ;
for(re int i=be_to_del.size()-1;i>=0;i--)
T[k].erase(be_to_del[i]);//倒序删除数
}
int main()
{
n=read(),Q=read();
for(re int i=1;i<=n;i++)
A[i]=read(),add(i,A[i]),work(i,A[i]);
while(Q--)
{
int flag=read();
if(flag==1)
{
int x=read(),y=read(),k=read();
change(x,y,k);
}
else if(flag==2)
{
int x=read(),y=read();
printf("%lld\n",query(x,y));
}
}
return 0;
}可能写完之后才发现这题是多么的珂学毒瘤（大雾）
到这里就没什么了，感谢你的阅读！
最后无耻的推一波我的 $blog$：
https://www.luogu.org/blog/new2zy/
拜拜~~~
