animalcoder

//题意：1e5区间查询【l,r】内的所有子区间有多少种不同的gcd值//思路：离线BIT//套路：问区间内所有子区间中有多少个数：从右端点小到大处理查询，维护值最近出现的下标 //对每个固定的右端点二分+RMQ维护向左滑动的 lft累计gcd与最右下标 gcd特性：lft大小nlogn //这样我们离线处理的时候可以暴力遍历lft对每个gcd值转移到最右的位置 （这样保证每个gcd...

学了一波树状数组非常好写inline int lowbit(int x){return x&(-x);}inline void add(int x,int d){while(x<=n)c[x]+=d,x+=lowbit(x);}inline ll query(int x){ll res=0;while(x)res+=c[x],x-=lowbit(x);return res;} ...