AC日记——由乃与大母神原型和偶像崇拜 洛谷 P3792

由乃与大母神原型和偶像崇拜

思路：

　　逆元+线段树维护和+线段树维护平方和+线段树维护最大最小值；

代码：

#include <bits/stdc++.h>

using namespace std;

#define maxn 500005

#define ll long long

#define llf ll

#define INF 0x7fffffff

#define True_Ans "damushen"

#define False_Ans "yuanxing"

#define mod (1000000009LL)

#define mod_ (833333341LL)

struct TreeNodeType {

    int l,r,mid,maxval,minval;

    ll sumval;

    llf sumval2;

};

struct TreeNodeType tree[maxn<<];

int n,m,qmax,qmin;

ll qsum;

llf qsum2;

inline void in(int &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'') Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

inline void in(ll &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'') Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

void tree_build(int now,int l,int r)

{

    tree[now].l=l,tree[now].r=r;

    if(l==r)

    {

        in(tree[now].sumval),tree[now].sumval2=(tree[now].sumval*tree[now].sumval)%mod;

        tree[now].maxval=tree[now].sumval,tree[now].minval=tree[now].sumval;return;

    }

    tree[now].mid=l+r>>,tree_build(now<<,l,tree[now].mid),tree_build(now<<|,tree[now].mid+,r);

    tree[now].sumval=tree[now<<].sumval+tree[now<<|].sumval;

    tree[now].sumval2=(tree[now<<].sumval2+tree[now<<|].sumval2)%mod;

    tree[now].maxval=max(tree[now<<].maxval,tree[now<<|].maxval);

    tree[now].minval=min(tree[now<<].minval,tree[now<<|].minval);

}

void tree_query(int now,int l,int r)

{

    if(tree[now].l>=l&&tree[now].r<=r)

    {

        qmax=max(qmax,tree[now].maxval),qmin=min(qmin,tree[now].minval);

        qsum+=tree[now].sumval,qsum2+=tree[now].sumval2;return;

    }

    if(l<=tree[now].mid) tree_query(now<<,l,min(tree[now].mid,r));

    if(r>tree[now].mid) tree_query(now<<|,max(tree[now].mid+,l),r);

}

void tree_change(int now,int to,int val_)

{

    if(tree[now].l==tree[now].r)

    {

        tree[now].sumval=val_,tree[now].maxval=val_,tree[now].minval=val_;

        tree[now].sumval2=(tree[now].sumval*tree[now].sumval)%mod;return;

    }

    if(to<=tree[now].mid) tree_change(now<<,to,val_);

    else tree_change(now<<|,to,val_);

    tree[now].sumval=tree[now<<].sumval+tree[now<<|].sumval;

    tree[now].sumval2=(tree[now<<].sumval2+tree[now<<|].sumval2)%mod;

    tree[now].maxval=max(tree[now<<].maxval,tree[now<<|].maxval);

    tree[now].minval=min(tree[now<<].minval,tree[now<<|].minval);

}

llf Sum2(int r)

{

    llf R_=r;

    return (((((R_*(R_+))%mod)*(R_*+))%mod)*)%mod;

}

ll Sum(int l,int r)

{

    ll L_=l,s=r-l+;

    return L_*s+s*(s-)/;

}

int main()

{

    in(n),in(m),tree_build(,,n);

    llf lfpos;ll llpos;int op,l,r;

    for(;m--;)

    {

        in(op),in(l),in(r);

        if(op==) tree_change(,l,r);

        else

        {

            qsum=,qsum2=,qmax=,qmin=INF,tree_query(,l,r);

            if(qmax-qmin==r-l)

            {

                if(qsum==Sum(qmin,qmax))

                {

                    if((qsum2+Sum2(qmin-))%mod==Sum2(qmax)) puts(True_Ans);

                    else puts(False_Ans);

                }

                else puts(False_Ans);

            }

            else puts(False_Ans);

        }

    }

    return ;

}