数列分块入门 8 可以多快

[题目链接，题意不在阐述](http://mqcoj.cn/p/4444)

[oj链接](http://mqcoj.cn/p/4444/solution/680b7c77d2f8cd2b3b5caf5a)

本文不太写字，可以参考代码。
## 思路1 分块A
运行数据：
```
代码长度
    4.5 KiB
总耗时
    1532ms
峰值时间
    234ms
峰值内存
    4.8 MiB
```
[提交记录](http://mqcoj.cn/record/680b75a9d2f8cd2b3b5cae86)

需要维护 Tag 表示块内全部覆盖为 X。

每次查询暴力求散块，整块如果没有 Tag 直接暴力求，有 Tag 直接得到答案。

每次修改暴力改散块，打 Tag 直接暴力求。

时间复杂度 $O(n^{1.5})$
### Code:
```cpp
//Do not hack it
// @author       fkxr(luogu uid=995934)
#include <bits/stdc++.h>
#define endl cerr<<"------------------I Love Sqrt Decomposition------------------\n";
//#define int long long
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#define ds(x) (x=='\r'||x=='\n'||x==' ')
#define MAX 20
namespace fastIO {
	template<typename T>inline void r(T& a) { a = 0; char ch = gc(); bool ok = 0; for (; ch < '0' || ch>'9';)ok ^= (ch == '-'), ch = gc(); for (; ch >= '0' && ch <= '9';)a = (a << 1) + (a << 3) + (ch ^ 48), ch = gc(); if (ok)a = -a; }
	template<typename T>inline void w(T a) { if (a == 0) { pc('0'); return; }static char ch[MAX]; int till = 0; if (a < 0) { pc('-'); for (; a;)ch[till++] = -(a % 10), a /= 10; } else for (; a;)ch[till++] = a % 10, a /= 10; for (; till;)pc(ch[--till] ^ 48); }
	struct Srr {
		inline Srr operator>>(int& a) { r(a); return{}; }
		inline Srr operator>>(char& ch) { ch = gc(); for (; ds(ch);)ch = gc(); return{}; }
		inline Srr operator>>(string& s) { s = ""; char ch = gc(); for (; ds(ch);)ch = gc(); for (; !(ds(ch) || ch == EOF);) { s.push_back(ch); ch = gc(); }return{}; }
		template<typename T>inline Srr operator<<(T& a) { r(a); return{}; }
		inline void is(int n, string& s) { s = ""; char ch = gc(); for (; ds(ch);)ch = gc(); for (; n--;) { s.push_back(ch); ch = gc(); } }
	}in;
	struct Sww {
		inline Sww operator<<(const int a) { w(a); return{}; }
		inline Sww operator<<(const char ch) { pc(ch); return{}; }
		inline Sww operator<<(const string s) { for (int i = 0; i < s.size(); i++)pc(s[i]); return{}; }
		template<typename T>inline Sww operator>>(const T a) { w(a); return{}; }
	}out;
}using fastIO::in; using fastIO::out;
#undef ds
#define eout cerr
namespace Maths {
	const bool __is_P[] = { 0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1 };
	inline bool IP(const int a) { if (a <= 29)return __is_P[a]; if (a % 2 == 0 || a % 3 == 0 || a % 5 == 0)return 0; for (int i = 6;; i += 6) { if (((i + 1) * (i + 1)) > a)return 1; if (a % (i + 1) == 0)return 0; if (((i + 5) * (i + 5)) > a)return 1; if (a % (i + 5) == 0)return 0; } }
	inline int power(int a, int b, const int mod = -1) { int ans = 1; if (mod == -1) { for (; b;) { if (b & 1)ans *= a; b >>= 1; a *= a; }return ans; }for (; b;) { if (b & 1)ans = ans * a % mod; b >>= 1; a = a * a % mod; }return ans; }
}using namespace Maths;

#define BIT Binary_Indexed_Tree
#ifdef BIT
namespace BIT {
	struct ds {
#define maxn 100005
		int c0[maxn], c1[maxn], sm[maxn], n;
		inline void Add(int* c, int p, int v) { for (; p <= n; p += p & -p)c[p] += v; }
		inline int Sum(int* c, int p) { int t = 0; for (; p; p -= p & -p)t += c[p]; return t; }
		inline int sum(int l, int r) { return Sum(c0, r) * r - Sum(c1, r) - Sum(c0, l - 1) * (l - 1) + Sum(c1, l - 1); }
		inline void add(int l, int r, int v) { Add(c0, l, v); Add(c0, r + 1, -v); Add(c1, l, (l - 1) * v); Add(c1, r + 1, -r * v); }
		inline void init(int* c, int len) { int last = 0; for (int i = 1; i <= len; i++) { last = c[i] - last; Add(c0, i, last); Add(c1, i, last * (i - 1)); last = c[i]; } }
	};
#undef maxn
}using namespace BIT;
#endif
int id[100005], tag[325], a[100005];
int len;
void cd(int idd) {
    if (tag[idd]) {
        for (int i = idd * len; id[i] == idd; i++) {
            a[i] = tag[idd];
        }
        tag[idd] = 0;
    }
}

int cha(int l, int r, int c) {
    int q = id[l], w = id[r], ans = 0;
    if (q == w) {
        cd(q);
        for (int i = l; i <= r; i++) {
            ans += (a[i] == c);
            a[i] = c;
        }
        return ans;
    }
    cd(q);
    for (int i = l; id[i] == q; i++) {
        ans += (a[i] == c);
        a[i] = c;
    }
    cd(w);
    for (int i = r; id[i] == w; i--) {
        ans += (a[i] == c);
        a[i] = c;
    }
    for (int i = q + 1; i < w; i++) {
        if (tag[i] == 0) {
            for (int j = i * len; id[j] == i; j++) {
                ans += (a[j] == c);
            }
            tag[i] = c;
        }
        else if (tag[i] == c) {
            ans += len;
        }
        else {
            tag[i] = c;
        }
    }
    return ans;
}

signed main() {
    int n;
    in >> n;
    len = sqrt(n);
    for (int i = 0; i < n; i++) {
        in >> a[i];
        a[i] += (2LL << 32);
        id[i] = i / len;
    }
    int m = n;
    for (; m--;) {
        int l, r, c;
        in >> l >> r >> c;
        out << cha(--l, --r, c + (2LL << 32)) << '\n';
    }
    return 0;
}
```
## 思路2 分块B
运行数据：
```
代码长度
    4.5 KiB 
总耗时
    997ms
峰值时间
    152ms
峰值内存
    1.6 MiB 
```
[提交记录](http://mqcoj.cn/record/680b778ad2f8cd2b3b5caf15)

还是思路一的思路，优化在于：数据是随机生成的，所以块长越大越好。
### Code:
```cpp
//Do not hack it
// @author       fkxr(luogu uid=995934)
#include <bits/stdc++.h>
#define endl cerr<<"------------------I Love Sqrt Decomposition------------------\n";
//#define int long long
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#define BIT Binary_Indexed_Tree
#ifdef BIT
namespace BIT {
	struct ds {
#define maxn 100005
		int c0[maxn], c1[maxn], sm[maxn], n;
		inline void Add(int* c, int p, int v) { for (; p <= n; p += p & -p)c[p] += v; }
		inline int Sum(int* c, int p) { int t = 0; for (; p; p -= p & -p)t += c[p]; return t; }
		inline int sum(int l, int r) { return Sum(c0, r) * r - Sum(c1, r) - Sum(c0, l - 1) * (l - 1) + Sum(c1, l - 1); }
		inline void add(int l, int r, int v) { Add(c0, l, v); Add(c0, r + 1, -v); Add(c1, l, (l - 1) * v); Add(c1, r + 1, -r * v); }
		inline void init(int* c, int len) { int last = 0; for (int i = 1; i <= len; i++) { last = c[i] - last; Add(c0, i, last); Add(c1, i, last * (i - 1)); last = c[i]; } }
	};
#undef maxn
}using namespace BIT;
#endif
int id[100005], tag[1525], a[100005];
int len;
void cd(int idd) {
    if (tag[idd]) {
        for (int i = idd * len; id[i] == idd; i++) {
            a[i] = tag[idd];
        }
        tag[idd] = 0;
    }
}

signed main() {
    int n;
    in >> n;
    len = sqrt(n/5);
    for (int i = 0; i < n; i++) {
        in >> a[i];
        a[i] += (2LL << 32);
        id[i] = i / len;
    }
    int m = n;
    for (; m--;) {
        int l, r, c;
        in >> l >> r >> c;
        out << cha(--l, --r, c + (2LL << 32)) << '\n';
    }
    return 0;
}
```
## 思路3 珂朵莉树
[关于什么是珂朵莉树](https://oi-wiki.org/misc/odt/)

运行数据：
```
代码长度
    4.1 KiB 
总耗时
    857ms
峰值时间
    129ms
峰值内存
    6.9 MiB 
```
很明显，这道题是否随机数据ODT的时间复杂度都是 $O(n\log n)$

### Code:
```cpp
//Do not hack it
// @author       fkxr(luogu uid=995934)
#include <bits/stdc++.h>
#define endl cerr<<"------------------I Love Sqrt Decomposition------------------\n";
//#define int long long
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

struct node {
	int l, r, v;
	node(int L, int R = 0, int V = 0) {
		l = L;
		r = R;
		v = V;
	}
	friend inline bool operator<(const node& a, const node& b) {
		return a.l < b.l;
	}
};
set<node>s;
#define I set<node>::iterator

inline I cut(int x) {
	I it = s.lower_bound(node(x));
	if (it != s.end() && it->l == x) 
		return it;
	--it;
	if (it->r < x) 
		return s.end();
	int L = it->l, R = it->r, V = it->v;
	s.erase(it);
	s.insert(node(L, x - 1, V));
	return s.insert(node(x, R, V)).first;
}

signed main() {
	int n;
	in >> n;
	for (int i = 1; i <= n; i++) {
		int x;
		in >> x;
		s.insert(node(i, i, x));
	}
	for (; n--;) {
		int l, r, c;
		in >> l >> r >> c;
		I itr = cut(r + 1), itl = cut(l);
		int ans = 0;
		for (I it = itl; it != itr; ++it) {
			ans += int(it->v == c) * (it->r - it->l + 1);
		}
		out << ans << '\n';
		s.erase(itl, itr);
		s.insert(node(l, r, c));
	}
    return 0;
}
```
# 还有更快的方法吗？
很遗憾，目前没有。

如果收效好的话更新 $O(n^{1.271})$ 的线段树分块的全面教程

正在渲染内容...