洛谷P3939 数颜色(二分 vector)

题意

题目链接

sol

直接拿vector维护每种颜色的出现位置，然后二分一下。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m, a[maxn];
vector<int> v[maxn];
void modify(int c, int l, int val) {
    vector<int> &t = v[c];
    int pos = lower_bound(t.begin(), t.end(), l) - t.begin();
    t[pos] += val;
}
int query(int c, int pos) {
    vector<int> &t = v[c];
    int num = upper_bound(t.begin(), t.end(), pos) - t.begin();
    if(num == 0) return 0;
    else return num;
}
int main() {
    n = read(); m = read();
    for(int i = 1; i <= n; i++) v[a[i] = read()].push_back(i);
    for(int i = 1; i <= m; i++) {
        int opt = read();
        if(opt == 1) {
            int l = read(), r = read(), c = read();
            printf("%d\n", query(c, r) - query(c, l - 1));
        } else {
            int l = read(), r = l + 1;
            if(a[l] != a[r]) {
                modify(a[l], l, 1); modify(a[r], r, -1);
                swap(a[l], a[r]);
            }
        }
    }
    return 0;   
}