Loading...

洛谷P1558 色板游戏

check评论:0 条 remove_red_eye浏览量:398 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-08-04

分块裸题,直接分块即可,因为颜色数目很少,查询用桶装一下就好

#include <bits/stdc++.h>
using namespace std;
int n,t,m,block;
int belong[100010],a[100010];
int color[400][31];
int biaoji[400];
void update(int blockn)
{
    memset(color[blockn],0,sizeof(color[blockn]));
    if(biaoji[blockn]!=0)
    {
        for(int i=(blockn-1)*block+1;i<=blockn*block;i++)
        {
            a[i]=biaoji[blockn];
        } 
        biaoji[blockn]=0;
    }
    for(int i=(blockn-1)*block+1;i<=blockn*block;i++)
    {
        color[blockn][a[i]]=1;
    }
}
void paint(int l,int r,int x)
{
    if(belong[l]==belong[r])
    {
        update(belong[l]);
        for(int i=l;i<=r;i++)
        {
            a[i]=x;
        } 
        update(belong[l]);
    }
    else
    {
        update(belong[l]);
        for(int i=l;i<=belong[l]*block;i++)
        {
            a[i]=x;
        }
        update(belong[l]);
        update(belong[r]);
        for(int i=(belong[r]-1)*block+1;i<=r;i++)
        {
            a[i]=x;
        }
        update(belong[r]);
        for(int i=belong[l]+1;i<belong[r];i++)
        {
            biaoji[i]=x;
        }
    }
}
int query(int l,int r)
{
    int ans=0;
    bool h[40];
    memset(h,0,sizeof(h));
    if(belong[l]==belong[r])
    {
        update(belong[l]);
        for(int i=l;i<=r;i++)
        {
            if(!h[a[i]])
            {
                h[a[i]]=1;
            }
        }
    }
    else
    {
        update(belong[l]);
        for(int i=l;i<=belong[l]*block;i++)
        {
            if(!h[a[i]])
            {
                h[a[i]]=1;
            }
        }
        update(belong[r]);
        for(int i=(belong[r]-1)*block+1;i<=r;i++)
        {
            if(!h[a[i]])
            {
                h[a[i]]=1;
                ans++;
            }
        }
        for(int i=belong[l]+1;i<belong[r];i++)
        {
            if(!biaoji[i])
            {
                for(int j=1;j<=t;j++)
                {
                    if(color[i][j]&&!h[j])
                    {
                        h[j]=1;
                    }
                }
            }
            else
            {
                if(!h[biaoji[i]])
                {
                    h[biaoji[i]]=1;
                }
            }
        }
    }
    ans=0;
    for(int i=1;i<=t;i++)
    {
        if(h[i])
        {
            ans++;
        }
    }
    return ans;
}
int main()
{
    cin>>n>>t>>m;
    block=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        belong[i]=(i-1)/block+1;
        color[belong[i]][1]=1;
        a[i]=1;
    } 
    char opt[4];
    for(int i=1;i<=m;i++)
    {
        int l,r,x;
        scanf("%s",opt);
        if(opt[0]=='C')
        {
            scanf("%d%d%d",&l,&r,&x);
            if(l>r)
            {
                swap(l,r);
            } 
            paint(l,r,x);
        }
        else
        {
            scanf("%d%d",&l,&r);
            if(l>r)
            {
                swap(l,r);
            } 
            printf("%d\n",query(l,r));
        }
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名