其实是复习笔记
T1:区间加法,单点查值
做法:两边暴力加法,整块加法标记,复杂度 O(n\sqrt{n})
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX_N 50005
using namespace std;
int n, blo;
int w[MAX_N];
int bl[MAX_N];
int tag[MAX_N];
void add(int a, int b, int x) {
for (int i = a; i <= min(b, bl[a] * blo); i++) {
w[i] += x;
}
if (bl[a] != bl[b]) {
for (int i = (bl[b] - 1) * blo + 1; i <= b; i++) {
w[i] += x;
}
}
for (int i = bl[a] + 1; i < bl[b]; i++) {
tag[i] += x;
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", w + i);
}
blo = (int)sqrt(n) + 1;
for (int i = 1; i <= n; i++) {
bl[i] = (i - 1) / blo + 1;
}
int op, x, y, z;
for (int i = 1; i <= n; i++) {
scanf("%d%d%d%d", &op, &x, &y, &z);
if (op == 0) {
add(x, y, z);
} else {
printf("%d\n", w[y] + tag[bl[y]]);
}
}
}
T2:区间加法,区间查询小于某个值的元素个数
做法:每个整块开个vector,里面排好序。两边暴力统计并重建vector,整块顺序不变,查询时lower_bound,复杂度 O(n\sqrt{n}\log{\sqrt{n}})
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#define MAX_N 50005
#define L(x) ((bl[x] - 1) * blo + 1)
#define R(x) (bl[x] * blo)
#define LB(x) (((x)-1) * blo + 1)
#define RB(x) ((x)*blo)
using namespace std;
int n, blo;
int w[MAX_N];
int bl[MAX_N];
int tag[MAX_N];
vector<int> v[MAX_N];
void bsort(int b) {
v[b].clear();
for (int i = LB(b); i <= min(n, RB(b)); i++) {
v[b].push_back(w[i]);
}
sort(v[b].begin(), v[b].end());
}
void add(int a, int b, int x) {
for (int i = a; i <= min(b, R(a)); i++) {
w[i] += x;
}
bsort(bl[a]);
if (bl[a] != bl[b]) {
for (int i = L(b); i <= b; i++) {
w[i] += x;
}
bsort(bl[b]);
}
for (int i = bl[a] + 1; i < bl[b]; i++) {
tag[i] += x;
}
}
int getans(int a, int b, int x) {
int cnt = 0;
for (int i = a; i <= min(b, R(a)); i++) {
cnt += (w[i] + tag[bl[a]] < x);
}
if (bl[a] != bl[b]) {
for (int i = L(b); i <= b; i++) {
cnt += (w[i] + tag[bl[b]] < x);
}
}
for (int i = bl[a] + 1; i < bl[b]; i++) {
cnt += (lower_bound(v[i].begin(), v[i].end(), x - tag[i]) - v[i].begin());
}
return cnt;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", w + i);
}
blo = (int)sqrt(n) + 1;
for (int i = 1; i <= n; i++) {
bl[i] = (i - 1) / blo + 1;
}
for (int i = 1; i <= bl[n]; i++) {
bsort(i);
}
int op, x, y, z;
for (int i = 1; i <= n; i++) {
scanf("%d%d%d%d", &op, &x, &y, &z);
if (op == 0) {
add(x, y, z);
} else {
printf("%d\n", getans(x, y, z * z));
}
}
}
T3:区间加法,区间查询某个值的前驱
做法:同T2
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#define MAX_N 100005
#define L(x) ((bl[x] - 1) * blo + 1)
#define R(x) (bl[x] * blo)
#define LB(x) (((x)-1) * blo + 1)
#define RB(x) ((x)*blo)
using namespace std;
int n, blo;
int w[MAX_N];
int bl[MAX_N];
int tag[MAX_N];
vector<int> v[MAX_N];
void bsort(int b) {
v[b].clear();
for (int i = LB(b); i <= min(n, RB(b)); i++) {
v[b].push_back(w[i]);
}
sort(v[b].begin(), v[b].end());
}
void add(int a, int b, int x) {
for (int i = a; i <= min(b, R(a)); i++) {
w[i] += x;
}
bsort(bl[a]);
if (bl[a] != bl[b]) {
for (int i = L(b); i <= b; i++) {
w[i] += x;
}
bsort(bl[b]);
}
for (int i = bl[a] + 1; i < bl[b]; i++) {
tag[i] += x;
}
}
int getans(int a, int b, int x) {
int ans = -1;
for (int i = a; i <= min(b, R(a)); i++) {
if (w[i] + tag[bl[a]] < x) {
ans = max(ans, w[i] + tag[bl[a]]);
}
}
if (bl[a] != bl[b]) {
for (int i = L(b); i <= b; i++) {
if (w[i] + tag[bl[b]] < x) {
ans = max(ans, w[i] + tag[bl[b]]);
}
}
}
for (int i = bl[a] + 1; i < bl[b]; i++) {
int t = lower_bound(v[i].begin(), v[i].end(), x - tag[i]) - v[i].begin();
if (t > 0) {
ans = max(ans, v[i][t - 1] + tag[i]);
}
}
return ans;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", w + i);
}
blo = (int)sqrt(n) + 1;
for (int i = 1; i <= n; i++) {
bl[i] = (i - 1) / blo + 1;
}
for (int i = 1; i <= bl[n]; i++) {
bsort(i);
}
int op, x, y, z;
for (int i = 1; i <= n; i++) {
scanf("%d%d%d%d", &op, &x, &y, &z);
if (op == 0) {
add(x, y, z);
} else {
printf("%d\n", getans(x, y, z));
}
}
}
T4:区间加法,区间求和
做法:每个整块记录全体增加的值和整块总和(不算全体增加的值),两边暴力维护,复杂度 O(n\sqrt{n})
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX_N 50005
#define L(x) ((bl[x] - 1) * blo + 1)
#define R(x) (bl[x] * blo)
#define LB(x) (((x)-1) * blo + 1)
#define RB(x) ((x)*blo)
#define int long long
using namespace std;
int n, blo;
int w[MAX_N];
int bl[MAX_N];
int sum[MAX_N];
int tag[MAX_N];
void add(int a, int b, int x) {
for (int i = a; i <= min(b, R(a)); i++) {
w[i] += x, sum[bl[a]] += x;
}
if (bl[a] != bl[b]) {
for (int i = L(b); i <= b; i++) {
w[i] += x, sum[bl[b]] += x;
}
}
for (int i = bl[a] + 1; i < bl[b]; i++) {
tag[i] += x;
}
}
int getsum(int a, int b, int p) {
int ans = 0;
for (int i = a; i <= min(b, R(a)); i++) {
ans = (ans + w[i] + tag[bl[a]]) % p;
}
if (bl[a] != bl[b]) {
for (int i = L(b); i <= b; i++) {
ans = (ans + w[i] + tag[bl[b]]) % p;
}
}
for (int i = bl[a] + 1; i < bl[b]; i++) {
ans = (ans + sum[i] + tag[i] * blo % p) % p;
}
return ans;
}
signed main() {
scanf("%lld", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", w + i);
}
blo = (int)sqrt(n) + 1;
for (int i = 1; i <= n; i++) {
bl[i] = (i - 1) / blo + 1;
sum[bl[i]] += w[i];
}
int op, x, y, z;
for (int i = 1; i <= n; i++) {
scanf("%lld%lld%lld%lld", &op, &x, &y, &z);
if (op == 0) {
add(x, y, z);
} else {
printf("%lld\n", getsum(x, y, z + 1));
}
}
}
T5:区间开方,区间求和
做法:有性质「大于1的数经过不超过5次开方后会变成1,0无论怎样开方都是0」,所以记录一下每个块是否是全0/1,对于不是全0/1的块暴力开方,复杂度 O(n\sqrt{n})
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX_N 50005
#define L(x) ((bl[x] - 1) * blo + 1)
#define R(x) (bl[x] * blo)
#define LB(x) (((x)-1) * blo + 1)
#define RB(x) ((x)*blo)
using namespace std;
int n, blo;
int w[MAX_N];
int bl[MAX_N];
int sum[MAX_N];
int cnt[MAX_N];
void sqrts(int a, int b) {
for (int i = a; i <= b; i++) {
sum[bl[i]] -= w[i];
cnt[bl[i]] -= (w[i] <= 1);
w[i] = sqrt(w[i]);
sum[bl[i]] += w[i];
cnt[bl[i]] += (w[i] <= 1);
}
}
void upd(int a, int b) {
sqrts(a, min(b, R(a)));
if (bl[a] != bl[b]) {
sqrts(L(b), b);
}
for (int i = bl[a] + 1; i < bl[b]; i++) {
if (cnt[i] < blo) {
sqrts(LB(i), RB(i));
}
}
}
int getsum(int a, int b) {
int ans = 0;
for (int i = a; i <= min(b, R(a)); i++) {
ans += w[i];
}
if (bl[a] != bl[b]) {
for (int i = L(b); i <= b; i++) {
ans += w[i];
}
}
for (int i = bl[a] + 1; i < bl[b]; i++) {
ans += sum[i];
}
return ans;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", w + i);
}
blo = (int)sqrt(n) + 1;
for (int i = 1; i <= n; i++) {
bl[i] = (i - 1) / blo + 1;
sum[bl[i]] += w[i];
cnt[bl[i]] += (w[i] <= 1);
}
int op, x, y, z;
for (int i = 1; i <= n; i++) {
scanf("%d%d%d%d", &op, &x, &y, &z);
if (op == 0) {
upd(x, y);
} else {
printf("%d\n", getsum(x, y));
}
}
}
T6:单点插入,单点查询
做法:每插入 \sqrt{n} 次,重新 O(n) 建块,总复杂度 O(n\sqrt{n})
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <vector>
#define MAX_N 200005
using namespace std;
int n, blo, cnt;
int w[MAX_N];
vector<int> v[MAX_N];
void ins(int k, int x) {
for (int i = 1; i <= cnt; i++) {
if (k <= v[i].size()) {
v[i].insert(v[i].begin() + (k - 1), x);
return;
}
k -= v[i].size();
}
}
int getans(int k) {
for (int i = 1; i <= cnt; i++) {
if (k <= v[i].size()) {
return v[i][k - 1];
}
k -= v[i].size();
}
return 0;
}
void rebuild() {
int tot = 0;
for (int i = 1; i <= cnt; i++) {
for (int j = 0; j < v[i].size(); j++) {
w[++tot] = v[i][j];
}
v[i].clear();
}
blo = (int)sqrt(tot) + 1;
for (int i = 1; i <= tot; i++) {
cnt = (i - 1) / blo + 1;
v[cnt].push_back(w[i]);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", w + i);
}
blo = (int)sqrt(n) + 1;
for (int i = 1; i <= n; i++) {
cnt = (i - 1) / blo + 1;
v[cnt].push_back(w[i]);
}
int op, x, y, z, c = 0;
for (int i = 1; i <= n; i++) {
scanf("%d%d%d%d", &op, &x, &y, &z);
if (op == 0) {
ins(x, y);
if (++c >= (int)sqrt(n) + 1) {
rebuild();
c = 0;
}
} else {
printf("%d\n", getans(y));
}
}
}
T7:区间加法,区间乘法,单点查值
做法:整块记录加法和乘法标记(先乘后加),两边先暴力重置所在块的标记,然后再暴力修改
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX_N 100005
#define MOD 10007
#define L(x) ((bl[x] - 1) * blo + 1)
#define R(x) (bl[x] * blo)
#define LB(x) (((x)-1) * blo + 1)
#define RB(x) ((x)*blo)
using namespace std;
int n, blo;
int w[MAX_N];
int bl[MAX_N];
int ta[MAX_N];
int tm[MAX_N];
void reset(int b) {
for (int i = LB(b); i <= min(n, RB(b)); i++) {
w[i] = (w[i] * tm[b] + ta[b]) % MOD;
}
ta[b] = 0, tm[b] = 1;
}
void add(int a, int b, int x) {
reset(bl[a]);
for (int i = a; i <= min(b, R(a)); i++) {
w[i] = (w[i] + x) % MOD;
}
if (bl[a] != bl[b]) {
reset(bl[b]);
for (int i = L(b); i <= b; i++) {
w[i] = (w[i] + x) % MOD;
}
}
for (int i = bl[a] + 1; i < bl[b]; i++) {
ta[i] = (ta[i] + x) % MOD;
}
}
void mul(int a, int b, int x) {
reset(bl[a]);
for (int i = a; i <= min(b, R(a)); i++) {
w[i] = w[i] * x % MOD;
}
if (bl[a] != bl[b]) {
reset(bl[b]);
for (int i = L(b); i <= b; i++) {
w[i] = w[i] * x % MOD;
}
}
for (int i = bl[a] + 1; i < bl[b]; i++) {
ta[i] = ta[i] * x % MOD;
tm[i] = tm[i] * x % MOD;
}
}
int getans(int k) {
return (w[k] * tm[bl[k]] + ta[bl[k]]) % MOD;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", w + i);
}
blo = (int)sqrt(n) + 1;
for (int i = 1; i <= n; i++) {
bl[i] = (i - 1) / blo + 1;
}
for (int i = 1; i <= bl[n]; i++) {
tm[i] = 1;
}
int op, x, y, z;
for (int i = 1; i <= n; i++) {
scanf("%d%d%d%d", &op, &x, &y, &z);
if (op == 0) {
add(x, y, z);
} else if (op == 1) {
mul(x, y, z);
} else {
printf("%d\n", getans(y));
}
}
}
T8:区间询问等于某个值的元素个数,并同时将该区间所有数改为该值
做法:
每个整块记录一下这个块是否被全体置为某个值。
修改时,对于两边所在的块,如果有全置标记,则将标记暴力下放到每个元素上,然后再暴力修改;对于整块,直接修改该块的全置标记。
查询时,如果没有全置标记就暴力查询,有的话就 O(1) 判断。
复杂度分析:
先假设一开始所有的数都是同一个值
每次修改操作显然是 O(\sqrt{n}) 的,并且每次修改操作至多会为接下来增加2倍的「暴力单块查询复杂度」即 O(\sqrt{n})
而除去暴力单块查询的区间查询操作的单次复杂度为 O(\sqrt{n})
所以该假设下的总复杂度为 O(n\sqrt{n})
而将假设「一开始所有的数都是同一个值」变为题中的情况,相当于一开始全部数都一样,然后做了 n 次修改操作,所以除去假设后的复杂度还是 O(n\sqrt{n})
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX_N 100005
#define L(x) ((bl[x] - 1) * blo + 1)
#define R(x) (bl[x] * blo)
#define LB(x) (((x)-1) * blo + 1)
#define RB(x) ((x)*blo)
using namespace std;
int n, blo;
int w[MAX_N];
int bl[MAX_N];
int tag[MAX_N];
void reset(int b) {
if (tag[b] != -1) {
for (int i = LB(b); i <= min(n, RB(b)); i++) {
w[i] = tag[b];
}
tag[b] = -1;
}
}
void upd(int a, int b, int x) {
reset(bl[a]);
for (int i = a; i <= min(b, R(a)); i++) {
w[i] = x;
}
if (bl[a] != bl[b]) {
reset(bl[b]);
for (int i = L(b); i <= b; i++) {
w[i] = x;
}
}
for (int i = bl[a] + 1; i < bl[b]; i++) {
tag[i] = x;
}
}
int getblo(int b, int x) {
int cnt = 0;
for (int i = LB(b); i <= min(n, RB(b)); i++) {
cnt += (w[i] == x);
}
tag[b] = x;
return cnt;
}
int getans(int a, int b, int x) {
int ans = 0;
for (int i = a; i <= min(b, R(a)); i++) {
ans += (tag[bl[a]] == x || (tag[bl[a]] == -1 && w[i] == x));
}
if (bl[a] != bl[b]) {
for (int i = L(b); i <= b; i++) {
ans += (tag[bl[b]] == x || (tag[bl[b]] == -1 && w[i] == x));
}
}
for (int i = bl[a] + 1; i < bl[b]; i++) {
if (tag[i] != -1) {
ans += blo * (tag[i] == x);
} else {
ans += getblo(i, x);
}
}
return ans;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", w + i);
}
blo = (int)sqrt(n) + 1;
for (int i = 1; i <= n; i++) {
bl[i] = (i - 1) / blo + 1;
}
memset(tag, -1, sizeof(tag));
int x, y, z;
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &x, &y, &z);
printf("%d\n", getans(x, y, z));
upd(x, y, z);
}
}
T9:离线区间众数
用莫队写更方便一些,所以这里就咕了qwq