1 solutions

  • 1
    @ 2025-4-25 20:13:43

    数列分块入门 8 可以多快

    洛谷链接

    题目链接，题意不在阐述

    本文不太写字，可以参考代码。

    思路1 分块A

    运行数据：

    代码长度
    4.5 KiB
总耗时
    1532ms
峰值时间
    234ms
峰值内存
    4.8 MiB

    提交记录

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

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

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

    时间复杂度 O(n1.5)O(n^{1.5})

    Code:

    //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

    提交记录

    还是思路一的思路，优化在于：数据是随机生成的，所以块长越大越好。

    Code:

    //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[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;
    }
}

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/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 珂朵莉树

    关于什么是珂朵莉树

    运行数据：

    代码长度
    4.1 KiB 
总耗时
    857ms
峰值时间
    129ms
峰值内存
    6.9 MiB

    很明显，这道题是否随机数据ODT的时间复杂度都是 O(nlog⁡n)O(n\log n)

    Code:

    //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

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(n1.271)O(n^{1.271}) 的线段树分块的全面教程

    • 1

    数列分块入门 8

    Information

    ID
    4444
    Time
    500ms
    Memory
    256MiB
    Difficulty
    9
    Tags
    (None)
    # Submissions
    44
    Accepted
    2
    Uploaded By
    1. About
    2. Contact Us
    3. Privacy
    4. Terms of Service
    5. Copyright Complaint
    6. Language
    7. Legacy mode
    8. Theme
    2. 蜀ICP备2022005482号-4
    3. Worker 0, 48ms
    4. Powered by Hydro v4.19.1 Community