LOJ#6284. 数列分块入门 8

分块的时候开一个数组标记这个区间是不是都是一样颜色的部分，如果是的话，我后面的查询，更新部分就可以直接整块操作，对于不是不全部都一样颜色的块在具体进到快里面去暴力。

在更新的时候对边上的两个不完整的块，先暴力把这个地方的标记下推下去，然后我在给它重新标记

#include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define first fi
#define second se
#define lowbit(x) (x & (-x))

typedef unsigned long long int ull;
typedef long long int ll;
const double pi = 4.0*atan(1.0);
const int inf = 0x3f3f3f3f;
const int maxn = 100005;
const int maxm = 100000;
const int mod = 10007;
using namespace std;

int n, m, tol, T;
int block;
int a[maxn];
int add[maxn];
bool vis[maxn];
int belong[maxn];

void init() {
    memset(a, 0, sizeof a);
    memset(add, 0, sizeof add);
    memset(vis, false, sizeof vis);
    memset(belong, 0, sizeof belong);
}

int L(int x) {
    return (x-1)*block + 1;
}

int R(int x) {
    return min(n, x*block);
}

void update(int l, int r, int c) {
    if(vis[belong[l]]) {
        for(int i=L(belong[l]); i<=R(belong[l]); i++)    a[i] = add[belong[i]];
        vis[belong[l]] = false;
    }
    for(int i=l; i<=min(r, R(belong[l])); i++)    a[i] = c;
    if(belong[l] == belong[r])    return ;
    if(belong[l] != belong[r]) {
        if(vis[belong[r]]) {
            for(int i=L(belong[r]); i<=R(belong[r]); i++)    a[i] = add[belong[i]];
            vis[belong[r]] = false;
        }
        for(int i=L(belong[r]); i<=r; i++)    a[i] = c;
    }
    for(int i=belong[l]+1; i<belong[r]; i++) {
        add[i] = c;
        vis[i] = true;
    }
}

int query(int l, int r, int c) {
    int ans = 0;
    if(vis[belong[l]]) {
        if(add[belong[l]] == c)    ans += min(R(belong[l]), r) - l + 1;
    } else {
        for(int i=l; i<=min(R(belong[l]), r); i++)    ans += (a[i]==c);
    }
    if(belong[l] == belong[r])    return ans;
    if(belong[l] != belong[r]) {
        if(vis[belong[r]]) {
            if(add[belong[r]] == c)    ans += r - L(belong[r]) + 1;
        } else {
            for(int i=L(belong[r]); i<=r; i++)    ans += (a[i] == c);
        }
    }
    for(int i=belong[l]+1; i<belong[r]; i++) {
        if(vis[i]) {
            if(add[i] == c)    ans += R(i) - L(i) + 1;
        } else {
            for(int j=L(i); j<=R(i); j++) {
                ans += (a[j] == c);
            }
        }
    }
    return ans;
}

int main() {
    while(~scanf("%d", &n)) {
        init();
        block = sqrt(n);
        for(int i=1; i<=n; i++)    {
            scanf("%d", &a[i]);
            belong[i] = (i-1) / block + 1;
        }
        m = n;
        while(m--) {
            int l, r, c;
            scanf("%d%d%d", &l, &r, &c);
            int ans = query(l, r, c);
            update(l, r, c);
            printf("%d
", ans);
        }
    }
    return 0;
}