MENU

洛谷P3939 数颜色

洛谷P3939

每个数存出现位置的有序表。查询直接二分;修改二分到对应的然后交换,因为是相邻的两个位置所以不会破坏有序性。

上来就想线段树/树状数组/分块/莫队。。。数据结构学傻了,没救了

#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
using namespace std;
struct io {
    static const int L = (1 << 21) + 1;
    char ibuf[L], *iS, *iT, obuf[L], *oS, *oT, st[50];
    void flush() { fwrite(obuf, 1, oS - obuf, stdout), oS = obuf; }
    void putc(char x) {
        *oS++ = x;
        if(oS == oT)flush();
    }
    int gc() { return iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin), (iS == iT ? EOF : *iS++)) : *iS++; }
    template<class T>T rd() {
        int c = gc();
        T x = 0;
        for(; !isdigit(c); c = gc());
        for(; isdigit(c); c = gc())x = x * 10 + (c & 15);
        return x;
    }
    template<class T>void print(T x) {
        if(!x) { putc('0'); return; }
        int tp = 0;
        for(; x; st[tp++] = x % 10 + 48, x /= 10);
        for(tp--; ~tp; putc(st[tp--]));
    }
    io() :oS(obuf), oT(obuf + L - 1) {}
    ~io() { fwrite(obuf, 1, oS - obuf, stdout); }
}ip;
int n = ip.rd<int>(), m = ip.rd<int>(), a[300001];
vector<int> v[300001];
int main() {
    for(int i = 1; i <= n; ++i)v[a[i] = ip.rd<int>()].push_back(i);
    while(m--) {
        int x = ip.rd<int>();
        if(x == 1) {
            int l = ip.rd<int>(), r = ip.rd<int>(), c = ip.rd<int>();
            ip.print(upper_bound(v[c].begin(), v[c].end(), r) - lower_bound(v[c].begin(), v[c].end(), l)), ip.putc('\n');
        } else {
            x = ip.rd<int>();
            if(a[x] != a[x + 1])++*lower_bound(v[a[x]].begin(), v[a[x]].end(), x), --*lower_bound(v[a[x + 1]].begin(), v[a[x + 1]].end(), x + 1), swap(a[x], a[x + 1]);
        }
    }
}
Leave a Comment

captcha
请输入验证码