Luogu P3939 数颜色

题目描述

https://www.luogu.com.cn/problem/P3939

Solution

我们直接每个颜色开一个vector

查询直接lower_bound

由于交换位置是不影响一个vector内的顺序，所以直接 $O(1)$ 交换即可

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define maxn 300010
#define pb push_back
using namespace std;

int n, m, a[maxn];

vector<int> col[maxn];

inline void solve_1() {
    int x, y, c, l, r; scanf("%d%d%d", &x, &y, &c);
    l = lower_bound(col[c].begin(), col[c].end(), x) - col[c].begin(); 
    r = upper_bound(col[c].begin(), col[c].end(), y) - col[c].begin() - 1; 
    printf("%d\n", r - l + 1); 
}

inline void solve_2() {
    int x, p1, p2; scanf("%d", &x);
    if (a[x] == a[x + 1]) return ;
    p1 = lower_bound(col[a[x]].begin(), col[a[x]].end(), x) - col[a[x]].begin();
    p2 = lower_bound(col[a[x + 1]].begin(), col[a[x + 1]].end(), x) - col[a[x + 1]].begin();
    swap(col[a[x]][p1], col[a[x + 1]][p2]);
    swap(a[x], a[x + 1]);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), col[a[i]].pb(i); 
    for (int i = 1; i <= m; ++i) {
        int opt; scanf("%d", &opt);
        switch (opt) {
        case 1 : solve_1(); break;
        case 2 : solve_2(); break;
        }
    }
    return 0;
}