首页 > 代码库 > AC日记——由乃与大母神原型和偶像崇拜 洛谷 P3792

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<<2];int n,m,qmax,qmin;ll qsum;llf qsum2;inline void in(int &now){    char Cget=getchar();now=0;    while(Cget>9||Cget<0) Cget=getchar();    while(Cget>=0&&Cget<=9)    {        now=now*10+Cget-0;        Cget=getchar();    }}inline void in(ll &now){    char Cget=getchar();now=0;    while(Cget>9||Cget<0) Cget=getchar();    while(Cget>=0&&Cget<=9)    {        now=now*10+Cget-0;        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>>1,tree_build(now<<1,l,tree[now].mid),tree_build(now<<1|1,tree[now].mid+1,r);    tree[now].sumval=tree[now<<1].sumval+tree[now<<1|1].sumval;    tree[now].sumval2=(tree[now<<1].sumval2+tree[now<<1|1].sumval2)%mod;    tree[now].maxval=max(tree[now<<1].maxval,tree[now<<1|1].maxval);    tree[now].minval=min(tree[now<<1].minval,tree[now<<1|1].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<<1,l,min(tree[now].mid,r));    if(r>tree[now].mid) tree_query(now<<1|1,max(tree[now].mid+1,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<<1,to,val_);    else tree_change(now<<1|1,to,val_);    tree[now].sumval=tree[now<<1].sumval+tree[now<<1|1].sumval;    tree[now].sumval2=(tree[now<<1].sumval2+tree[now<<1|1].sumval2)%mod;    tree[now].maxval=max(tree[now<<1].maxval,tree[now<<1|1].maxval);    tree[now].minval=min(tree[now<<1].minval,tree[now<<1|1].minval);}llf Sum2(int r){    llf R_=r;    return (((((R_*(R_+1))%mod)*(R_*2+1))%mod)*833333341)%mod;}ll Sum(int l,int r){    ll L_=l,s=r-l+1;    return L_*s+s*(s-1)/2;}int main(){    in(n),in(m),tree_build(1,1,n);    llf lfpos;ll llpos;int op,l,r;    for(;m--;)    {        in(op),in(l),in(r);        if(op==1) tree_change(1,l,r);        else        {            qsum=0,qsum2=0,qmax=0,qmin=INF,tree_query(1,l,r);            if(qmax-qmin==r-l)            {                if(qsum==Sum(qmin,qmax))                {                    if((qsum2+Sum2(qmin-1))%mod==Sum2(qmax)) puts(True_Ans);                    else puts(False_Ans);                }                else puts(False_Ans);            }            else puts(False_Ans);        }    }    return 0;}

 

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