加载中…
个人资料
鈞少
鈞少
  • 博客等级:
  • 博客积分:0
  • 博客访问:32,758
  • 关注人气:17
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

HDU  4578  Transformation (线段树)

(2013-08-10 17:06:13)
靠  对不起   遗憾题   杭州现场赛没过 导致差两名没拿到名额 唉


#include 
#include 
#include 

using namespace std;

#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define mod 10007

typedef struct 
{
    int l , r ; 
       int val;
    int a1 , a2 , a3;
   int col;
    int sum1,sum2,sum3;
 int len(){return (r - l + 1 );}
     int midt(){return (r + l)>>1;}
   
}element;

element tree_sg[101000<<2];

void pushdown(int idx)//懒惰标记 
{
        if(tree_sg[idx].col != -1)
  {
           tree_sg[LL(idx)].l = tree_sg[idx].l , tree_sg[LL(idx)].r = tree_sg[idx].midt();
             tree_sg[RR(idx)].l = tree_sg[idx].midt()+1 , tree_sg[RR(idx)].r = tree_sg[idx].r;
           tree_sg[LL(idx)].val = tree_sg[RR(idx)].val = tree_sg[idx].val;
          
           tree_sg[LL(idx)].a1 = tree_sg[RR(idx)].a1 = tree_sg[idx].a1 ;
               tree_sg[LL(idx)].a2 = tree_sg[RR(idx)].a2 = tree_sg[idx].a2 ;
               tree_sg[LL(idx)].a3 = tree_sg[RR(idx)].a3 = tree_sg[idx].a3 ;
            
           tree_sg[LL(idx)].sum1 = (tree_sg[LL(idx)].a1 * tree_sg[LL(idx)].len()%mod)%mod;
             tree_sg[LL(idx)].sum2 = (tree_sg[LL(idx)].a2 * tree_sg[LL(idx)].len()%mod)%mod;
             tree_sg[LL(idx)].sum3 = (tree_sg[LL(idx)].a3 * tree_sg[LL(idx)].len()%mod)%mod;
             tree_sg[RR(idx)].sum1 = (tree_sg[RR(idx)].a1 * tree_sg[RR(idx)].len()%mod)%mod;
             tree_sg[RR(idx)].sum2 = (tree_sg[RR(idx)].a2 * tree_sg[RR(idx)].len()%mod)%mod;
             tree_sg[RR(idx)].sum3 = (tree_sg[RR(idx)].a3 * tree_sg[RR(idx)].len()%mod)%mod;
          
                
           tree_sg[LL(idx)].col = tree_sg[RR(idx)].col = tree_sg[idx].col;
             tree_sg[idx].col = -1;
           
   }
}

void pushup(int idx)
{
 tree_sg[idx].sum1 = (tree_sg[LL(idx)].sum1%mod + tree_sg[RR(idx)].sum1%mod)%mod;
    tree_sg[idx].sum2 = (tree_sg[LL(idx)].sum2%mod + tree_sg[RR(idx)].sum2%mod)%mod;
    tree_sg[idx].sum3 = (tree_sg[LL(idx)].sum3%mod + tree_sg[RR(idx)].sum3%mod)%mod;
 
}

void change(int l , int r , int L , int R , int c , int idx)
{
 tree_sg[idx].l = L , tree_sg[idx].r = R;
 
   if(l <= L && R <= r )
       {
           tree_sg[idx].col = 0;
               tree_sg[idx].val = c;
               tree_sg[idx].val %= mod;
        tree_sg[idx].a1 = (tree_sg[idx].val)%mod;
           tree_sg[idx].a2 = (tree_sg[idx].val%mod * tree_sg[idx].val%mod )%mod;
               tree_sg[idx].a3 = (tree_sg[idx].val%mod * tree_sg[idx].val%mod * tree_sg[idx].val%mod )%mod;
             
           tree_sg[idx].sum1 = (tree_sg[idx].a1%mod * tree_sg[idx].len()%mod)%mod;
             tree_sg[idx].sum2 = (tree_sg[idx].a2%mod * tree_sg[idx].len()%mod)%mod;
             tree_sg[idx].sum3 = (tree_sg[idx].a3%mod * tree_sg[idx].len()%mod)%mod;
          
           return;
     }
        
  int mid = (L + R)>>1;
      
   pushdown(idx);
   
   if(l <= mid )change(l ,r , L , mid , c , LL(idx));
  if(mid < r )change(l ,r , mid + 1 , R , c , RR(idx));
    
   pushup(idx);        
}

