セグメントツリー(二):セグメント更新

POJ 2777

/*

          ，          



                ，          



      ：C >> <<    + -  ，x << 1 + 1   x * 2 + 1   ，      

     (x << 1) + 1,            。



           。      ……



    2011-07-29 07:59

*/







#include <stdio.h>



#define MAXN 1000000



struct node

{

    int l, r, c;

}t[MAXN];



int c[32];



void build(int l, int r, int x)

{

    t[x].l = l;

    t[x].r = r;

    t[x].c = 1;

    if (l == r)

        return;

    int m = (l + r) >> 1;

    build(l, m, x << 1);

    build(m + 1, r, (x << 1) + 1);

}





void update(int l, int r, int c, int x)

{

    if ((l == t[x].l) && (r == t[x].r))

        return t[x].c = c;

   // else if (t[x].l < t[x].r)

    {

        int m  = (t[x].l + t[x].r)  >> 1;

        if (t[x].c >= 1)

        {

            t[x << 1].c = t[(x << 1) + 1].c = t[x].c;

            t[x].c = -1;

        }

        if (r <= m)

            update(l, r, c, x << 1);

        else if (l > m)

            update(l, r, c, (x << 1) + 1);

        else

        {

            update(l, m, c, (x << 1));

            update(m + 1, r, c, (x << 1) + 1);

        }

    }

}



void query(int l, int r, int x)

{

    if (t[x].c > 0)

        return c[t[x].c] = 1;

//    else if (t[x].c == -1 && t[x].l < t[x].r)

    {

        int m = (t[x].l + t[x].r) >> 1;

        if (r <= m)

            query(l, r, x << 1);

        else if (l > m)

            query(l, r, (x << 1) + 1);

        else

        {

            query(l, m, x << 1);

            query(m + 1, r, (x << 1) + 1);

        }

    }

}



int count()

{

    int i, sum = 0;

    for(i = 1; i <= 30; i++)

        sum += c[i];

    return sum;

}



void swap(int *a, int *b)

{

    int temp = *a;

    *a = *b;

    *b = temp;

}



int main()

{

    int n, t, o;

    while (scanf("%d%d%d", &n, &t, &o) == 3)

    {

        build(1, n, 1);

        while (o--)

        {

            char ch[2];

            scanf("%s", &ch);

            if (ch[0] == 'C')

            {

                int a, b, c;

                scanf("%d%d%d", &a, &b, &c);

                if (a > b)

                    swap(&a, &b);

                update(a, b, c, 1);

            }

            else

            {

                int a, b;

                scanf("%d%d", &a, &b);

                if (a > b)

                    swap(&a, &b);

                memset(c, 0, sizeof(c));

                query(a, b, 1);

                printf("%d
", count());

            }

        }

    }

    return 0;

}

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }
 
HDU 1698

/*

  ：   n    1   ，  m     [x..y]    1，2 3   ，         



  ：    ，    ，     。



  ：   C     G++    。Debug  ，                        ，            ，      

*/





#include <stdio.h>

#define MAXN 400000

#define ROOT 1





struct

{

    int left,right,cover;

}t[MAXN];

//cover            ，  -1    

void build(int p, int left, int right)

{

    t[p].left = left;

    t[p].right = right;

    t[p].cover = 1;

    if (left == right)

        return;

    int m = (left + right) / 2;

    build(p*2, left, m);

    build(p*2+1, m+1, right);

}//  ，      1   





void change(int p, int left , int right, int color)

{

    if ((t[p].left >= left) && (t[p].right <= right))

    {

        t[p].cover = color;

        return;

    }//                 cover    

    if (t[p].cover != -1)

    {

        t[p*2].cover = t[p*2+1].cover = t[p].cover;

        t[p].cover = -1;

    }//                ，       ，cover  -1，                 ，           

    int m = (t[p].left + t[p].right) / 2;

    if (left <= m)

        change(p*2, left, right, color);

    if (right > m )

        change(p*2+1, left, right, color);

    //      ，             ，           ，                  ，              。         ，        ，     ，    。

}



int count(int p, int left, int right)

{

    int m = (t[p].left + t[p].right) / 2;

    if (t[p].left == left && t[p].right == right)

    {

        if (t[p].cover != -1)

            return t[p].cover * (t[p].right - t[p].left + 1);

        else return count(p*2, left, m) + count(p*2+1, m+1, right);

    }//  ，                    

   if (m >= right)

        return count(p*2, left, m);

    else if (m < left)

        return count(p*2+1, m+1, right);

    else return count(p*2, left, m) + count(p*2+1, m+1, right);

    //              

}

//              ，  count         ，     





int main()

{

    int i,j,k,m,n,t,x,y,z;

    scanf("%d", &t);

    for (k = 1; k <= t; k++)

    {

        scanf("%d%d", &n, &m);

        build(ROOT, 1, n);

        for (i = 1; i <= m; i++)

        {

            scanf("%d%d%d", &x, &y, &z);

            change(ROOT, x, y, z);

        }

           printf("Case %d: The total value of the hook is %d.
",k,count(1,1,n));

    }//      .

    return 0;

}

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }