1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108
| #include <bits/stdc++.h> #define MAXN 500005 using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } int a[MAXN]; namespace SegmentTree{ struct node{ int l,r; long long sum; int mino,maxn; }tree[MAXN<<2]; #define lc i<<1 #define rc i<<1|1 inline void pushup(int i){ tree[i].sum=tree[lc].sum+tree[rc].sum; tree[i].maxn=max(tree[lc].maxn,tree[rc].maxn); tree[i].mino=min(tree[lc].mino,tree[rc].mino); } inline void Set(int i,int val){ tree[i].sum=val*val; tree[i].mino=tree[i].maxn=val; } void Build(int i,int l,int r){ tree[i].l=l,tree[i].r=r; if (l==r){ Set(i,a[l]); return ; } int mid=(l+r)>>1; Build(lc,l,mid); Build(rc,mid+1,r); pushup(i); } void Update(int i,int pos,int val){ if (tree[i].l==tree[i].r){ Set(i,val); return ; } int mid=(tree[i].l+tree[i].r)>>1; if (pos<=mid) Update(lc,pos,val); else Update(rc,pos,val); pushup(i); } int QueryMax(int i,int L,int R){ if (L<=tree[i].l&&tree[i].r<=R){ return tree[i].maxn; } int mid=(tree[i].l+tree[i].r)>>1,ans=-0x7fffffff; if (L<=mid) ans=max(ans,QueryMax(lc,L,R)); if (mid<R) ans=max(ans,QueryMax(rc,L,R)); return ans; } int QueryMin(int i,int L,int R){ if (L<=tree[i].l&&tree[i].r<=R){ return tree[i].mino; } int mid=(tree[i].l+tree[i].r)>>1,ans=0x7fffffff; if (L<=mid) ans=min(ans,QueryMin(lc,L,R)); if (mid<R) ans=min(ans,QueryMin(rc,L,R)); return ans; } long long QuerySum(int i,int L,int R){ if (L<=tree[i].l&&tree[i].r<=R){ return tree[i].sum; } int mid=(tree[i].l+tree[i].r)>>1; long long ans=0; if (L<=mid) ans+=QuerySum(lc,L,R); if (mid<R) ans+=QuerySum(rc,L,R); return ans; } } using namespace SegmentTree; int main(){ int n=read(),m=read(); for (register int i=1;i<=n;++i){ a[i]=read(); } Build(1,1,n); while (m--){ int opr=read(); if (opr==1){ int x=read(),y=read(); Update(1,x,y); } else { int l=read(),r=read(); int fi=QueryMin(1,l,r),ed=QueryMax(1,l,r); if (r-l!=ed-fi){puts("yuanxing");continue;} long long ans=0; for (register int i=fi;i<=ed;++i) ans+=(long long)(i*i); if (ans==QuerySum(1,l,r)) puts("damushen"); else puts("yuanxing"); } } }
|