转载请注明：http://blog.csdn.net/jiangshibiao/article/details/23990489

【原题】

2120: 数颜色

Time Limit: 6 Sec  Memory Limit: 259 MB

Submit: 1201  Solved: 429

[

id=2120" style="color:blue; text-decoration:none">Submit][Status]

Description

Input

Output

Sample Input

Sample Output

HINT

【分析】曾经用莫队算法做一直超时。

今天意外听说能够用非常神的暴力A过去，于是打算去试试。

【基础暴力代码】

#include<cstdio>

#include<cstring>

using namespace std;

bool f[1000005];

int a[10005],l,r,n,m,i,j,ans;

char c;

int main()

{

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

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

    scanf("%d",&a[i]);

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

  {

    c=' ';while (c!='Q'&&c!='R') c=getchar();

    scanf("%d%d",&l,&r);

    if (c=='R') {a[l]=r;continue;}

    ans=0;memset(f,0,sizeof(f));

    for (j=l;j<=r;j++)

      if (!f[a[j]]) ans++,f[a[j]]=true;

    printf("%d\n",ans);

  }

  return 0;

}

我们会发现，f数组的MEMSET太耗时间了。

怎么办呢？用凌神的标号法！

做到某个i操作时，从l到r扫描，若f[a[j]]还不是i就把他赋成i，并把ans加一。

但是这样还是超时啊。事实证明，当数组开得非常大时，寻址须要非常多时间。

我们能够把颜色离散一下，使每次判重的数组f的元素仅仅有11000（注意会改1000次），这样2s妥妥地A了。

【代码】

#include<cstdio>

using namespace std;

int f[11005],l,r,n,m,i,j,ans,p,d[10005];

int a[1000005];

char c;

int main()

{

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

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

  {

    int o;

    scanf("%d",&o);

    if (!a[o]) a[o]=++p;

    d[i]=a[o];

  }

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

  {

    c=' ';while (c!='Q'&&c!='R') c=getchar();

    scanf("%d%d",&l,&r);

    if (c=='R') {if(!a[r])a[r]=++p;d[l]=a[r];continue;}

    ans=0;

    for (j=l;j<=r;j++)

      if (f[d[j]]!=i) ans++,f[d[j]]=i;

    printf("%d\n",ans);

  }

  return 0;

}