hdu 4578 Transformation - c++编程基础

TOP

hdu 4578 Transformation

2015-07-20 17:51:56 来源: 作者: 【大中小】浏览:3次

Tags：hdu 4578 Transformation

又做了一道好题。。

有三种操作：

1 a b c [a,b]加上c

2 a b c [a,b]乘上c

3 a b c [a,b]变为c

4 a b c 求[a,b]的c次方和(1<=c<=3)

这题首先需要解决的第一个问题是加上或乘上一个数对这个区间的c次方和分别产生什么改变，很简单，一化简就能得到。

第二个问题是当一段区间上既有乘又有加的lazy时应该怎么向下推送，因为一段区间上只能有一个lazy，我起初做的是先将有lazy的标记向下传，直到不冲突为止，然后更新这个区间的lazy，后来无数次的wa。代码太长了，简直无法debug。

同学说要找到这两个lazy的关系，即可以把每个数看做mult * x + add。加上一个数y时,add+= y，乘上一个数y时，mult *= y，add *= y。这样就解决了先加后乘和先乘后加的问题了，感觉好机智，mark。

#include 
  
   
#include 
   
     #include
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                //#define LL long long #define LL __int64 #define eps 1e-12 #define PI acos(-1.0) using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 100010; const int mod = 10007; struct node { int l,r; int mult,add; int s[4]; } tree[maxn*4]; void build(int v, int l, int r) { tree[v].l = l; tree[v].r = r; tree[v].mult = 1; tree[v].add = 0; tree[v].s[1] = tree[v].s[2] = tree[v].s[3] = 0; if(l == r) return; int mid = (l+r)>>1; build(v*2,l,mid); build(v*2+1,mid+1,r); } void cal(int v,int mult, int add) { int len = tree[v].r - tree[v].l + 1; tree[v].s[1] = tree[v].s[1] * mult%mod; tree[v].s[2] = tree[v].s[2] * mult%mod*mult%mod; tree[v].s[3] = tree[v].s[3] * mult%mod*mult%mod*mult%mod; tree[v].mult = (tree[v].mult * mult)%mod; tree[v].add = (tree[v].add * mult)%mod; tree[v].s[3] = (tree[v].s[3] + 3*add%mod*add%mod*tree[v].s[1]%mod)%mod; tree[v].s[3] = (tree[v].s[3] + 3*add%mod*tree[v].s[2]%mod)%mod; tree[v].s[3] = (tree[v].s[3] + len*add%mod*add%mod*add%mod)%mod; tree[v].s[2] = (tree[v].s[2] + 2*add%mod*tree[v].s[1]%mod)%mod; tree[v].s[2] = (tree[v].s[2] + len*add%mod*add%mod)%mod; tree[v].s[1] = (tree[v].s[1] + len*add%mod)%mod; tree[v].add = (tree[v].add + add)%mod; } void push_down(int v) { if(tree[v].l == tree[v].r) return; cal(v*2,tree[v].mult,tree[v].add); cal(v*2+1,tree[v].mult,tree[v].add); tree[v].mult = 1; tree[v].add = 0; } void push_up(int v) { int ls = v*2,rs = v*2+1; tree[v].s[1] = (tree[ls].s[1] + tree[rs].s[1])%mod; tree[v].s[2] = (tree[ls].s[2] + tree[rs].s[2])%mod; tree[v].s[3] = (tree[ls].s[3] + tree[rs].s[3])%mod; } void update(int v, int l, int r, int mult, int add) { if(tree[v].l == l && tree[v].r == r) { cal(v,mult,add); return; } push_down(v); int mid = (tree[v].l + tree[v].r) >> 1; if(r <= mid) update(v*2,l,r,mult,add); else if(l > mid) update(v*2+1,l,r,mult,add); else { update(v*2,l,mid,mult,add); update(v*2+1,mid+1,r,mult,add); } push_up(v); } int query(int v, int l, int r,int p) { if(tree[v].l == l && tree[v].r == r) { return tree[v].s[p]; } push_down(v); int mid = (tree[v].l + tree[v].r) >> 1; if(r <= mid) return query(v*2,l,r,p); else if(l > mid) return query(v*2+1,l,r,p); else return (query(v*2,l,mid,p) + query(v*2+1,mid+1,r,p))%mod; } int main() { int n,m; int op,x,y,c; while(~scanf(%d %d,&n,&m)) { if(n == 0 && m == 0) break; build(1,1,n); while(m--) { scanf(%d %d %d %d,&op,&x,&y,&c); if(op == 1) update(1,x,y,1,c); else if(op == 2) update(1,x,y,c,0); else if(op == 3) update(1,x,y,0,c); else printf(%d ,query(1,x,y,c)%mod); } } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：Codeforces Round #262 (Div. 2) ..	下一篇：hdu3472 HS BDC --- 混合图欧拉回..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: