题解 P3987 【我永远喜欢珂朵莉~】

· · 题解

前言的前言

算是在初一结束之前做了一道Ynoi的毒瘤题了吧。。。

也算了却了一个心愿吧。

前言

作为一个珂学家看到这题就立了个flag要A掉它

然后这题交了49遍才过这么浪费评测机资源会不会被打

换了三四种方法

最后被最后一个点卡了十几次

后来一怒之下把能换int的long long换了就过了(大雾)

正文

前置芝士：线段树 vector iterator

一开始我是根据官方题解的方法来做的

然而本蒟蒻不会平衡树

只能暴力分解因子再暴力查询

结果不断卡常还是只有43-58 pts

因为我比较喜欢线段树所以我写的线段树

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")//请忽略这部分
#include<bits/stdc++.h>
#define rint register int
#define N 100005
#define Num 500005
typedef long long ll;
ll input[N],n,m;
std::vector<ll> f[Num];//存储每个数的因子
inline ll read(){//快读
    ll x=0;
    char ch=getchar();
    while(!isdigit(ch))
     ch=getchar();
    while(isdigit(ch))
     x=(x<<3)+(x<<1)+(ch^48),
      ch=getchar();
    return x;
}
namespace Segment_Tree{//线段树模板
    struct Tree{
        ll l,r,val;
    }tree[N<<2];
    void build(ll index,ll l,ll r){
        tree[index].l=l;
        tree[index].r=r;
        if(l==r){
            tree[index].val=input[l];
            return;
        }
        ll mid=l+r>>1;
        build(index<<1,l,mid);
        build(index<<1|1,mid+1,r);
        tree[index].val=tree[index<<1].val+tree[index<<1|1].val;
        return;
    }
    void sub(ll index,ll dis,ll k){
        tree[index].val-=k;
        if(tree[index].l==tree[index].r)
         return;
        if(dis<=tree[index<<1].r)
         sub(index<<1,dis,k);
        if(dis>=tree[index<<1|1].l)
         sub(index<<1|1,dis,k);
    }
    ll ask(ll index,ll l,ll r){
        if(tree[index].l>=l&&tree[index].r<=r)
          return tree[index].val;
        ll mid=tree[index].l+tree[index].r>>1,ans=0;
        if(l<=mid)
         ans+=ask(index<<1,l,r);
        if(r>mid)
         ans+=ask(index<<1|1,l,r);
        return ans;
    }
}
using namespace Segment_Tree;
inline void trace(ll num){//暴力分解因子
    ll top=std::sqrt(num);
    for(rint i=2;i<=top;++i){
        if(num%i)
         continue;
        f[num].push_back(i);
    }
    ll count=f[num].size();
    for(rint i=count;i<count*2;++i)
     f[num].push_back(num/f[num][i-count]);
    f[num].push_back(num);
    return;
}
inline void find(ll l,ll r,ll k){//区间除
    if(k==1)
     return;
    for(rint i=l;i<=r;++i){
        ll key=INT_MAX;
        for(rint j=0;j<f[input[i]].size();++j){//暴力查找
            if(f[input[i]][j]==k){
                key=j;
                break;
            }
        }
        if(key==INT_MAX)
         continue;
        ll t=input[i];
        input[i]/=k;
        sub(1,i,t-input[i]);//线段树单点修改
    }
    return;
}
int main(){
    //freopen("input.txt","r",stdin);
    for(rint i=2;i<=500000;++i)
     trace(i); //分解因子
    n=read(),m=read();
    for(rint i=1;i<=n;++i)
     input[i]=read();
    build(1,1,n);
    for(rint i=1;i<=m;++i){
        ll q=read();
        switch(q){
            case 1:{
                //printf("it's question 1.\n");
                ll l=read(),r=read(),k=read();
                find(l,r,k);
                break;
            }
            case 2:{
                //printf("it's question 2.\n");
                ll l=read(),r=read();
                printf("%lld\n",ask(1,l,r));
                break;
            }
        }
    }
}

然后接下来一整天本蒟蒻都在考虑怎么优化

离线分解也莫名其妙T掉

平衡树我又不会

只能换一种做法

于是我把希望寄托于：

vector

对于每一个input[i]，我们开一个vector，它们的值都是input[i]的因子，即f[i][j]存的是所有是i的j倍数的数在原数组中的下标，在输入的时候直接与处理好

但是如果暴力枚举还是会T掉

这是我们就要引进两个STL自带函数：

