费解的gcd

费解的gcd

https://ac.nowcoder.com/acm/contest/71419/F

浅浅来一个线段树的解法,希望能帮到大家

using namespace std;
const int N=1e6+9,mod=998244353;
int n,q;
int a[N],b[N],e[N];
int ne[N*4];
void pruck(int u)//求结点值
{
    ne[u]=__gcd(ne[u<<1],ne[u<<1|1]);
}
void build(int u,int l,int r)//建树
{
    if(l==r)
    {
        ne[u]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pruck(u);
}
void date(int u,int x,int l,int r)//更新结点数据
{
    if(l==r&&l==x)
    {
        ne[u]=0;
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=x)
        date(u<<1,x,l,mid);
    else
        date(u<<1|1,x,mid+1,r);
    pruck(u);
}
void solve()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build(1,1,n);
    int ans=0;
    for(int i=1;i<=q;i++)
    {
        cin>>e[i];
        if(e[i]==0)
        {
            ans=(ans+ne[1])%mod;
        }
        else
        {
            date(1,e[i],1,n);
        }
    }
    cout<<ans<<'\n';
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
}
全部评论

相关推荐

笔试域名是show&nbsp;me&nbsp;bug
投递挚文集团等公司7个岗位 >
点赞 评论 收藏
分享
#简历#先说一说我自己的想法,很多人都很排斥苍穹外卖,认为没什么技术点和含金量,但实际上我觉得恰恰相反,苍穹外卖虽然代码本身并不是你自身能力的证明,但是是作为一个新人学习时很好的跳板和原始框架,在这个框架上进行的改进可以很好的辐射到你自己的个人成果上,并作为你和面试官聊天的筹码大多数人的苍穹外卖只写增删改查,千篇一律,吸引不了面试官,所以这才让大家误以为只要是苍穹外卖就不要写进简历里这种误区,但实际上如果你在原有的层面上进行改进,并作为你的项目亮点和面试官介绍,告诉他你的苍穹外卖和别人的有什么不同,增加了哪些技术难点,这才显得你是完全自己理解了这个项目,并且有自己动手实践项目的能力,而不是就看了个课程就以为自己会了,就当成自己的了,如此一来,这反而成为你的加分项苍穹外卖为什么看的人最多,说明它好啊,如果它不好,为什么看的人还这么多,想清楚这个逻辑,我觉得要做的最重要的事,就是如何在原有框架上进行改进提效,比起听其他人的话重新搞一个项目性价比高得多,而且我亲测项目并没有成为我找到工作的阻碍,我投的大厂一大半都给我面试了,而且很多不止一个部门,退一万步说,当你手头没有其他项目的时候,有苍穹外卖总比什么都没有的好很多,不需要因为苍穹外卖有任何心理负担关于简历的任何部分都欢迎大家提意见,十分感谢大家,祝大家找实习+秋招顺利上岸,offer拿到手软#简历中的项目经历要怎么写##我的上岸简历长这样##最后再改一次简历##简历##简历被挂麻了,求建议#
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务