# 加载中...

• 博客等级：
• 博客积分：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

• 评论加载中，请稍候...

发评论

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

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

新浪公司 版权所有