Codeforces 438D The Child and Sequence

题目链接：http://codeforces.com/contest/438/problem/D

要求线段树区间取模，单点修改，区间求和。

做法很简单，就是维护一个区间最大值，当这个区间的最大值都要小于我要取模的这个值的时候就直接$return$。

为什么能过？　　

额。。。。。

没错就是这样，单点加法每次也只恢复了一个点的|势能|,而势能是最多减少$log$次的。(让我思考一下啊换成区间修改这题怎么捉...)

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<vector>
  5 #include<cstdlib>
  6 #include<cmath>
  7 #include<cstring>
  8 using namespace std;
  9 #define maxn 1001000
 10 #define llg long long 
 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
 12 llg n,m,type,val[maxn],mx[maxn],T;
 13 
 14 inline llg getint()
 15 {
 16     llg w=0,q=0; char c=getchar();
 17        while((c<'0' || c>'9') && c!='-') c=getchar(); if(c=='-') q=1,c=getchar(); 
 18        while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); return q ? -w : w;
 19 }
 20 
 21 void build(llg o,llg l,llg r)
 22 {
 23     if (l==r)
 24     {
 25         val[o]=getint();
 26         mx[o]=val[o];
 27         return ;
 28     }
 29     llg lc=o<<1,rc=o<<1|1,mid=(l+r)>>1;
 30     build(lc,l,mid); build(rc,mid+1,r);
 31     mx[o]=max(mx[lc],mx[rc]);
 32     val[o]=val[lc]+val[rc];
 33 }
 34 
 35 llg sum(llg o,llg l,llg r,llg L,llg R)
 36 {
 37     if (l>=L && r<=R) return val[o];
 38     llg lc=o<<1,rc=o<<1|1,mid=(l+r)>>1,SUM=0;
 39     if (mid>=L) SUM+=sum(lc,l,mid,L,R);
 40     if (mid<R) SUM+=sum(rc,mid+1,r,L,R);
 41     return SUM;
 42 }
 43 
 44 void modify(llg o,llg l,llg r,llg x,llg v)
 45 {
 46     if (l==r)
 47     {
 48         val[o]=mx[o]=v;
 49         return ;
 50     }    
 51     llg lc=o<<1,rc=o<<1|1,mid=(l+r)>>1;
 52     if (mid>=x) modify(lc,l,mid,x,v);
 53     if (mid<x) modify(rc,mid+1,r,x,v);
 54     val[o]=val[lc]+val[rc];
 55     mx[o]=max(mx[lc],mx[rc]);
 56 }
 57 
 58 void mod(llg o,llg l,llg r,llg L,llg R,llg v)
 59 {
 60     if (mx[o]<v) return ;//!!!!!!
 61     if (l==r)
 62     {
 63         val[o]%=v; mx[o]=val[o];
 64         return ;
 65     }    
 66     llg lc=o<<1,rc=o<<1|1,mid=(l+r)>>1;
 67     if (mid>=L) mod(lc,l,mid,L,R,v);
 68     if (mid<R) mod(rc,mid+1,r,L,R,v);
 69     val[o]=val[lc]+val[rc];
 70     mx[o]=max(mx[lc],mx[rc]);
 71 }
 72 
 73 int main()
 74 {
 75     yyj("sep");
 76     cin>>n>>T;
 77     build(1,1,n);;
 78     while (T--)
 79     {
 80         type=getint();
 81         if (type==1) 
 82         {
 83             llg l,r;
 84             l=getint(),r=getint();
 85             printf("%lld
",sum(1,1,n,l,r));    
 86         }    
 87         if (type==2) 
 88         {
 89             llg l,r,x;
 90             l=getint(),r=getint(),x=getint();
 91             mod(1,1,n,l,r,x);
 92         }
 93         if (type==3) 
 94         {
 95             llg k,x;
 96             k=getint(),x=getint();
 97             modify(1,1,n,k,x);
 98         }
 99     }
100     return 0;
101 }