HDU 4391 Paint the Wall (블록 체인 리스트 | 세그먼트 해시)

제목 링크: 여 기 를 클릭 ~ ~
제목:
n 개의 점 이 있 습 니 다. 각 점 마다 하나의 색 (같 을 수 있 습 니 다) 이 있 습 니 다. 두 가지 조작: 1. 구간 [a, b] 을 색 c 로 염색 합 니 다.2. 구간 [a, b] 에서 색상 이 c 인 점 이 몇 개 있 는 지 물 어 봅 니 다.
문제 풀이 방향:
색상 의 종류 (5 개 이내) 가 적 으 면 클래식 한 선분 수 구간 염색 의 입문 문제 다.
그러나 이 문 제 는 색깔 이 너무 많아 하 쉬 를 진행 할 수 있 지만 규 모 는 10 ^ 5 에 달 할 수 있어 소박 하 게 선분 수 로 는 이 루어 질 수 없다.
근 데 다 들 선분 트 리 에 최적화 한 게 많아 요.(유지 구간 색상 종류의 최소 값 과 최대 값 을 조회 할 때 최적화 할 수 있 습 니 다)
그러나 믿 을 만 한 사 고 는 블록 체인 시트 로 문 제 를 세그먼트 하 쉬 라 고 한다.
사고방식: 각 블록 마다 맵 < color, cnt > 를 유지 합 니 다.
그 다음 에 업데이트 작업 에서 건 너 간 블록 에 대해 해당 하 는 map 를 비우 고 새로운 색상 을 추가 합 니 다. 길 이 는 Block 입 니 다.len, 대응 하 는 단일 색상 을 업데이트 하지 않 아 도 됩 니 다.
양 끝 이 한 덩어리 도 안 되 는 부분 에 대해 서 는 다양한 색상 이 나 올 수 있 으 므 로 한 점 의 색상 을 폭력 적 으로 업데이트 해 야 한다.
사실은 전체적인 사상 은 전체적인 색채 가 유일한 것 이 아니 라 한 점 의 가치 가 진실 치 에 대응 해 야 한 다 는 것 이다.이렇게 하면 어떤 블록 을 업데이트 할 때 O (1) 임 을 보증 할 수 있다.못 알 아 보 겠 으 면 코드 를 보 세 요...
처음에는 시간 을 초과 할 까 봐 맵 으로 이 루어 지지 못 했 지만 나중에 맵 을 대담 하 게 사용 하 라 는 말 을 듣 고 하 나 를 썼 습 니 다. 마침내 2 시간 동안 바 뀌 었 습 니 다. 마지막 블록 을 수정 할 때 아래 표 시 는 n 을 초과 하지 않도록 주의 하 세 요.

#include <map>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <algorithm>

using namespace std;

#define size(v) (int)v.size()

const int N = 1e5 + 5;

int n,color,a[N],block_len;

map<int,int> blocks_colors[333];

void bf_update(int l,int r)
{
    int block_id = l / block_len;
    if(size(blocks_colors[block_id]) == 1)
    {
        map<int,int>::iterator it = blocks_colors[block_id].begin();
        int old_color = it->first;
        int old_cnt   = it->second;
        if(color == old_color)
            return ;
        if(r - l + 1 == old_cnt)
        {
            blocks_colors[block_id][color] = r - l + 1;
            blocks_colors[block_id].erase(it);
            return ;
        }
        for(int i=block_len*block_id;i<n && i<block_len*(block_id+1);i++)
        {
            if(i >= l && i <= r)
                a[i] = color;
            else
                a[i] = old_color;
        }
        blocks_colors[block_id][color] = r - l + 1;
        blocks_colors[block_id][old_color] = old_cnt - (r - l + 1);
    }
    else
    {
        for(int i=l;i<=r;i++)
        {
            if(a[i] == color)
                continue;
            map<int,int>::iterator it = blocks_colors[block_id].find(a[i]);
            if(it->second == 1)
                blocks_colors[block_id].erase(it);
            else
                it->second--;
            blocks_colors[block_id][color]++;
            a[i] = color;
        }
    }
}

int bf_query(int l,int r)
{
    int block_id = l / block_len;
    if(blocks_colors[block_id].count(color))
    {
        if(size(blocks_colors[block_id]) == 1)
            return r - l + 1;
        else
        {
            int ret = 0;
            for(int i=l;i<=r;i++)
                if(a[i] == color)
                    ++ret;
            return ret;
        }
    }
    else
        return 0;
}

void update(int l,int r)
{
    int block_id1 = l / block_len;
    int block_id2 = r / block_len;
    if(block_id1 == block_id2)
    {
        bf_update(l,r);
        return ;
    }
    int rr = block_len * (block_id1 + 1) - 1;
    int ll = block_len * block_id2;
    bf_update(l,rr);
    bf_update(ll,r);
    for(int id=block_id1+1;id<block_id2;id++)
    {
        blocks_colors[id].clear();
        blocks_colors[id][color] = block_len;
    }
}

int query(int l,int r)
{
    int block_id1 = l / block_len;
    int block_id2 = r / block_len;
    if(block_id1 == block_id2)
        return bf_query(l,r);
    int rr = block_len * (block_id1 + 1) - 1;
    int ll = block_len * block_id2;
    int ret = bf_query(l,rr) + bf_query(ll,r);
    for(int id=block_id1+1;id<block_id2;id++)
        if(blocks_colors[id].count(color))
            ret += blocks_colors[id][color];
    return ret;
}

void debug(int n,int max_id)
{
    printf("color of a[]: ");
    for(int i=0;i<n;i++)
        printf("%d ",a[i]);
    puts("***");
    for(int i=0;i<=max_id;i++)
    {
        printf("the %dth block[%d,%d]=>
",i,i*block_len,(i+1)*block_len-1);
        for(map<int,int>::iterator it=blocks_colors[i].begin();it!=blocks_colors[i].end();it++)
            printf("\t\t\t %d -> %d
",it->first,it->second);
        puts("");
    }
}

int main()
{
    //freopen("in.ads","r",stdin);
    int m;
    while(~scanf("%d%d",&n,&m))
    {
        block_len = (int)sqrt(n * 1.0);
        //block_len = 400;
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        int block_id_max = n / block_len;
        for(int i=0;i<=block_id_max;i++)
            blocks_colors[i].clear();
        for(int i=0;i<n;i++)
        {
            int block_id = i / block_len;
            blocks_colors[block_id][ a[i] ]++;
        }
        int op,l,r;
        while(m--)
        {
            scanf("%d%d%d%d",&op,&l,&r,&color);
            if(op == 1)
                update(l,r);
            else
                printf("%d
",query(l,r));
        }
    }
    return 0;
}