P1903 数颜色 / 维护队列（带修莫队）

2021/9/24 6:11:06

编程Tag： 队列 int define include 画笔 -- ++ 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支画笔中共有几种不同颜色的画笔。

思路：
带修莫队，与普通莫队不同的是，带修莫队在保存的询问信息中增加了一维时间，按左端点为第一关键字，右端点为第二关键字，时间为第三关键字进行排序，块的大小一般取\(n^{\dfrac{2}{3}}\)。
注意：此题中，如果用 \(getchar()\)函数进行字符输入输出，会RE最后三个点（~~没想明白~~），直接用字符串输入就不会出问题。

code:

点击查看代码

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <deque>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#include <unordered_map>

#define fi first
#define se second
#define pb push_back
// #define endl "\n"
#define debug(x) cout << #x << ":" << x << endl;
#define bug cout << "********" << endl;
#define all(x) x.begin(), x.end()
#define lowbit(x) x & -x
#define fin(x) freopen(x, "r", stdin)
#define fout(x) freopen(x, "w", stdout)
#define ull unsigned long long
#define ll long long 

const double eps = 1e-15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1.0);
const int mod =  998244353;
const int maxn = 1e6 + 10;

using namespace std;

int tot, cnt, block;
int n, m, ret;
int ans[maxn], s[maxn], vis[maxn];

struct node1{
    int l, r, t, id;
    bool operator<(const node1 &a)const{
        if(a.l/block == l/block){
            if(a.r/block == r/block)return t < a.t;
            if((l/block) & 1)return r < a.r;
            else return r > a.r;
        }
        return l < a.l;
    }
}q[maxn];
struct node2{
    int x, y;
}p[maxn];

void add(int x){
    if(!vis[s[x]])ret ++;
    vis[s[x]] ++;
}

void del(int x){
    vis[s[x]] --;
    if(!vis[s[x]])ret --;
}

void work(int x, int l, int r){
    int &a = p[x].y, b = p[x].x;
    if(l <= b && b <= r){
        if(!(vis[a] ++))ret ++;
        if(!(-- vis[s[b]]))ret --;
    }   
    swap(a, s[b]);
}

int main(){
    char ch; int a, b;
    scanf("%d%d", &n, &m);
    block = pow(n, 2.0/3); 
    for(int i = 1; i <= n; i ++)scanf("%d", &s[i]);
    for(int i = 1; i <= m; i ++){
        char ch[5];
        scanf("%s", ch);
        scanf("%d%d", &a, &b);
        if(ch[0] == 'Q')q[++ tot] = {a, b, cnt, tot};
        else p[++ cnt] = {a, b};
    }
    sort(q + 1, q + tot + 1);
    int l = 0, r = 0, t = 0;
    for(int i = 1; i <= tot; i ++){
        while(l < q[i].l)del(l ++);
        while(l > q[i].l)add(-- l);

        while(r > q[i].r)del(r --);
        while(r < q[i].r)add(++ r);
        
        while(t > q[i].t)work(t --, l, r);
        while(t < q[i].t)work(++ t, l, r);
        ans[q[i].id] = ret;
    }
    for(int i = 1; i <= tot; i ++)printf("%d\n", ans[i]);
    return 0;
}

这篇关于P1903 数颜色 / 维护队列（带修莫队）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

P1903 数颜色 / 维护队列（带修莫队）

相关编程文章