void add(int l , int r , int L , int R , int c , int idx)
{
     if(l <= L && R <= r  && tree_sg[idx].col != -1)
    {
           //tree_sg[idx].col = 0;
             tree_sg[idx].val += c;
              tree_sg[idx].val %= mod;
        tree_sg[idx].a1 = (tree_sg[idx].val)%mod;
           tree_sg[idx].a2 = (tree_sg[idx].val%mod * tree_sg[idx].val%mod )%mod;
               tree_sg[idx].a3 = (tree_sg[idx].val%mod * tree_sg[idx].val%mod * tree_sg[idx].val%mod )%mod;
             
           tree_sg[idx].sum1 = (tree_sg[idx].a1%mod * tree_sg[idx].len()%mod)%mod;
             tree_sg[idx].sum2 = (tree_sg[idx].a2%mod * tree_sg[idx].len()%mod)%mod;
             tree_sg[idx].sum3 = (tree_sg[idx].a3%mod * tree_sg[idx].len()%mod)%mod;
          
           return;
     }
        
   int mid = (L + R)>>1;
      
   pushdown(idx);
   
   if(l <= mid )add(l ,r , L , mid , c , LL(idx));
     if(mid < r )add(l ,r , mid + 1 , R , c , RR(idx));
       
   pushup(idx);        
 
}

void Mul(int l , int r , int L , int R , int c , int idx)
{
    if(l <= L && R <= r && tree_sg[idx].col != -1)
      {
           //tree_sg[idx].col = 0;
             tree_sg[idx].val *= c;
              tree_sg[idx].val %= mod;
        tree_sg[idx].a1 = (tree_sg[idx].val)%mod;
           tree_sg[idx].a2 = (tree_sg[idx].val%mod * tree_sg[idx].val%mod )%mod;
               tree_sg[idx].a3 = (tree_sg[idx].val%mod * tree_sg[idx].val%mod * tree_sg[idx].val%mod )%mod;
             
           tree_sg[idx].sum1 = (tree_sg[idx].a1%mod * tree_sg[idx].len()%mod)%mod;
             tree_sg[idx].sum2 = (tree_sg[idx].a2%mod * tree_sg[idx].len()%mod)%mod;
             tree_sg[idx].sum3 = (tree_sg[idx].a3%mod * tree_sg[idx].len()%mod)%mod;
          
           return;
     }
        
   int mid = (L + R)>>1;
      
   pushdown(idx);
   
   if(l <= mid )Mul(l ,r , L , mid , c , LL(idx));
     if(mid < r )Mul(l ,r , mid + 1 , R , c , RR(idx));
       
   pushup(idx);        
 
}

int query(int l,int r, int L, int R , int p , int idx)
{
       if(l <= L && R <= r && tree_sg[idx].col != -1 )
     {
           if(p == 1)
                  return tree_sg[idx].sum1;
           if(p == 2)
                  return tree_sg[idx].sum2;
           if(p == 3)
                  return tree_sg[idx].sum3;
   }
        
   int mid = (L + R)>>1;
    
   pushdown(idx);
   
   if(r <= mid )return query(l ,r , L , mid , p , LL(idx));
    else if(l > mid )return query(l ,r , mid+1 , R , p , RR(idx));
      else return (  query(l ,r , L , mid , p , LL(idx) ) + query(l ,r , mid+1 , R , p , RR(idx) ) )%mod;
     
        
}

int main()
{
   int  n , m ; 
  
   while(~scanf("%d%d",&n,&m),n|m)
     {
           int k,x,y,c;
             
           change(1 , n , 1 , n , 0 , 1);//初始为0 
           
           while(m--)
          {
                   scanf("%d%d%d%d",&k,&x,&y,&c);      
                    if( k == 1 )
                                add(x , y , 1 , n , c , 1);
                 if( k == 2 )
                                Mul(x , y , 1 , n , c , 1);
                 if( k == 3)
                         change(x , y , 1 , n , c , 1);
                      if( k == 4)
                         printf("%d\n", query(x , y , 1 , n , c , 1) );
              }
                
                
                
   }
        

       return 0;
}


0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有