一无所|知的小|J f

一无所|知的小|J f

被分块了(划去

题解 P3939 【数颜色】

posted on 2018-12-28 22:02:27 | under 题解 |

emm...这题分块有点卡空间

机房dalao直接按题意分块被卡时间+卡空间了。。。 所以考虑一下怎样优化, 一看这种求个数的题目, 颜色种类一般都不会很多, 所以尝试离散化。 离散化之后用一个cnt数组来处理一下每种离散化后颜色个数的前缀和, 交换两个点的时候如果这两个点再同一个块里自然直接改, 不在的话修改一下本块的cnt也就是了。查询的时候散块直接暴力, 整块前缀和相减,这样修改的复杂度是O1, 查询的时间复杂度是 两个块的长度(散块的查询) 。足以通过此题

于是愉快的MLE到95分, 尝试用unsinged short来存cnt数据, 但是这样又会WA一个点, 把块调大了一些就过了。

另外注意: 查询的颜色未必在初始序列中出现, 所以要开个数组特判一下。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define maxn 300010 
#define re register
#define FOR(i, l, r) for(re int i = l; i <= r; ++i)
using namespace std;

int n, m, c, r, t, x, y, s;
int sq;
int a[maxn], b[maxn], z[maxn];
bool bl[maxn];
int cnt[550][maxn];
inline void in(re int &x){
    x=0;re int bl = 1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c == '-')
          bl = -1;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
    x *= bl;
}

void out(re int a){
    if(a < 0) {
        putchar('-');
        a = -a;
    }
    if(a>=10)out(a/10);
    putchar(a%10+'0');
}

inline int query(int x, int y, int k) {
    int res = 0;
    FOR(i, x, min(y, b[x]*sq))
      if(a[i] == k)
        ++res;
    if(b[x] != b[y])
      FOR(i, (b[y]-1)*sq+1, y)
        if(a[i] == k)
          ++res;
    if(b[x] < b[y]) {
        res += (cnt[b[y]-1][k]-cnt[b[x]][k]);   
    }
    return res;
}

void change(int x) {
    if(b[x] == b[x+1]) {
        swap(a[x], a[x+1]);
    }
    else {
        --cnt[b[x]][a[x]];
        ++cnt[b[x]][a[x+1]];
        swap(a[x], a[x+1]);
    }
}

int main() {
    in(n), in(m);
    sq = min(n, 1528); 
    FOR(i, 1, n)
      in(a[i]), b[i] = (i-1)/sq+1, z[i] = a[i], bl[a[i]] = 1;
    z[0] = n;
    sort(z+1, z+z[0]+1);
    z[0] = unique(z+1, z+z[0]+1)-z-1;
    FOR(i, 1, n) {
        a[i] = lower_bound(z+1, z+z[0]+1, a[i])-z;
        ++cnt[b[i]][a[i]];
    }
    FOR(i, 2, b[n]) {
        FOR(j, 1, z[0])
          cnt[i][j] += cnt[i-1][j];
    }
    FOR(i, 1, m) {
        in(t);
        if(t == 1) {
            in(x), in(y), in(s);
            if(!bl[s]) {
                puts("0");
                continue;
            } 
            s = lower_bound(z+1, z+z[0]+1, s)-z;
            out(query(x, y, s)),
            putchar(10);
        }
        else {
            in(x);
            change(x);
        }
    }
}