首页 > 代码库 > codeforces438D The Child and Sequence
codeforces438D The Child and Sequence
题面：codeforces438D
正解：线段树。
这题好像是$picks$出的题，然后无限弱化才上的$cf$。。
区间取模，每个数取模以后至少$/2$，所以暴力搞即可。
证明：若$p<x/2$，那么$x \ mod \ p<x/2$；若$p>x/2$，那么$ x \ mod \ p=x-p<x/2$。
维护一个区间最大值，如果$<p$那么就直接退出，否则把这个区间递归做再取模。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <queue>10 #include <stack>11 #include <map>12 #include <set>13 #define N (200010)14 #define ls (x<<1)15 #define rs (x<<1|1)16 #define il inline17 #define RG register18 #define ll long long19 20 using namespace std;21 22 int mx[N<<2],a[N],n,m;23 ll sum[N<<2];24 25 il int gi(){26 RG int x=0,q=1; RG char ch=getchar();27 while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();28 if (ch==‘-‘) q=-1,ch=getchar();29 while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();30 return q*x;31 }32 33 il void pushup(RG int x){34 sum[x]=sum[ls]+sum[rs],mx[x]=max(mx[ls],mx[rs]); return;35 }36 37 il void build(RG int x,RG int l,RG int r){38 if (l==r){ sum[x]=mx[x]=a[l]; return; } RG int mid=(l+r)>>1;39 build(ls,l,mid),build(rs,mid+1,r),pushup(x); return;40 }41 42 il void update(RG int x,RG int l,RG int r,RG int p,RG int v){43 if (l==r){ sum[x]=mx[x]=v; return; } RG int mid=(l+r)>>1;44 p<=mid?update(ls,l,mid,p,v):update(rs,mid+1,r,p,v);45 pushup(x); return;46 }47 48 il void updatemod(RG int x,RG int l,RG int r,RG int xl,RG int xr,RG int v){49 if (l==r){ sum[x]%=v,mx[x]%=v; return; }50 if (mx[x]<v) return; RG int mid=(l+r)>>1;51 if (xr<=mid) updatemod(ls,l,mid,xl,xr,v);52 else if (xl>mid) updatemod(rs,mid+1,r,xl,xr,v);53 else updatemod(ls,l,mid,xl,mid,v),updatemod(rs,mid+1,r,mid+1,xr,v);54 pushup(x); return;55 }56 57 il ll query(RG int x,RG int l,RG int r,RG int xl,RG int xr){58 if (xl<=l && r<=xr) return sum[x]; RG int mid=(l+r)>>1;59 if (xr<=mid) return query(ls,l,mid,xl,xr);60 else if (xl>mid) return query(rs,mid+1,r,xl,xr);61 else return query(ls,l,mid,xl,mid)+query(rs,mid+1,r,mid+1,xr);62 }63 64 int main(){65 #ifndef ONLINE_JUDGE66 freopen("438D.in","r",stdin);67 freopen("438D.out","w",stdout);68 #endif69 n=gi(),m=gi();70 for (RG int i=1;i<=n;++i) a[i]=gi(); build(1,1,n);71 for (RG int i=1,op,l,r,x,k;i<=m;++i){72 op=gi();73 if (op==1) l=gi(),r=gi(),printf("%I64d\n",query(1,1,n,l,r));74 if (op==2) l=gi(),r=gi(),x=gi(),updatemod(1,1,n,l,r,x);75 if (op==3) k=gi(),x=gi(),update(1,1,n,k,x);76 }77 return 0;78 }
codeforces438D The Child and Sequence
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。