题解 P1558 【色板游戏】

其实这道题分块也可以水过

将色板分成 $\sqrt(N)$ 块,块内维护是否被标记和涂有几种颜色

每次更新和查询时整块直接查询,块内暴力查询,复杂度 $M\sqrt(N) \T$

#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
using namespace std;

struct block
{
    int l;
    int r;
    int v;
    bool c[40];
};

const int MAXN = 1e5 + 100;
int n, m, T, size;
int a[MAXN], g[MAXN];
block b[500];

void update(int p)
{
    int l = b[p].l, r = b[p].r;    
    memset(b[p].c, 0, sizeof b[p].c);
    if (b[p].v != 0)
    {
        for (int i = l; i < r + 1; ++i)
            a[i] = b[p].v;
        b[p].v = 0;
    }
    for (int i = l; i < r + 1; ++i)
        b[p].c[a[i]] = true;
    return;
}

void paint(int l, int r, int x)
{
    int beg = g[l], end = g[r];
    if (beg == end)
    {
        update(beg);
        for (int i = l; i < r + 1; ++i)
            a[i] = x;
        update(beg);
    }
    else
    {
        update(beg);
        for (int i = l; i < beg * size + 1; ++i)
            a[i] = x;        
        update(beg);
        update(end);
        for (int i = (end - 1) * size + 1; i < r + 1; ++i)
            a[i] = x;
        update(end);
        for (int i = beg + 1; i < end; ++i)
            b[i].v = x;

    }
    return;
}

int query(int l, int r)
{
    int beg = g[l], end = g[r], ret = 0;
    bool h[40];
    memset(h, 0, sizeof h);
    if (beg == end)
    {
        update(beg);
        for (int i = l; i < r + 1; ++i)
        {
            if (!h[a[i]])
                h[a[i]] = true;
        }
    }
    else
    {
        update(beg);
        for (int i = l; i < beg * size + 1; ++i)
        {
            if (!h[a[i]])
                h[a[i]] = true;
        }
        update(end);
        for (int i = (end - 1) * size + 1; i < r + 1; ++i)
        {
            if (!h[a[i]])
                h[a[i]] = true;
                ++ret;
        }
        for (int i = beg + 1; i < end; ++i)
        {
            if (b[i].v == 0)
            {
                for (int j = 1; j < T + 1; ++j)
                {
                    if (b[i].c[j] && !h[j])
                        h[j] = true;
                }
            }
            else if (!h[b[i].v])
                h[b[i].v] = true;
        }
    }
    ret = 0;
    for (int i = 1; i < T + 1; ++i)
    {
        if (h[i])
            ++ret;
    }
    return ret;
}

inline int read()
{
    char ch = getchar();
    while (ch < '0' || ch > '9')
        ch = getchar();
    int x = 0;
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}

int main()
{
    n = read();
    T = read();
    m = read();
    size = sqrt(n) + 1;
    for (int i = 1; i < n + 1; ++i)
    {
        a[i] = 1;
        g[i] = (i - 1) / size + 1;
    }
    for (int i = 1; i < size + 1; ++i)
    {
        b[i].v = 0;
        b[i].c[1] = true; 
        b[i].l = (i - 1) * size + 1;
        b[i].r = i * size;
    }
    for (int i = 0; i < m; ++i)
    {
        char ch = getchar();
        while (ch != 'C' && ch != 'P')
            ch = getchar();
        if (ch == 'C')
        {
            int l = read(), r = read(), x = read();
            if (l > r)
                swap(l, r);
            paint(l, r, x);
        }
        else if (ch == 'P')
        {
            int l = read(), r = read();
            if (l > r)
                swap(l, r);
            printf("%d\n", query(l, r));
        }
    }
    return 0;
}

发表于 2017-11-28 21:21:47 in 题解