首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。