专栏首页数据结构与算法P1903 【模板】分块/带修改莫队(数颜色)

P1903 【模板】分块/带修改莫队(数颜色)

题目描述

墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令:

1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。

2、 R P Col 把第P支画笔替换为颜色Col。

为了满足墨墨的要求,你知道你需要干什么了吗?

输入输出格式

输入格式:

第1行两个整数N,M,分别代表初始画笔的数量以及墨墨会做的事情的个数。

第2行N个整数,分别代表初始画笔排中第i支画笔的颜色。

第3行到第2+M行,每行分别代表墨墨会做的一件事情,格式见题干部分。

输出格式:

对于每一个Query的询问,你需要在对应的行中给出一个数字,代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。

输入输出样例

输入样例#1:

6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

输出样例#1:

4
4
3
4

说明

对于100%的数据,N≤10000,M≤10000,修改操作不多于1000次,所有的输入数据中出现的所有整数均大于等于1且不超过10^6。

来源:bzoj2120

本题数据为洛谷自造数据,使用CYaRon耗时5分钟完成数据制作。

裸的带修改的莫队

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<cstdlib>
  7 #include<ctime>
  8 using namespace std;
  9 const int MAXN=10001;
 10 static void read(int &n)
 11 {
 12     char c='+';int x=0;bool flag=0;
 13     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
 14     while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c-48);c=getchar();}
 15     flag==1?n=-x:n=x;
 16 }
 17 int n,m;
 18 int a[MAXN];
 19 struct CX
 20 {
 21     int l,r,id,tm;// tm上一次的更改操作 
 22 }cx[MAXN];
 23 int cxnum;
 24 struct GG
 25 {
 26     int pos,val,pre;
 27 }gg[MAXN];
 28 int ggnum;
 29 int head[MAXN];
 30 int where[MAXN];
 31 int base;
 32 int vis[MAXN];// 是否有更改操作 
 33 int color[MAXN];
 34 int ans=0;
 35 int out[MAXN];
 36 int comp(const CX &a,const CX &b)
 37 {
 38     if(where[a.l]==where[b.l])
 39         return a.r<b.r;
 40     else 
 41         return where[a.l]<where[b.l];
 42 }
 43 int calc(int x)
 44 {
 45     if(vis[x])
 46     {
 47         if(--color[a[x]]==0)
 48             ans--;
 49     }
 50     else 
 51     {
 52         if(++color[a[x]]==1)
 53             ans++;
 54     }    
 55     vis[x]=!vis[x];
 56 }
 57 void change(int p,int v)
 58 {
 59     if(vis[p])
 60     {
 61         calc(p);
 62         a[p]=v;
 63         calc(p);
 64     }
 65     else
 66     a[p]=v;
 67 }
 68 
 69 int main()
 70 {
 71     read(n);read(m);
 72     for(int i=1;i<=n;i++)
 73         read(a[i]),head[i]=a[i];
 74     base=sqrt(n);
 75     for(int i=1;i<=n;i++)
 76         where[i]=(i-1)/base+1;
 77     for(int i=1;i<=m;i++)
 78     {
 79         char c;
 80         int x,y;
 81         cin>>c;
 82         read(x);read(y);
 83         if(c=='Q')// 查询 
 84         {
 85             cxnum++;
 86             cx[cxnum].l=x;
 87             cx[cxnum].r=y;
 88             cx[cxnum].id=cxnum;
 89             cx[cxnum].tm=ggnum;
 90         }
 91         else
 92         {
 93             ggnum++;
 94             gg[ggnum].pos=x;
 95             gg[ggnum].val=y;
 96             gg[ggnum].pre=head[x];
 97             head[x]=y;
 98         }
 99     }
100     sort(cx+1,cx+cxnum+1,comp);
101     int l=1,r=0;
102     for(int i=1;i<=cxnum;i++)
103     {
104         for(int j=cx[i-1].tm+1;j<=cx[i].tm;j++)
105             change(gg[j].pos,gg[j].val);
106         for(int j=cx[i-1].tm;j>=cx[i].tm+1;j--)
107             change(gg[j].pos,gg[j].pre);// 此处是pre,不是val!!! 
108         for(;l<cx[i].l;l++)
109             calc(l);
110         for(;l>cx[i].l;l--)
111             calc(l-1);
112         for(;r<cx[i].r;r++)
113             calc(r+1);
114         for(;r>cx[i].r;r--)
115             calc(r);
116         out[cx[i].id]=ans;
117     }
118     for(int i=1;i<=cxnum;i++)
119         printf("%d\n",out[i]);
120     return 0;
121 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BZOJ4300: 绝世好题(dp)

    给定一个长度为n的数列ai,求ai的子序列bi的最长长度,满足bi&bi-1!=0(2<=i<=len)。

    attack
  • 关于scanf与cin哪个快的问题

    一开始入c++的时候成天跑cin,cout 直到有一天用cin,cout超时 才知道scanf比cin快的多 但是后来又听说加了ios::sync_with_s...

    attack
  • BZOJ3509: [CodeChef] COUNTARI(生成函数 分块)

    发现 ,那么有一种暴力思路是枚举j,对于之前出现过的数构造一个生成函数,对于之后出现过的数构造一个生成函数,求一下第 项的值。复杂度

    attack
  • Codeforces Round #561 (Div. 2)

    C. 求min(|X-Y|,|X+Y|) <= min(X,Y) <= max(X,Y) <= max(|X-Y|,|X+Y|)

    用户2965768
  • 「2017 Multi-University Training Contest 2」2017多校训练2

    给定数组a[1..n]和b[1..n],b[i]在[1~n]内。要得到a[n+1..2n],每次选b数组的一个,令a[i]为j=b[k]到i-1位置中最大的a[...

    饶文津
  • 2017年中国大学生程序设计竞赛-中南地区赛暨第八届湘潭市大学生计算机程序设计大赛题解&源码(A.高斯消元,D,模拟,E,前缀和,F,LCS,H,Prim算法,I,胡搞,J,树状数组)

    A-------------------------------------------------------------------------------...

    Angel_Kitty
  • CSU 1326: The contest(分组背包)

    http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1326 题意:       n个题目,每个题目都有一个价值P...

    用户1624346
  • BZOJ4300: 绝世好题(dp)

    给定一个长度为n的数列ai,求ai的子序列bi的最长长度,满足bi&bi-1!=0(2<=i<=len)。

    attack
  • HDU 3488 Tour(拆点+二分图最大权匹配--KM)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3488

    Ch_Zaqdt
  • 1035. 插入与归并(25)

    插入排序是迭代算法,逐一获得输入数据,逐步产生有序的输出序列。每步迭代中,算法从输入序列中取出一元素,将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

    AI那点小事

扫码关注云+社区

领取腾讯云代金券