无语，调试的煎熬..
数列分块入门 9
求区间的最小的出现最多次数的数。
这里很显然先处理出块与块之间的最小众数，然后两边的残余块暴力就行。
如何高效找两边的，这里就用到了二分，首先要对数离散化，然后值的容器里存位置，然后直接用查询的区间去二分，这样就能找到给定的区间里有多少个了。
PS：预处理写错了找了好久。。一开始写到了if里面，后面发现这样有的块就更新不到了。~~
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> pii; const int N = 1e5 + 5; const int M = 2000 + 5; const LL Mod = 10007; #define pi acos(-1) #define INF 1e18 + 5 #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO { inline int read() { int x = 0, f = 1; 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 x * f; } } using namespace FASTIO; int n, sz, bl[N], a[N], b[N], len; int mx[M][M], mxnum[M][M], num[N], mp[N]; bool vis[N]; vector<int> vec[N]; void init(int x) { for(int i = 1;i <= len;++i) num[i] = 0; int maxx = 0, mxpos = 0; for (int i = (x - 1) * sz + 1; i <= n; ++i) { num[a[i]]++; if (num[a[i]] > maxx || (num[a[i]] == maxx && a[i] < mxpos)) { maxx = num[a[i]]; mxpos = a[i]; } mx[x][bl[i]] = mxpos; mxnum[x][bl[i]] = maxx; } } int query(int L, int r) { int maxx = 0, mxpos = 0; for (int i = 1; i <= len; ++i) num[i] = vis[i] = 0; if (bl[L] + 1 <= bl[r] - 1) { maxx = mxnum[bl[L] + 1][bl[r] - 1]; mxpos = mx[bl[L] + 1][bl[r] - 1]; } for (int i = L; i <= min(n, bl[L] * sz); ++i) { if (vis[a[i]] == 0) { int pos2 = upper_bound(vec[a[i]].begin(), vec[a[i]].end(), r) - vec[a[i]].begin(); int pos1 = lower_bound(vec[a[i]].begin(), vec[a[i]].end(), L) - vec[a[i]].begin(); num[a[i]] = pos2 - pos1; vis[a[i]] = 1; } if (num[a[i]] > maxx || (num[a[i]] == maxx && a[i] < mxpos)) { maxx = num[a[i]]; mxpos = a[i]; } } if (bl[L] * sz + 1 > r) return mp[mxpos]; for (int i = (bl[r] - 1) * sz + 1; i <= r; ++i) { if (vis[a[i]] == 0) { int pos2 = upper_bound(vec[a[i]].begin(), vec[a[i]].end(), r) - vec[a[i]].begin(); int pos1 = lower_bound(vec[a[i]].begin(), vec[a[i]].end(), L) - vec[a[i]].begin(); num[a[i]] = pos2 - pos1; vis[a[i]] = 1; } if (num[a[i]] > maxx || (num[a[i]] == maxx && a[i] < mxpos)) { maxx = num[a[i]]; mxpos = a[i]; } } return mp[mxpos]; } int main() { n = read(); //sz = sqrt(n); sz = 150; int tot = 0; for (int i = 1; i <= n; ++i) { a[i] = read(); b[++tot] = a[i]; } sort(b + 1, b + tot + 1); len = unique(b + 1, b + tot + 1) - b - 1; for (int i = 1; i <= n; ++i) { int x = lower_bound(b + 1, b + len + 1, a[i]) - b; mp[x] = a[i]; a[i] = x; } for (int i = 1; i <= n; ++i) { bl[i] = (i - 1) / sz + 1; vec[a[i]].push_back(i); } for (int i = 1; i <= n / sz + 1; ++i) { init(i); } for (int i = 1; i <= n; ++i) { int L, r; L = read(), r = read(); printf("%d ", query(L, r)); } return 0; } /* 12 10 9 23 45 31 44 44 23 9 5 6 6 1 2 1 3 1 4 1 5 1 6 1 7 1 8 */
数列分块入门 8
查找区间某个数出现的次数并修改，这里其实是偏暴力的做法，因为最多标记一次之后就很快了。
一开始一直觉得会超时，这种复杂度好难估算啊~。。
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> pii; const int N = 1e5 + 5; const int M = 1e3; const LL Mod = 10007; #define pi acos(-1) #define INF 1e18 + 5 #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO { inline int read() { int x = 0, f = 1; 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 x * f; } } using namespace FASTIO; int n, sz, bl[N], num[N], a[N]; int solve(int L, int r, int c) { int ans = 0; int st = (bl[L] - 1) * sz + 1; int ed = min(n, bl[L] * sz); if (num[bl[L]] != 0) { for (int i = st; i <= ed; ++i) a[i] = num[bl[L]]; num[bl[L]] = 0; } for (int i = L; i <= min(bl[L] * sz, r); ++i) { if (a[i] == c) ans++; a[i] = c; } L = bl[L] * sz + 1; if (L > r) return ans; while (bl[L] != bl[r]) { if (num[bl[L]] != 0) { if (num[bl[L]] == c) { int st = (bl[L] - 1) * sz + 1; int ed = min(n, bl[L] * sz); ans += ed - st + 1; } } else { int st = (bl[L] - 1) * sz + 1; int ed = bl[L] * sz; for (int j = st; j <= ed; ++j) { if (a[j] == c) ans++; } } num[bl[L]] = c; L = bl[L] * sz + 1; } st = (bl[L] - 1) * sz + 1; ed = min(n, bl[L] * sz); if (num[bl[L]] != 0) { for (int i = st; i <= ed; ++i) a[i] = num[bl[L]]; num[bl[L]] = 0; } for (int i = L; i <= r; ++i) { if (a[i] == c) ans++; a[i] = c; } return ans; } int main() { n = read(); sz = sqrt(n); for (int i = 1; i <= n; ++i) a[i] = read(); for (int i = 1; i <= n; ++i) { bl[i] = (i - 1) / sz + 1; } for (int i = 1; i <= n; ++i) { int L, r, c; L = read(), r = read(), c = read(); printf("%d ", solve(L, r, c)); } return 0; }
数列分块入门 7
区间加乘，注意顺序的处理即可，想清楚其实不难。
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> pii; const int N = 1e5 + 5; const int M = 1e3; const LL Mod = 10007; #define pi acos(-1) #define INF 1e18 + 5 #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO { inline LL read() { LL x = 0, f = 1; 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 x * f; } } using namespace FASTIO; int n, sz, bl[N]; LL ADD[N], MUL[N], Size[N], a[N], link[M][M], pla[N]; void add(int L, int r, int c) { int st = (bl[L] - 1) * sz + 1; int ed = min(n, bl[L] * sz); for (int i = st; i <= ed; ++i) { link[bl[L]][pla[i]] = (link[bl[L]][pla[i]] * MUL[bl[L]]) % Mod; link[bl[L]][pla[i]] = (link[bl[L]][pla[i]] + ADD[bl[L]]) % Mod; } MUL[bl[L]] = 1; ADD[bl[L]] = 0; for (int i = L; i <= min(bl[L] * sz, r); ++i) { link[bl[L]][pla[i]] = (link[bl[L]][pla[i]] + c) % Mod; } L = bl[L] * sz + 1; if (L > r) return ; while (bl[L] != bl[r]) { ADD[bl[L]] = (ADD[bl[L]] + c) % Mod; L = bl[L] * sz + 1; } st = (bl[L] - 1) * sz + 1; ed = min(n, bl[L] * sz); for (int i = st; i <= ed; ++i) { link[bl[L]][pla[i]] = (link[bl[L]][pla[i]] * MUL[bl[L]]) % Mod; link[bl[L]][pla[i]] = (link[bl[L]][pla[i]] + ADD[bl[L]]) % Mod; } MUL[bl[L]] = 1; ADD[bl[L]] = 0; for (int i = L; i <= r; ++i) { link[bl[L]][pla[i]] = (link[bl[L]][pla[i]] + c) % Mod; } } void mul(int L, int r, int c) { int st = (bl[L] - 1) * sz + 1; int ed = min(n, bl[L] * sz); for (int i = st; i <= ed; ++i) { link[bl[L]][pla[i]] = (link[bl[L]][pla[i]] * MUL[bl[L]]) % Mod; link[bl[L]][pla[i]] = (link[bl[L]][pla[i]] + ADD[bl[L]]) % Mod; } MUL[bl[L]] = 1; ADD[bl[L]] = 0; for (int i = L; i <= min(bl[L] * sz, r); ++i) { link[bl[L]][pla[i]] = (link[bl[L]][pla[i]] * c) % Mod; } L = bl[L] * sz + 1; if (L > r) return ; while (bl[L] != bl[r]) { MUL[bl[L]] = (MUL[bl[L]] * c) % Mod; ADD[bl[L]] = (ADD[bl[L]] * c) % Mod; L = bl[L] * sz + 1; } st = (bl[L] - 1) * sz + 1; ed = min(n, bl[L] * sz); for (int i = st; i <= ed; ++i) { link[bl[L]][pla[i]] = (link[bl[L]][pla[i]] * MUL[bl[L]]) % Mod; link[bl[L]][pla[i]] = (link[bl[L]][pla[i]] + ADD[bl[L]]) % Mod; } MUL[bl[L]] = 1; ADD[bl[L]] = 0; for (int i = L; i <= r; ++i) { link[bl[L]][pla[i]] = (link[bl[L]][pla[i]] * c) % Mod; } } LL query(int pos) { int sum = 0, st = 1; while (st != 0) { int ma = sum + Size[st]; if (ma >= pos) { int tmp = pos - sum; //printf("mul is %lld add is %lld ",MUL[st],ADD[st]); return (link[st][tmp] * MUL[st] % Mod + ADD[st]) % Mod; } sum += Size[st]; st++; } } int main() { n = read(); sz = sqrt(n); for (int i = 1; i <= n; ++i) a[i] = read(); for (int i = 1; i <= n; ++i) { bl[i] = (i - 1) / sz + 1; link[bl[i]][++Size[bl[i]]] = a[i]; pla[i] = Size[bl[i]]; MUL[bl[i]] = 1; } for (int i = 1; i <= n; ++i) { int opt, L, r, c; opt = read(), L = read(), r = read(), c = read(); if (opt == 0) add(L, r, c); else if (opt == 1) mul(L, r, c); else printf("%lld ", query(r)); } return 0; } /* 7 1 2 2 3 9 3 2 0 1 3 1 1 1 4 4 0 1 7 2 2 1 6 6 1 2 6 4 2 1 6 6 */