题解 P2464 【[SDOI2008]郁闷的小J】

· · 题解

这道题看各位大神用各种二叉树AC，可是我懒（其实不知道怎么用），没写二叉树，写了个超级简单的分块就AC了，效率还前几……

我们可以把数列分成几块，每块用map维护（STL大法好），map可以直接储存当前块内某个数字的个数，然后就可以乱搞了。

对于询问，直接就是块状数组最基本的询问方式，更改就先更改数列，然后修改当前块的map值，为了节省空间，如果当前块某个数字的出现个数变成0了，可以直接删除。

这样总复杂度为O((k+(n/k)·log k)·m)，其中k是每个块的大小。

可以通过函数求导算出大致k=sqrt(n·log n)的时候复杂度最低，为O(m·sqrt(n·log n))。

分块大法好……

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <math.h>
#include <queue>
#include <map>
#include <functional>
#include <time.h>
#define inline __attribute((always_inline))
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;

const int maxn = 100005, maxs = 400;
int seq[maxn], n, m, sz;
map<int, int> buc[maxs];
map<int, int>::iterator it;
char opt[5];
int main(){
    scanf("%d%d", &n, &m);
    sz = sqrt(n * log2(n));
    for(int i = 0; i < n; i++){
        scanf("%d", seq + i);
        int k = i / sz;
        it = buc[k].find(seq[i]);
        if(it == buc[k].end()) buc[k].insert(make_pair(seq[i], 1));
        else it->second++;
    }
    while(m--){
        scanf("%s", opt);
        if(opt[0] == 'C'){
            int p, x;
            scanf("%d%d", &p, &x); p--;
            int k = p / sz;
            it = buc[k].find(seq[p]);
            if(--it->second == 0) buc[k].erase(it);
            seq[p] = x;
            it = buc[k].find(x);
            if(it == buc[k].end()) buc[k].insert(make_pair(x, 1));
            else it->second++;
        } else {
            int s, t, x;
            scanf("%d%d%d", &s, &t, &x); s--, t--;
            int ks = s / sz, kt = t / sz, res = 0;
            if(ks * sz == s) ks--;
            if(kt * sz + sz - 1 == t) kt++;
            for(int i = ks + 1; i < kt; i++){
                it = buc[i].find(x);
                if(it != buc[i].end()) res += it->second;
            }
            int end = min(t + 1, ks * sz + sz);
            for(int i = s; i < end; i++) res += seq[i] == x;
            if(end <= t) for(int i = kt * sz; i <= t; i++) res += seq[i] == x;
            printf("%d\n", res);
        }
    }
    return 0;
}