首页 > 代码库 > HDU 4902 Nice boat 多校4 线段树

HDU 4902 Nice boat 多校4 线段树

给定n个数

第一个操作和普通,区间覆盖性的,把l-r区间的所有值改成固定的val

第二个操作是重点,输入l r x 把l-r区间的所有大于x的数,变成gcd(a[i],x) a[i]即指满足条件的序列上的数值

最后才输出所有值

当时苦思这个地方如何优化,想着不可能单点去更新吧,但是区间gcd,不能保存下来,一来他是要>x才有效,本来聪哥想了一种先把各种x gcd一遍,最后在push下去,发现不行,就是因为他对>x才有效,你在区间就直接gcd了,那不是把不该gcd的也给搞了

还想过说先存起来所有的x,当然也有限制条件,就是说比较大的就不要了,因为gcd越搞越小,你后面来个大的x没意义,最后再push下去。。。我这样敲了一下,wa了,后来分析下,觉得这个根顺序还是有关系,我直接记录完,push下去没讲顺序 还是有问题的

 

后来居然claration有人讲他暴力过的,。。我也是醉了

当然不是真的完全暴力,还是要优化的,一个是大家都做了的,就是利用第一个操作,如果某区间都是一个值,那gcd直接在这个区间跟这个值弄一下,就可以了,不用再往下走了。

我还做了另一个优化,就是记录每个区间的最大值,要是当前x走到某个区间,发现比最大值还>=,那直接return即可,没有任何意义

后来终于是AC了,注意点细节,没什么太难的。不过后来讨论到为什么可以这样不超时,聪哥说有个lamp定理,可以证明每个int整数,最多不超过31次gcd就会变成1(感觉像二分一样,聪哥说这玩意衰变得很快),也就是说,我有了上述优化之后,实际每个数最多只要31次更新到底即可,n个数只要n*31次更新到底即可,其他的都会被优化掉,所以为什么不会超时。。。虽然我不明白这个31次是怎么来的,不过如果这个是成立的,那就完全可以解释这个算法了。,明天还去跟聪哥讨论一下这个lamp定理,看下到底是怎么证明出31次的

 

后来我AC之后又想优化一下,把原因的1操作的懒惰标记iss想变成状态型的,比如单个节点iss永远是1,表示他就是被自己覆盖了嘛,但是会WA,就是说,你状态型的,你上面的结构也要保持该状态,上面没处理好,很麻烦的。。所以不建议是这么混着来,懒惰标记就是懒惰标记,别混成状态标记了

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define LL __int64using namespace std;const int N=100000+10;int A[N];int setv[N<<2],iss[N<<2],d[N<<2];int gcd(int a,int b){    if (abs(a)<abs(b)) swap(a,b);    while (b)    {        int tmp=a;        a=b;        b=tmp%b;    }    return a;}int n;void up(int rt){    d[rt]=max(d[rt<<1],d[rt<<1|1]);    if (setv[rt<<1]==setv[rt<<1|1] && iss[rt<<1] && iss[rt<<1|1]){        setv[rt]=setv[rt<<1];        iss[rt]=1;    }}void build(int rt,int l,int r){    iss[rt]=setv[rt]=0;    if (l>=r)    {        d[rt]=A[l];        return;    }    int mid=(l+r)>>1;    build(lson);    build(rson);    up(rt);}void pushdown(int rt,int l,int r){    if (l>=r) return;    if (iss[rt]){        d[rt]=setv[rt];        setv[rt<<1]=setv[rt<<1|1]=setv[rt];        d[rt<<1]=d[rt<<1|1]=setv[rt];        iss[rt<<1]=iss[rt<<1|1]=iss[rt];        iss[rt]=0;    }}void fix(int L,int R,int val,int rt,int l,int r){    if (L<=l && r<=R)    {        iss[rt]=1;        setv[rt]=val;        d[rt]=val;        if (l==r) A[l]=val;        return;    }    pushdown(rt,l,r);    int mid=(l+r)>>1;    if (R<=mid) fix(L,R,val,lson);    else    if (L>mid)  fix(L,R,val,rson);    else{        fix(L,R,val,lson);        fix(L,R,val,rson);    }    up(rt);}void fgcd(int L,int R,int val,int rt,int l,int r){    if (val>=d[rt]) return;    if (iss[rt] && L<=l && r<=R && l<r){        if (setv[rt]>val){            setv[rt]=gcd(setv[rt],val);            d[rt]=setv[rt];        }        return;    }    if (L==l && r==R && l==r)    {        if (iss[rt]){            A[l]=setv[rt];            d[rt]=A[l];            iss[rt]=0;        }        if (A[l]>val){            A[l]=gcd(A[l],val);            d[rt]=A[l];        }        return;    }    pushdown(rt,l,r);    int mid=(l+r)>>1;    if (R<=mid) fgcd(L,R,val,lson);    else    if (L>mid) fgcd(L,R,val,rson);    else    {        fgcd(L,mid,val,lson);        fgcd(mid+1,R,val,rson);    }    up(rt);}void merges(int rt,int l,int r){    if (l>=r)    {        if (iss[rt]){            A[l]=setv[rt];            d[l]=setv[rt];            iss[rt]=0;        }        return;    }    int mid=(l+r)>>1;    pushdown(rt,l,r);    merges(lson);    merges(rson);}int main(){    int t,q,op;    scanf("%d",&t);    while (t--)    {        scanf("%d",&n);        for (int i=1;i<=n;i++){            scanf("%d",&A[i]);        }        build(1,1,n);        scanf("%d",&q);        while (q--)        {            int a,b,x;            scanf("%d",&op);            scanf("%d%d%d",&a,&b,&x);            if (op==1){                fix(a,b,x,1,1,n);            }            else{                fgcd(a,b,x,1,1,n);            }        }        merges(1,1,n);        for (int i=1;i<=n;i++){            printf("%d ",A[i]);        }        puts("");    }    return 0;}