分塊

6277. 數(shù)列分塊入門 1

分塊思想

我們把每m個元素分成一塊，所以我們總共的塊數(shù)就是$n/m$塊，一般情況下我們?nèi)?span id="ze8trgl8bvbq" class="katex--inline">$m=\sqrt{n}$.對于區(qū)間加操作，我們可以先暴力左右兩邊，然后對于中間的整塊的部分的加減，我們累加在塊的標記上，然后我們每次查詢的時候只要，每個元素的值加上這個塊的標記值，就可以得到我們的答案了。

復(fù)雜度分析

每次操作我們修改的最多的元素最多就是$O(\sqrt{n})$級別的個數(shù)，時間復(fù)雜讀也就是$O(\sqrt{n})$級別的，查詢的時間復(fù)雜度是$O(1)$的，最多有$n$個操作，整體上是$O(n\sqrt{n})$的，于是一個暴力而優(yōu)美的分塊算法就出現(xiàn)了，簡單的思想，\sqrt { }?級別的優(yōu)化。

代碼

/*Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> #define mp make_pair #define pb push_back #define endl '\n'using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii;const double pi = acos(-1.0); const double eps = 1e-7; const int inf = 0x3f3f3f3f;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }void print(ll x) {if(x < 10) {putchar(x + 48);return ;}print(x / 10);putchar(x % 10 + 48); }const int N = 5e4 + 10;int value[N], bl[N], tag[N], block, n;void add(int l, int r, int c) {for(int i = l; i <= bl[l] * block && i <= r; i++) {//對前面的部分進行暴力修改。value[i] += c;}if(bl[l] != bl[r]) {//如果這兩個塊不在同一個分塊中才要進行后面的暴力修改，否則將會重復(fù)累加。for(int i = block * (bl[r] - 1) + 1; i <= r; i++) {value[i] += c;}}for(int i = bl[l] + 1; i <= bl[r] - 1; i++) {//對每個塊進行區(qū)間修改。tag[i] += c;}//嚴格來說每次修改的復(fù)雜度最多將會是3 * sqrt(n) }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);n = read(); block = sqrt(n);//block是分塊的大小for(int i = 1; i <= n; i++) {value[i] = read();bl[i] = (i - 1) / block + 1;//每個位置在分塊中的位置。}for(int i = 1; i <= n; i++) {int op = read(), l = read(), r = read(), c = read();if(!op) {add(l, r, c);}else {printf("%d\n", value[r] + tag[bl[r]]);//他當(dāng)前的值加上分塊的累加值。}}return 0; }

6278. 數(shù)列分塊入門 2

想法

查詢操作：對于每一個塊我們開一個數(shù)組來維護其有序的狀態(tài)，所以對于每一個整塊我們可以通過二分去得到我們的答案，對于兩頭的塊，我們可以暴力去得到滿足條件的數(shù)。

修改操作：同樣的對于整塊的我們還是在一個區(qū)間標記加上其修改值，對于兩頭的操作我們需要額外單獨的操作，記得操作完之后要把原來的存區(qū)間有序的數(shù)組重新排序，得到一個新的區(qū)間有序數(shù)組。

代碼

/*Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> #define mp make_pair #define pb push_back #define endl '\n'using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii;const double pi = acos(-1.0); const double eps = 1e-7; const int inf = 0x3f3f3f3f;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }void print(ll x) {if(x < 10) {putchar(x + 48);return ;}print(x / 10);putchar(x % 10 + 48); }const int N = 5e4 + 10;int value[N], bl[N], tag[N], n, block, m;vector<int> elem[N];void reset(int x) {//最好還是寫一個函數(shù)，一開始我就是沒寫函數(shù)然后wa了一次。elem[x].clear();for(int i = (x - 1) * block + 1; i <= x * block && i <= n; i++)elem[x].pb(value[i]);sort(elem[x].begin(), elem[x].end()); }void add(int l, int r, int x) {for(int i = l; i <= r && i <= bl[l] * block; i++)value[i] += x;reset(bl[l]);if(bl[l] != bl[r]) {for(int i = (bl[r] - 1) * block + 1; i <= r; i++)value[i] += x;reset(bl[r]);}for(int i = bl[l] + 1; i <= bl[r] - 1; i++)tag[i] += x; }int query(int l, int r, int x) {int sum = 0;for(int i = l; i <= r && i <= bl[l] * block; i++)if(value[i] + tag[bl[i]] < x)sum++;if(bl[l] != bl[r])for(int i = (bl[r] - 1) * block + 1; i <= r; i++)if(value[i] + tag[bl[i]] < x)sum++;for(int i = bl[l] + 1; i <= bl[r] - 1; i++) {sum += lower_bound(elem[i].begin(), elem[i].end(), x - tag[i]) - elem[i].begin();}return sum; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);n = read(); block = sqrt(n);for(int i = 1; i <= n; i++) {value[i] = read();bl[i] = (i + block - 1) / block;elem[bl[i]].pb(value[i]);}m = bl[n];for(int i = 1; i <= m; i++) sort(elem[i].begin(), elem[i].end());for(int i = 1; i <= n; i++) {int op = read(), l = read(), r = read(), c = read();if(op & 1) {printf("%d\n", query(l, r, c * c));}else {add(l, r, c);}}return 0; }

6279. 數(shù)列分塊入門 3

想法

這題應(yīng)該是跟上一個類似，就是$query$操作稍微變化一下。

用上面的代碼修改的時候要注意，這題數(shù)據(jù)變大了，需要改成$1e5+10$，不然就跟我一樣入坑了。

代碼

/*Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> #define mp make_pair #define pb push_back #define endl '\n'using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii;const double pi = acos(-1.0); const double eps = 1e-7; const int inf = 0x3f3f3f3f;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }void print(ll x) {if(x < 10) {putchar(x + 48);return ;}print(x / 10);putchar(x % 10 + 48); }const int N = 1e5 + 10;int value[N], bl[N], tag[N], n, block, m;vector<int> elem[N];void reset(int x) {elem[x].clear();for(int i = (x - 1) * block + 1; i <= x * block && i <= n; i++)elem[x].pb(value[i]);sort(elem[x].begin(), elem[x].end()); }void add(int l, int r, int x) {for(int i = l; i <= r && i <= bl[l] * block; i++)value[i] += x;reset(bl[l]);if(bl[l] != bl[r]) {for(int i = (bl[r] - 1) * block + 1; i <= r; i++)value[i] += x;reset(bl[r]);}for(int i = bl[l] + 1; i <= bl[r] - 1; i++)tag[i] += x; }ll query(int l, int r, int x) {ll ans = -1e10;for(int i = l; i <= r && i <= bl[l] * block; i++)if(value[i] + tag[bl[i]] < x && value[i] + tag[bl[i]] > ans)ans = value[i] + tag[bl[i]];if(bl[l] != bl[r])for(int i = (bl[r] - 1) * block + 1; i <= r; i++)if(value[i] + tag[bl[i]] < x && value[i] + tag[bl[i]] > ans)ans = value[i] + tag[bl[i]];for(int i = bl[l] + 1; i <= bl[r] - 1; i++) {auto p = lower_bound(elem[i].begin(), elem[i].end(), x - tag[i]);if(p == elem[i].begin()) continue;p--;ans = max(ans, 1ll * (*p + tag[i]));}return ans == -1e10 ? -1 : ans; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);n = read(); block = sqrt(n);for(int i = 1; i <= n; i++) {value[i] = read();bl[i] = (i + block - 1) / block;elem[bl[i]].pb(value[i]);}m = bl[n];for(int i = 1; i <= m; i++) sort(elem[i].begin(), elem[i].end());for(int i = 1; i <= n; i++) {int op = read(), l = read(), r = read(), c = read();if(op & 1) {printf("%d\n", query(l, r, c));}else {add(l, r, c);}}return 0; }

6280. 數(shù)列分塊入門 4

想法

仿照題二，我們可以再引入一個數(shù)組來代表當(dāng)前塊的總和，之后的操作就變得簡單了。

代碼

/*Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> #define mp make_pair #define pb push_back #define endl '\n'using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii;const double pi = acos(-1.0); const double eps = 1e-7; const int inf = 0x3f3f3f3f;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }void print(ll x) {if(x < 10) {putchar(x + 48);return ;}print(x / 10);putchar(x % 10 + 48); }const int N = 1e5 + 10;ll a[N], sum[N], tag[N];int n, block, bl[N];void update(int l, int r, int x) {for(int i = l; i <= bl[l] * block && i <= r; i++) {a[i] += x;sum[bl[i]] += x;}if(bl[l] != bl[r]) {for(int i = (bl[r] - 1) * block + 1; i <= r; i++) {a[i] += x;sum[bl[i]] += x;}}for(int i = bl[l] + 1; i <= bl[r] - 1; i++)tag[i] += x; }int query(int l, int r, int mod) {ll ans = 0;for(int i = l; i <= bl[l] * block && i <= r; i++) {ans = (ans + a[i] + tag[bl[i]]) % mod;}if(bl[l] != bl[r]) {for(int i = (bl[r] - 1) * block + 1; i <= r; i++) {ans = (ans + a[i] + tag[bl[i]]) % mod;}}for(int i = bl[l] + 1; i <= bl[r] - 1; i++) {ans = (ans + sum[i] + tag[i] * block) % mod;}return ans; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);n = read(); block = sqrt(n);for(int i = 1; i <= n; i++) {a[i] = read();bl[i] = (i + block - 1) / block;sum[bl[i]] += a[i];}for(int i = 1; i <= n; i++) {int op = read(), l = read(), r = read(), c = read();if(op & 1) {printf("%d\n", query(l, r, c + 1));}else {update(l, r, c);}}return 0; }

6281. 數(shù)列分塊入門 5

想法

一開始看到這個題目感覺分塊無從下手啊，區(qū)間開方操作，結(jié)果一看他們ac代碼，原來是開根號，，，

既然是開根號那就簡單了，學(xué)過線段樹應(yīng)該寫過這類題，我們只要加一個區(qū)間tag來標記區(qū)間內(nèi)所有的數(shù)是否全部變成0和1即可。然后再加一個區(qū)間和，對于tag標記為，區(qū)間所有的數(shù)都是0 和1的我們可以直接查詢區(qū)間和，也可以跳過他的開方顯然有$\sqrt{1}=1$， $\sqrt{0}=0$

代碼

/*Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> #define mp make_pair #define pb push_back #define endl '\n'using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii;const double pi = acos(-1.0); const double eps = 1e-7; const int inf = 0x3f3f3f3f;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }void print(ll x) {if(x < 10) {putchar(x + 48);return ;}print(x / 10);putchar(x % 10 + 48); }const int N = 1e5 + 10;int a[N], sum[N], tag[N];int n, block, bl[N];void update(int l, int r) {for(int i = l; i <= r && i <= bl[l] * block; i++) {if(a[i] == 0 || a[i] == 1) continue;sum[bl[i]] -= a[i];a[i] = sqrt(a[i]);sum[bl[i]] += a[i];if(a[i] == 1 || a[i] == 0) tag[bl[i]]++;}if(bl[l] != bl[r]) {for(int i = (bl[r] - 1) * block + 1; i <= r; i++) {if(a[i] == 0 || a[i] == 1) continue;sum[bl[i]] -= a[i];a[i] = sqrt(a[i]);sum[bl[i]] += a[i];if(a[i] == 1 || a[i] == 0) tag[bl[i]]++;}}for(int i = bl[l] + 1; i <= bl[r] - 1; i++) {if(tag[i] == block) continue;else {for(int j = (i - 1) * block + 1; j <= i * block; j++) {if(a[j] == 0 || a[j] == 1) continue;sum[bl[j]] -= a[j];a[j] = sqrt(a[j]);sum[bl[j]] += a[j];if(a[i] == 1 || a[i] == 0) tag[bl[i]]++;}}} }int query(int l, int r) {int ans = 0;for(int i = l; i <= r && i <= bl[l] * block; i++)ans += a[i];if(bl[l] != bl[r]) {for(int i = (bl[r] - 1) * block + 1; i <= r; i++)ans += a[i];}for(int i = bl[l] + 1; i <= bl[r] - 1; i++) {if(tag[i] == block) ans += sum[i];else {for(int j = (i - 1) * block + 1; j <= i * block; j++)ans += a[j];}}return ans; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);n = read(); block = sqrt(n);for(int i = 1; i <= n; i++) {a[i] = read();bl[i] = (i + block - 1) / block;sum[bl[i]] += a[i];if(a[i] == 0 || a[i] == 1) tag[bl[i]]++;}for(int i = 1; i <= n; i++) {int op = read(), l = read(), r = read(), c = read();if(op & 1) {printf("%d\n", query(l, r));}else {update(l, r);}}return 0; }

6282. 數(shù)列分塊入門 6

想法

這里引入了一個暴力的$rebuild$，不愧是分塊，依舊是如此的暴力。

代碼

/*Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> #define mp make_pair #define pb push_back #define endl '\n'using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii;const double pi = acos(-1.0); const double eps = 1e-7; const int inf = 0x3f3f3f3f;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }void print(ll x) {if(x < 10) {putchar(x + 48);return ;}print(x / 10);putchar(x % 10 + 48); }const int N = 2e5 + 10;int value[N], n, m, block;vector<int> a[N];pii query(int x) {int now = 1;while(x > a[now].size()) {x -= a[now].size(), now++;}return mp(now, x - 1); }void rebuild() {int num = 0;for(int i = 1; i <= m; i++) {for(int j = 0; j < a[i].size(); j++) {value[++num] = a[i][j];}a[i].clear();//注意一定要clear，我就在這里找bug找了半小時。}block = sqrt(num), m = (num + block - 1) / block;for(int i = 1; i <= num; i++) {a[(i + block - 1) / block].pb(value[i]);} }void insert(int pos, int value) {pii p = query(pos);a[p.first].insert(a[p.first].begin() + p.second, value);if(a[p.first].size() > 20 * block)rebuild(); }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);n = read();block = sqrt(n), m = (n + block - 1) / block;for(int i = 1; i <= n; i++) {value[i] = read();a[(i + block - 1) / block].pb(value[i]);}for(int i = 1; i <= n; i++) {int op = read(), l = read(), r = read(), c = read();if(op & 1) {pii ans = query(r);printf("%d\n", a[ans.first][ans.second]);}else {insert(l, r);}}return 0; }

6283. 數(shù)列分塊入門 7

想法

暴力兩頭，區(qū)間操作中間。

代碼

/*Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> #define mp make_pair #define pb push_back #define endl '\n'using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii;const double pi = acos(-1.0); const double eps = 1e-7; const int inf = 0x3f3f3f3f;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }void print(ll x) {if(x < 10) {putchar(x + 48);return ;}print(x / 10);putchar(x % 10 + 48); }const int N = 1e5 + 10, mod = 1e4 + 7;int a[N], add[N], mult[N], bl[N], n, block;void init(int bl) {for(int i = (bl - 1) * block + 1; i <= bl * block; i++) {a[i] = (a[i] * mult[bl]) % mod;a[i] = (a[i] + add[bl]) % mod;}mult[bl] = 1, add[bl] = 0; }void Add(int l, int r, int x) {init(bl[l]);for(int i = l; i <= r && i <= bl[l] * block; i++)a[i] = (a[i] + x) % mod;if(bl[l] != bl[r]) {init(bl[r]);for(int i = (bl[r] - 1) * block + 1; i <= r; i++)a[i] = (a[i] + x) % mod;}for(int i = bl[l] + 1; i <= bl[r] - 1; i++)add[i] = (add[i] + x) % mod; }void Mult(int l, int r, int x) {init(bl[l]);for(int i = l; i <= r && i <= bl[l] * block; i++)a[i] = (a[i] * x) % mod;if(bl[l] != bl[r]) {init(bl[r]);for(int i = (bl[r] - 1) * block + 1; i <= r; i++)a[i] = (a[i] * x) % mod;}for(int i = bl[l] + 1; i <= bl[r] - 1; i++)mult[i] = (mult[i] * x) % mod, add[i] = (add[i] * x) % mod; }int query(int pos) {return (((a[pos] * mult[bl[pos]])) % mod + add[bl[pos]]) % mod; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);n = read();block = sqrt(n);for(int i = 1; i <= n; i++) {a[i] = read() % mod;bl[i] = (i + block - 1) / block;mult[i] = 1;}for(int i = 1; i <= n; i++) {int op = read(), l = read(), r = read(), x = read();if(!op) {Add(l, r, x);} else if(op & 1) {Mult(l, r, x);} else {printf("%d\n", query(r));}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的数列分块入门 (1 ~ 7)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。