hdu 1698(線分樹)

7934 ワード
線分樹 hdoj
テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1698
Just a Hook
Time Limit:4000/2000 MS(Java/Others)    メモリLimit:32768/32768 K(Java/Others)Total Submission(s):39519    Acceepted Submission(s):19156
Problem Description
In the game of DotA、Pudge’s meat hook is actually the most horrible for most of the hersoes.The hook is made up of several consecutive metallic sticks which are of the same length.

Now Pudge wants to do some operation on on the hook.
Let us number the consecutive metallic sticks of the hook from 1 to N.For each operation,Pudge can change the consecuve metallic sticks,numbed from X to Y,into cupreous sticks,silver stics.
The total value of the hool is calculated as the sum of values of N metallic sticks.More precisely,the value for each kind of stick is carred as follows:
For each cupreous stick、the value is 1.
For each silver stick,the value is 2.
For each golden stick、the value is 3.
Pudge wants to know the total value of the hook after performing the operation.
Yu may consider the original Hook is made up of cupreous sticks.
 
Input
The input consists of several test cases.The first line of the input is the number of the cases.The re no more than 10 cases.
For each case,the first line contains an integer N,1<=N==100,000,which is the number of the sticks of Pudge’s meatok and the second line cond an integer Q,0==Q==100,000,which the moris.Oris.
Next Q lines、each line contains three integers X、Y、1<=X====N、Z、1<=Z、=3、which defines an operation:change the metal kind Z、where Z=1 present、3
 
Output
For each case,print a number in a line representing the total value of the hook after the operations.Use the format in the example.
 
Sample Input
 
   

     1 10 2 1 5 2 5 9 3
 

Sample Output 
 
   

     Case 1: The total value of the hook is 24.


思路：一道线段树区间更新上午板子题，主要是测试一下板子好不好使~

#include   
#include   
#include   
#include   
#include   
#define MAXN 100010  
#define inf 0x3f3f3f3f  
  
using namespace std;  
  
struct node{  
    int l,r;//  [l,r]  
    int add;//         
    int sum;//     
    int mx; //       
    int mn; //       
}tree[MAXN<<2];//     4       
int cnt=0;
void pushup(int index){  
    tree[index].sum = tree[index<<1].sum+tree[index<<1|1].sum;  
    tree[index].mx = max(tree[index<<1].mx,tree[index<<1|1].mx);  
    tree[index].mn = min(tree[index<<1].mn,tree[index<<1|1].mn);  
}  
void pushdown(int index){  
    //            
    //             ，                  
    if(tree[index].add){  
        //        
        
        tree[index<<1].sum = (tree[index<<1].r-tree[index<<1].l+1)*tree[index].add; 
        tree[index<<1|1].sum = (tree[index<<1|1].r-tree[index<<1|1].l+1)*tree[index].add; 
        tree[index<<1].mx = tree[index].add; 
        tree[index<<1|1].mx = tree[index].add; 
        tree[index<<1].mn = tree[index].add; 
        tree[index<<1|1].mn = tree[index].add; 
        tree[index<<1].add = tree[index].add; 
        tree[index<<1|1].add = tree[index].add; 
        tree[index].add = 0;
        
        //           val  
          
//        tree[index<<1].sum += (tree[index<<1].r-tree[index<<1].l+1)*tree[index].add;  
//        tree[index<<1|1].sum +=(tree[index<<1|1].r-tree[index<<1|1].l+1)*tree[index].add;  
//        tree[index<<1].mx += tree[index].add;  
//        tree[index<<1|1].mx += tree[index].add;  
//        tree[index<<1].mn += tree[index].add;  
//        tree[index<<1|1].mn += tree[index].add;  
//        tree[index<<1].add += tree[index].add;  
//        tree[index<<1|1].add += tree[index].add;  
//        tree[index].add = 0;  
  
    }  
}  
void build(int l,int r,int index){  
    tree[index].l = l;  
    tree[index].r = r;  
    tree[index].add = 0;//       0  
    if(l == r){  
        tree[index].sum=1;  
        tree[index].mn = tree[index].mx = tree[index].sum;  
        return ;  
    }  
    int mid = (l+r)>>1;  
    build(l,mid,index<<1);  
    build(mid+1,r,index<<1|1);  
    pushup(index);  
}  
void updata(int l,int r,int index,int val){  
    if(l <= tree[index].l && r >= tree[index].r){  
        //        val,      tree[index].r-tree[index].l+1 
       //   ，            ： 
        tree[index].sum = (tree[index].r-tree[index].l+1)*val; 
        tree[index].mn = val; 
        tree[index].mx = val; 
        tree[index].add = val;
        //           val,      tree[index].r-tree[index].l+1  
        //  ，            ：  
//        tree[index].sum += (tree[index].r-tree[index].l+1)*val;  
//        tree[index].mn += val;  
//        tree[index].mx += val;  
//        tree[index].add += val;//      
  
        return ;  
    }  
    pushdown(index);  
    int mid = (tree[index].l+tree[index].r)>>1;  
    if(l <= mid){  
        updata(l,r,index<<1,val);  
    }  
    if(r > mid){  
        updata(l,r,index<<1|1,val);  
    }  
    pushup(index);  
}  
int query(int l,int r,int index){  
    if(l <= tree[index].l && r >= tree[index].r){  
        return tree[index].sum;  
        //return tree[index].mx;  
        //return tree[index].mn;  
    }  
    pushdown(index);  
    int mid = (tree[index].l+tree[index].r)>>1;  
    int ans = 0;  
    int Max = 0;  
    int Min = inf;  
    if(l <= mid){  
        ans += query(l,r,index<<1);  
        Max = max(query(l,r,index<<1),Max);  
        Min = min(query(l,r,index<<1),Min);  
    }  
    if(r > mid){  
        ans += query(l,r,index<<1|1);  
        Max = max(query(l,r,index<<1|1),Max);  
        Min = min(query(l,r,index<<1|1),Min);  
    }  
    return ans;  
    //return Max;  
    //return Min;  
}  
int main()  
{  
    int n,m,t,t1,t2,t3;
	scanf("%d",&t);  
    while(t--)
	{
	    cnt++;
		scanf("%d",&n);
	    scanf("%d",&m);
        build(1,n,1);
		updata(1,n,1,1);  
        while(m--)
		{  
            scanf("%d%d%d",&t1,&t2,&t3);  
            updata(t1,t2,1,t3);
        }
		printf("Case %d: The total value of the hook is %d.
",cnt,query(1,n,1));  
    }  
    return 0;  
}
UbuntuインストールPythonマシン学習パッケージ
phoenixを使ってhbase(四)を操作します.