// http://acm.pku.edu.cn/JudgeOnline/problem?id=2777
#include "stdio.h"

#define MAX 100000

struct node
{
    long l;
    long r;
    unsigned c;
    long b;           // 标识是否是单色
}xdtree[MAX * 3];

// xdtree_leaf_size = 2^(n - 1) = 131072 > 100000
//                n = 18
// xdtree_size = 2^n - 1 =  262143;

long   L, T, O;

long calc(unsigned c)
{
    long i, diff;

    for(i = 0, diff = 0; i < T; i++)
    {
        if ((1 << i) & c)
            diff++;
    }
    return diff;
}


void build_tree(long n, long l, long r)
{
    long m;
    
    xdtree[n].l  = l;
    xdtree[n].r  = r;
    xdtree[n].c  = 1;
    xdtree[n].b  = 1;

    if (r == l)
        return;

    m = (r + l) >> 1;

    build_tree(2 * n + 1, l, m);
    build_tree(2 * n + 2, m + 1, r);
}

unsigned insert(long i, long l, long r, unsigned c)
{
    long m;
    unsigned lc, rc;
 
    if (xdtree[i].l == l && xdtree[i].r == r)
    {
        xdtree[i].c = c;
        xdtree[i].b = 1;
        return c;
    }

    m = (xdtree[i].l + xdtree[i].r) >> 1;
    
    if (m >= r)
    {
        lc = insert(2 * i + 1, l, r, c);
        rc = xdtree[i].b ? insert(2 * i + 2, m + 1, xdtree[i].r, xdtree[i].c) : xdtree[2 * i + 2].c;
    }
    else if (m + 1 <= l)
    {

        lc = xdtree[i].b ? insert(2 * i + 1, xdtree[i].l, m, xdtree[i].c) : xdtree[2 * i + 1].c;
        rc = insert(2 * i + 2, l, r, c);
    }
    else
    {
        if (xdtree[i].b)
        {
            insert(2 * i + 1, xdtree[i].l, m, xdtree[i].c);
            insert(2 * i + 2, m + 1, xdtree[i].r, xdtree[i].c);
        }
        lc = insert(2 * i + 1, l, m, c);
        rc = insert(2 * i + 2, m + 1, r, c);
    }
    xdtree[i].c = lc | rc;
    xdtree[i].b = calc(xdtree[i].c) == 1 ? 1 : 0;
    return xdtree[i].c;
}

unsigned find(long i, long l, long r)
{
    long m;
    
    if (xdtree[i].b)
    {
        return xdtree[i].c;
    }

    if (xdtree[i].l == l && xdtree[i].r == r)
    {
        return xdtree[i].c;
    }

    m = (xdtree[i].l + xdtree[i].r) >> 1;
    
    if (m >= r)
    {
        return find(2 * i + 1, l, r);
    }
    else if (m  + 1 <= l)
    {
        return find(2 * i + 2, l, r);
    }
    else
    {
        return find(2 * i + 1, l, m) | find(2 * i + 2, m + 1, r);
    }
}

void main()
{
    char  f[4];
    long   A, B, C;
    unsigned color;

    scanf("%d %d %d", &L, &T, &O);
    
    build_tree(0, 1, L);    
    
    while (O--)
    {
        scanf("%s", f);
        if ('C' == f[0])
        {
            scanf("%d %d %d", &A, &B, &C);
            A < B ? insert(0, A, B, 1 << (C - 1)) : insert(0, B, A, 1 << (C - 1));
        }
        else
        {
            scanf("%d %d", &A, &B);
            color = A < B ? find(0, A, B) : find(0, B, A);
            printf("%d\n", calc(color));
        }        
    }
}

• Re:WA了很多次，仔细找了好久都没有发现错误。请各位大牛帮忙看看！ (51) Lenus 2010-08-21 00:45:14