[洛谷P3987]我永远喜欢珂朵莉~

题目大意：

给你一个数列。有两个操作：

1. 给一个区间内所有(v_i)的倍数除以(v_i)。
2. 询问区间和。

解题思路：

首先，建(10^6)棵平衡树（不要慌o((⊙﹏⊙))o）。

然后对操作离线。

对于每个初始的数(a_i)，暴算出他的所有约数，并把(i)丢进与约数相应的平衡树里（如果修改中没出现这个约数则忽略即可）。

由于(10^6)内约数最多的数也只有200来个约数，所以不用担心空间问题。

接下来处理操作。

对于每个修改，我们直接在相应的平衡树中找到修改区间内的数，然后若(a_i)是v的倍数，则(a_i)除以v，若除完后(a_i)不是(v)的倍数了（或本身已经不是了），则在这个平衡树中删除这个数。

注意本身可能已经在其他v的修改中除掉了某个约数，所以仍然要判是否整除。

区间求和什么的，树状数组即可。

C++ Code：

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define reg register
using LoveLive=long long;
const int M=1e6+5,N=1e5+5;
LoveLive btr[M];
int n,m,a[N],opt[N],L[N],R[N],v[N],cnt=0,rt[M],nodes=0;
std::vector<int>V[1000005];std::stack<int>st;
struct node{
    int ls,rs,r,v,sz;
}d[M<<6];
bool vis[M];
inline void add(int x,int d){for(;x<=M;x+=x&-x)btr[x]+=d;}
inline LoveLive ask(int x){reg LoveLive r=0;for(;x;x-=x&-x)r+=btr[x];return r;}
inline int readint(){
    reg int c=getchar(),d=0;
    for(;!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar())
    d=(d<<3)+(d<<1)+(c^'0');
    return d;
}
inline int merge(int x,int y){
    if(!x||!y)return x|y;
    if(d[x].r<d[y].r){
        d[x].rs=merge(d[x].rs,y);
        return x;
    }
    d[y].ls=merge(x,d[y].ls);
    return y;
}
inline void split(int u,int k,int&x,int&y){
    if(!u)return void(x=y=0);
    if(d[u].v<=k)
    split(d[x=u].rs,k,d[u].rs,y);else
    split(d[y=u].ls,k,x,d[u].ls);
}
inline void Delete(int&rt,int x){
    reg int a,b;
    split(rt,x-1,rt,a);
    split(a,x,a,b);
    rt=merge(rt,b);
}
int build(int l,int r,int&i){
    if(l>r)return 0;
    reg int nw=++nodes,mid=l+r>>1;
    d[nw]=(node){0,0,rand(),V[i][mid]};
    d[nw].ls=build(l,mid-1,i);
    d[nw].rs=build(mid+1,r,i);
    return nw;
}
void dfs(int now,int&v){
    if(!now)return;
    dfs(d[now].ls,v),dfs(d[now].rs,v);
    int&nw=a[d[now].v];
    if(nw%v==0){
        add(d[now].v,nw/v-nw);
        nw/=v;
    }
    if(nw%v)st.push(d[now].v);
}
int main(){
    srand(time(0));
    srand(rand());
    n=readint(),m=readint();
    for(reg int i=1;i<=n;++i)add(i,a[i]=readint());
    for(reg int i=1;i<=m;++i){
        opt[i]=readint(),L[i]=readint(),R[i]=readint();
        if(opt[i]==1)vis[v[i]=readint()]=1;
    }
    //begin 寻找每个数的约数并将每个数的位置插入对应的平衡树 
    for(reg int i=1;i<=n;++i){
        reg int&nw=a[i];
        for(reg int j=1;j*j<=a[i];++j)
        if(nw%j==0){
            if(vis[j]&&j>1)V[j].push_back(i);
            if(j*j<nw&&vis[nw/j])V[nw/j].push_back(i);
        }
    }
    for(reg int i=2;i<M;++i)
    if(V[i].size())rt[i]=build(0,V[i].size()-1,i);
    //end 
    //begin 查询及修改 
    for(reg int i=1;i<=m;++i)
    if(opt[i]==1){
        if(v[i]>1){
            reg int&nw=rt[v[i]],x,y;
            split(nw,L[i]-1,nw,x);
            split(x,R[i],x,y);
            dfs(x,v[i]);
            nw=merge(merge(nw,x),y);
            while(!st.empty()){
                reg int p=st.top();
                st.pop();
                split(nw,p-1,nw,x);
                split(x,p,x,y);
                nw=merge(nw,y);
            }
        }
    }else printf("%lld
",ask(R[i])-ask(L[i]-1));
    //end 
    return 0;
}

[洛谷P3987]我永远喜欢珂朵莉~

相关推荐