lower$ $bound upper$ $bound 在从小到大的有序数组中， $lower$ $bound(begin,end,num)$：从数组的$begin$位置到$end-1$位置二分查找第一个大于或等于$num$的数字，找到返回该数字的地址，不存在则返回$end$。 $upper$ $bound(begin,end,num)$：从数组的$begin$位置到$end-1$位置二分查找第一个大于$num$的数字，找到返回该数字的地址，不存在则返回$end$。 这和这里有什么关系呢？ #### $lower$ $bound(f[k].begin(),f[k].end(),l)$到$upper$ $bound(f[k].begin(),f[k].end(),r)$刚好就是这个要改变的区间！ 但是因为$lower$ $bound$ 和 $upper$ $bound$ 返回的是一个地址，所以要用$iterator$($STL$迭代器，珂以理解为$STL$的指针)来存储 除完之后我们要删除其他消失的因子 这时我们就要引进一个神奇的东西：$vector$自带的$erase

但是erase正向删数会出现问题(删除一个数后后面的数下标都会 -1)，所以要反向删数，这个其他题解已近讲得很清楚了，这里不再赘述。

至此我们有了满分的AC代码：

祭上代码

#pragma GCC optimize("O3")
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")//同上
#include<bits/stdc++.h>
#define rint register int
#define N 100005
#define Num 500005
typedef long long ll;
int input[N],n,m;
std::vector<int> f[Num];//存储因子
std::vector<int>::iterator p1,p2,it;
std::vector<std::vector<int>::iterator> del;//存储要删除的数
inline void write(ll x){//快写
     if(x>9) 
      write(x/10);
     putchar(x%10+'0');
}
inline int read(){//快读
    int x=0;
    char ch=getchar();
    while(!isdigit(ch))
     ch=getchar();
    while(isdigit(ch))
     x=(x<<3)+(x<<1)+(ch^48),
      ch=getchar();
    return x;
}
namespace Segment_Tree{//线段树模板
    struct Tree{
        int l,r;
        ll val;
    }tree[N<<2];
    void build(int index,int l,int r){
        tree[index].l=l;
        tree[index].r=r;
        if(l==r){
            tree[index].val=input[l];
            return;
        }
        int mid=l+r>>1;
        build(index<<1,l,mid);
        build(index<<1|1,mid+1,r);
        tree[index].val=(ll)(tree[index<<1].val+tree[index<<1|1].val);
        return;
    }
    void sub(int index,int dis,int k){
        tree[index].val-=k;
        if(tree[index].l==tree[index].r)
         return;
        if(dis<=tree[index<<1].r)
         sub(index<<1,dis,k);
        if(dis>=tree[index<<1|1].l)
         sub(index<<1|1,dis,k);
    }
    ll ask(int index,int l,int r){
        if(tree[index].l>=l&&tree[index].r<=r)
          return tree[index].val;
        int mid=tree[index].l+tree[index].r>>1;
        ll ans=0;
        if(l<=mid)
         ans+=ask(index<<1,l,r);
        if(r>mid)
         ans+=ask(index<<1|1,l,r);
        return ans;
    }
}
using namespace Segment_Tree;
inline void trace(int index,int num){//分解因子
    for(rint i=1;i*i<=num;++i){
        if(num%i)
         continue;
        f[i].push_back(index);
        if(num/i^i)
         f[num/i].push_back(index);
    }
}
inline void find(int l,int r,int k){
    if(k==1||f[k].empty()) //剪枝
     return;
    p1=std::lower_bound(f[k].begin(),f[k].end(),l);
    p2=std::upper_bound(f[k].begin(),f[k].end(),r);//查找区间
    if(p1==f[k].end())//剪枝
     return;
    del.clear();
    for(it=p1;it!=p2;++it){//暴力更新因子
        if(input[*it]%k)
         continue;
        int val=input[*it],w=val/k;
        sub(1,*it,input[*it]-input[*it]/k);
        input[*it]/=k;
        val=input[*it];
        if(val%k)
         del.push_back(it);
    }
    for(rint i=del.size()-1;i>0;--i)
     f[k].erase(del[i]); //暴力删除数
}
int main(){
    n=read(),m=read();
    for(rint i=1;i<=n;++i)
     input[i]=read(),trace(i,input[i]);//读入顺便处理
    build(1,1,n);//建树
    while(m--){
        int q=read();
        switch(q){
            case 1:{
                int l=read(),r=read(),k=read();
                find(l,r,k);
                break;
            }
            case 2:{
                int l=read(),r=read();
                write(ask(1,l,r));
                putchar('\n');
                break;
            }
        }
    }
}