学习笔记（二） 区间问题
一、ST表（RMQ或RGQ问题等）
ST算法处理静态空间的RMQ问题效率相当高，预处理时间复杂度 O(nlogn) ，查询时间复杂度 O(1)。思路同莫队算法类似，同为分块+处理，但是ST完全不支持修改，如果只有查询，ST查询效率远高于莫队。
思路：DP预处理（倍增法）+贪心查询
首先，ST需要分块，通过倍增思路分块。第一组全分为长度为1的块，第二组全分为长度为2的块，第三组长度为4，倍增地以此类推。注意这里的分块每个块之间不是完全互斥的，和归并排序中的分组完全相反，这里的分块是分别以每个元素为头找到长度为2^(组数-1) 的块，只要块的尾没到数组的结尾，就把每个元素都找到这样的块。如此，总共需要logn个块，用二维数组存储，应该类似于 dp[logn][n] 这样，dp[i][j] 代表第i+1组中以j为首元素的块，而记载的答案自然为要找的最大值或最小值。
然后，分块思路和存储方式找到了，第一组即 dp[0][j] 自然为原数组。通过转移方程:
dp[i][j]=min{dp[i-1][j],dp[i-1][j+2^(i-1)]}
递推得到全部的信息。转移方程代表第i+1组以j为首元素的块的最小值为上一组可以将其平分的两个块最小值的最小值。
因为最值是符合贪心的，所以只要两个小区间能完全覆盖住大区间（两个小区间重叠也可以），那么就可以贪心的递推。
最后便是如何查询了，按照上述所言，对于L到R之间的最值查询，len=R-L+1，只要找到两个小块重叠刚好完全覆盖这个长度就好，小块的长度x满足 x<=len<=2x 就好，即小块在第log(len)+1组。令k=log(lR-L+1)，那么答案就出来了：
ans=min{dp[k][L],dp[k][R-2^k+1]}
eg.洛谷P2880
附链接https://www.luogu.com.cn/problem/P2880
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define rep(i,l,r) for(register int i=l;i<=r;i++)
using namespace std;
const int N = 5e4 + 5;
const int INF = 0x3fffffff;
const double eps = 1e-6;
typedef long long ll;
const int modp = 1e6 + 37;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - 48;
ch = getchar();
}
return x * f;
}
int n, q;
int l, r;
int Log[N];
int dp1[100][N];
int dp2[100][N];
void init() {
Log[0] = -1;
rep(i, 1, n) Log[i] = Log[i >> 1] + 1;
rep(i, 1, Log[n]) {
rep(j, 1, n) {
if (j + (1 << i) - 1 <= n)
dp1[i][j] = min(dp1[i - 1][j], dp1[i - 1][j + (1 << (i - 1))]);
}
}
rep(i, 1, Log[n]) {
rep(j, 1, n) {
if (j + (1 << i) - 1 <= n)
dp2[i][j] = max(dp2[i - 1][j], dp2[i - 1][j + (1 << (i - 1))]);
}
}
}
void solve() {
int mina, maxa;
int k = Log[r - l + 1];
mina = min(dp1[k][l], dp1[k][r - (1 << k) + 1]);
maxa = max(dp2[k][l], dp2[k][r - (1 << k) + 1]);
cout << maxa - mina << endl;
}
int main() {
ios::sync_with_stdio(0), cout.tie(0), cin.tie(0);
n=read();
q=read();
rep(i, 1, n) dp1[0][i] = dp2[0][i] = read();
init();
while (q--) {
l = read();
r = read();
solve();
}
return 0;
}
同理，求取区间最大公约数问题一样解法。对于离线无需维护数组时用ST算法时间复杂度短且非常好写（只需记住两个dp转移方程就好）。
二、线段树
hdu 4027
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define rep(i,l,r) for(register int i=l;i<=r;i++)
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3fffffff;
const double eps = 1e-6;
typedef long long ll;
const int modp = 1e6 + 37;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - 48;
ch = getchar();
}
return x * f;
}
ll n, m;
ll a[N];
ll tree[N << 2];
ll ls(ll x) {
return x << 1;
}
ll rs(ll x) {
return x << 1 | 1;
}
void push_up(ll p) {
tree[p] = tree[ls(p)] + tree[rs(p)];
}
void addtag(ll p, ll pl, ll pr) {
if (tree[p] > (pr - pl + 1)) {
if (pl == pr) {
tree[p] = (ll)sqrt(tree[p]);
return;
}
ll mid = (pl + pr) >> 1;
addtag(ls(p), pl, mid);
addtag(rs(p), mid + 1, pr);
push_up(p);
}
}
ll build(ll p, ll pl, ll pr) {
if (pr == pl) {
tree[p] = a[pl];
return tree[p];
}
ll mid = (pl + pr) >> 1;
tree[p] = build(ls(p), pl, mid) + build(rs(p), mid + 1, pr);
return tree[p];
}
void updata(ll l, ll r, ll p, ll pl, ll pr) {
if (l <= pl && r >= pr) {
addtag(p, pl, pr);
return;
}
ll mid = (pl + pr) >> 1;
if (l <= mid)
updata(l, r, ls(p), pl, mid);
if (r > mid)
updata(l, r, rs(p), mid + 1, pr);
push_up(p);
}
ll sum(ll l, ll r, ll p, ll pl, ll pr) {
if (l <= pl && r >= pr) {
return tree[p];
}
ll res = 0;
ll mid = (pl + pr) >> 1;
if (l <= mid)
res += sum(l, r, ls(p), pl, mid);
if (r > mid)
res += sum(l, r, rs(p), mid + 1, pr);
return res;
}
int main() {
//ios::sync_with_stdio(0), cout.tie(0), cin.tie(0);
ll k = 0;
while (scanf("%lld", &n) != EOF) {
for (ll i = 1; i <= n; i++)
scanf("%lld", &a[i]);
build(1, 1, n);
scanf("%lld", &m);
++k;
cout << "Case #" << k << ":" << endl;
while (m--) {
ll t, x, y;
scanf("%lld%lld%lld", &t, &x, &y);
if (x > y)
swap(x, y);
if (t == 0)
updata(x, y, 1, 1, n);
else
cout << sum(x, y, 1, 1, n) << endl;
}
}
return 0;
}
hdu 4578
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define rep(i,l,r) for(register int i=l;i<=r;i++)
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3fffffff;
const double eps = 1e-6;
typedef int ll;
const int modp = 10007;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - 48;
ch = getchar();
}
return x * f;
}
ll n, m;
ll tree1[N << 2];
ll tag1[N << 2];
ll tree2[N << 2];
ll tag2[N << 2];
ll tree3[N << 2];
ll tag3[N << 2];
ll ls(ll x) {
return x << 1;
}
ll rs(ll x) {
return x << 1 | 1;
}
void push_up(ll p) {
tree1[p] = (tree1[ls(p)] + tree1[rs(p)]) % modp;
tree2[p] = (tree2[ls(p)] + tree2[rs(p)]) % modp;
tree3[p] = (tree3[ls(p)] + tree3[rs(p)]) % modp;
}
void addtag1(ll p, ll d, ll pl, ll pr) { //加法稍麻烦，参考公式
tree3[p] = ((tree3[p] + (pr - pl + 1) * d % modp * d % modp * d % modp) % modp + 3 * d *
(tree2[p] + tree1[p] * d % modp) % modp) % modp;
tree2[p] = (tree2[p] + (pr - pl + 1) * d % modp * d % modp + 2 * tree1[p] * d % modp) % modp;
tree1[p] = (tree1[p] + (pr - pl + 1) * d % modp) % modp;
tag1[p] = (tag1[p] + d) % modp;
}
void addtag2(ll p, ll d, ll pl, ll pr) { //乘法注意，如果有加法标记，将加法标记也乘上乘法标记
tag1[p] = (tag1[p] * d) % modp;
tag2[p] = (tag2[p] * d) % modp;
tree1[p] = tree1[p] * d % modp;
tree2[p] = tree2[p] * d % modp * d % modp;
tree3[p] = tree3[p] * d % modp * d % modp * d % modp;
}
void addtag3(ll p, ll d, ll pl, ll pr) { //change时清空加法和乘法标记
tag1[p] = tag3[p] = 0;
tag2[p] = 1;
tag3[p] = d;
tree1[p] = (pr - pl + 1) * d % modp;
tree2[p] = (pr - pl + 1) * d % modp * d % modp;
tree3[p] = (pr - pl + 1) * d % modp * d % modp * d % modp;
}
void pd1(ll p, ll pl, ll pr) { //加
if (tag1[p]) {
ll mid = (pl + pr) >> 1;
addtag1(ls(p), tag1[p], pl, mid);
addtag1(rs(p), tag1[p], mid + 1, pr);
tag1[p] = 0;
}
}
void pd2(ll p, ll pl, ll pr) { //乘
if (tag2[p] != 1) {
ll mid = (pl + pr) >> 1;
addtag2(ls(p), tag2[p], pl, mid);
addtag2(rs(p), tag2[p], mid + 1, pr);
tag2[p] = 1;
}
}
void pd3(ll p, ll pl, ll pr) { //change
if (tag3[p]) {
ll mid = (pl + pr) >> 1;
addtag3(ls(p), tag3[p], pl, mid);
addtag3(rs(p), tag3[p], mid + 1, pr);
tag3[p] = 0;
}
}
void push_down(ll p, ll pl, ll pr) { //先change然后再乘最后加
pd3(p, pl, pr);
pd2(p, pl, pr);
pd1(p, pl, pr);
}
void build(ll p, ll pl, ll pr) {
tag1[p] = tag3[p] = 0;
tag2[p] = 1; //注意乘法标记初值为1
if (pr == pl) {
tree1[p] = tree2[p] = tree3[p] = 0;
return;
}
ll mid = (pl + pr) >> 1;
build(ls(p), pl, mid);
build(rs(p), mid + 1, pr);
push_up(p);
}
void updata(ll l, ll r, ll d, ll p, ll pl, ll pr, ll k) {
if (l <= pl && r >= pr) {
if (k == 1)
addtag1(p, d, pl, pr);
else if (k == 2)
addtag2(p, d, pl, pr);
else
addtag3(p, d, pl, pr);
return;
}
push_down(p, pl, pr);
ll mid = (pl + pr) >> 1;
if (l <= mid)
updata(l, r, d, ls(p), pl, mid, k);
if (r > mid)
updata(l, r, d, rs(p), mid + 1, pr, k);
push_up(p);
}
ll sum(ll l, ll r, ll p, ll pl, ll pr, ll k) {
if (l <= pl && r >= pr) {
if (k == 1)
return tree1[p];
else if (k == 2)
return tree2[p];
else
return tree3[p];
}
push_down(p, pl, pr);
ll res = 0;
ll mid = (pl + pr) >> 1;
if (l <= mid)
res = (res + sum(l, r, ls(p), pl, mid, k)) % modp;
if (r > mid)
res = (res + sum(l, r, rs(p), mid + 1, pr, k)) % modp;
return res % modp;
}
int main() {
ios::sync_with_stdio(0), cout.tie(0), cin.tie(0);
while (true) {
cin >> n >> m;
if (n == 0 && m == 0)
break;
build(1, 1, n);
while (m--) {
ll op, x, y, d;
cin >> op >> x >> y >> d;
if (x > y)
swap(x, y);
if (op != 4)
updata(x, y, d, 1, 1, n, op);
else {
cout << sum(x, y, 1, 1, n, d) << endl;
}
}
}
return 0;
}
洛谷P6242
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define rep(i,l,r) for(register int i=l;i<=r;i++)
using namespace std;
const int N = 5e5 + 5;
const int INF = 1e9 + 5; //0x3fffffff;
const double eps = 1e-6;
typedef long long ll;
const int modp = 1e6 + 37;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - 48;
ch = getchar();
}
return x * f;
}
ll n, m;
ll a[N];
ll maa[N << 2];
ll numa[N << 2];
ll mab[N << 2];
ll suma[N << 2];
ll sea[N << 2];
ll tagma[N << 2];
ll tagse[N << 2];
ll taghisma[N << 2];
ll taghisse[N << 2];
ll ls(ll x) {
return x << 1;
}
ll rs(ll x) {
return x << 1 | 1;
}
void push_up(ll p) {
suma[p] = suma[ls(p)] + suma[rs(p)];
maa[p] = max(maa[ls(p)], maa[rs(p)]);
mab[p] = max(mab[ls(p)], mab[rs(p)]);
sea[p] = max(sea[ls(p)], sea[rs(p)]);
if (maa[ls(p)] == maa[rs(p)]) {
numa[p] = numa[ls(p)] + numa[rs(p)];
} else {
sea[p] = max(sea[p], min(maa[ls(p)], maa[rs(p)]));
numa[p] = maa[ls(p)] > maa[rs(p)] ? numa[ls(p)] : numa[rs(p)];
}
}
void addtag(ll p, ll pl, ll pr, ll t1, ll t2, ll t3, ll t4) {
suma[p] += (t1 * numa[p] + (pr - pl + 1 - numa[p]) * t2);
mab[p] = max(mab[p], t3 + maa[p]);
maa[p] += t1;
if (sea[p] != -INF)
sea[p] += t2;
taghisma[p] = max(taghisma[p], tagma[p] + t3), tagma[p] += t1;
taghisse[p] = max(taghisse[p], tagse[p] + t4), tagse[p] += t2;
}
void push_down(ll p, ll pl, ll pr) {
ll maxn = max(maa[ls(p)], maa[rs(p)]);
ll mid = (pl + pr) >> 1;
if (maxn == maa[ls(p)])
addtag(ls(p), pl, mid, tagma[p], tagse[p], taghisma[p], taghisse[p]);
else
addtag(ls(p), pl, mid, tagse[p], tagse[p], taghisse[p], taghisse[p]);
if (maxn == maa[rs(p)])
addtag(rs(p), mid + 1, pr, tagma[p], tagse[p], taghisma[p], taghisse[p]);
else
addtag(rs(p), mid + 1, pr, tagse[p], tagse[p], taghisse[p], taghisse[p]);
tagma[p] = tagse[p] = taghisma[p] = taghisse[p] = 0;
}
void build(ll p, ll pl, ll pr) {
tagma[p] = tagse[p] = taghisma[p] = taghisse[p] = 0;
if (pr == pl) {
mab[p] = maa[p] = suma[p] = a[pl];
sea[p] = -INF;
numa[p] = 1;
return;
}
ll mid = (pl + pr) >> 1;
build(ls(p), pl, mid) ;
build(rs(p), mid + 1, pr);
push_up(p);
}
void updata1(ll l, ll r, ll d, ll p, ll pl, ll pr) {
if (l <= pl && r >= pr) {
addtag(p, pl, pr, d, d, d, d);
return;
}
push_down(p, pl, pr);
ll mid = (pl + pr) >> 1;
if (l <= mid)
updata1(l, r, d, ls(p), pl, mid);
if (r > mid)
updata1(l, r, d, rs(p), mid + 1, pr);
push_up(p);
}
void updata2(ll l, ll r, ll d, ll p, ll pl, ll pr) {
if (maa[p] <= d)
return;
if (l <= pl && r >= pr && sea[p] < d) {
addtag(p, pl, pr, d - maa[p], 0, d - mab[p], 0);
return;
}
push_down(p, pl, pr);
ll mid = (pl + pr) >> 1;
if (l <= mid)
updata2(l, r, d, ls(p), pl, mid);
if (r > mid)
updata2(l, r, d, rs(p), mid + 1, pr);
push_up(p);
}
ll sum(ll l, ll r, ll p, ll pl, ll pr) {
if (l <= pl && r >= pr) {
return suma[p];
}
push_down(p, pl, pr);
ll res = 0;
ll mid = (pl + pr) >> 1;
if (l <= mid)
res += sum(l, r, ls(p), pl, mid);
if (r > mid)
res += sum(l, r, rs(p), mid + 1, pr);
return res;
}
ll qmaxa(ll l, ll r, ll p, ll pl, ll pr) {
if (l <= pl && r >= pr) {
return maa[p];
}
push_down(p, pl, pr);
ll mid = (pl + pr) >> 1;
ll res = -INF;
if (l <= mid)
res = max(qmaxa(l, r, ls(p), pl, mid), res);
if (r > mid)
res = max(qmaxa(l, r, rs(p), mid + 1, pr), res);
return res;
}
ll qmaxb(ll l, ll r, ll p, ll pl, ll pr) {
if (l <= pl && r >= pr) {
return mab[p];
}
push_down(p, pl, pr);
ll mid = (pl + pr) >> 1;
ll res = -INF;
if (l <= mid)
res = max(qmaxb(l, r, ls(p), pl, mid), res);
if (r > mid)
res = max(qmaxb(l, r, rs(p), mid + 1, pr), res);
return res;
}
int main() {
n = read();
m = read();
for (ll i = 1; i <= n; i++)
a[i] = read();
build(1, 1, n);
while (m--) {
ll op, x, y;
op = read();
x = read();
y = read();
if (op == 1) {
ll d;
d = read();
updata1(x, y, d, 1, 1, n);
} else if (op == 2) {
ll d;
d = read();
updata2(x, y, d, 1, 1, n);
} else if (op == 3) {
cout << sum(x, y, 1, 1, n) << endl;
} else if (op == 4) {
cout << qmaxa(x, y, 1, 1, n) << endl;
} else {
cout << qmaxb(x, y, 1, 1, n) << endl;
}
}
return 0;
}
hdu1540
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define rep(i,l,r) for(register int i=l;i<=r;i++)
using namespace std;
const int N = 5e4 + 10;
const int INF = 0x3fffffff;
const double eps = 1e-6;
typedef int ll;
const int modp = 1e6 + 37;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - 48;
ch = getchar();
}
return x * f;
}
ll n, m;
ll tree[N];
stack<ll> st;
void init() {
memset(tree, 0, sizeof(tree));
rep(i, 1, n) tree[i] = lowbit(i);
while (!st.empty())
st.pop();
}
void updata(ll x, ll d) {
while (x <= n) {
tree[x] += d;
x += lowbit(x);
}
}
ll sum(ll x) {
ll res = 0;
while (x > 0) {
res += tree[x];
x -= lowbit(x);
}
return res;
}
bool check(ll l, ll r) {
if (sum(r) - sum(l - 1) >= r - l + 1)
return true;
return false;
}
ll solve(ll x) {
ll res = 0;
ll l = 1, r = x + 1;
while (l < r) {
ll mid = (l + r) >> 1;
if (check(mid, x))
r = mid;
else
l = mid + 1;
}
ll pos1 = r;
l = x;
r = n;
while (l < r) {
ll mid = (l + r + 1) >> 1;
if (check(x, mid))
l = mid;
else
r = mid - 1;
}
ll pos2 = l;
return pos2 - pos1 + 1;
}
int main() {
//ios::sync_with_stdio(0), cout.tie(0), cin.tie(0);
while (~scanf("%d%d", &n, &m)) {
init();
while (m--) {
char op[10];
scanf("%s", op);
if (op[0] == 'D') {
ll x;
scanf("%d", &x);
updata(x, -1);
st.push(x);
} else if (op[0] == 'Q') {
ll x;
scanf("%d", &x);
ll ans = solve(x);
printf("%d\n", ans);
} else {
ll x;
x = st.top();
st.pop();
updata(x, 1);
}
}
}
return 0;
}
hdu 1542
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define rep(i,l,r) for(register int i=l;i<=r;i++)
using namespace std;
const int N = 5e3 + 10;
const int INF = 0x3fffffff;
const double eps = 1e-6;
typedef long long ll;
const int modp = 1e6 + 37;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - 48;
ch = getchar();
}
return x * f;
}
ll n;
double tree[N << 2];
int tag[N << 2];
double xx[N];
typedef struct scanl {
double x1, x2, y;
int io;
bool operator <(const scanl &a) {
return y < a.y;
}
scanl() {
}
scanl(double xx1, double xx2, double yy, int iio) {
x1 = xx1, x2 = xx2, y = yy, io = iio;
}
} Line;
Line line[N];
ll ls(ll p) {
return p << 1;
}
ll rs(ll p) {
return p << 1 | 1;
}
void push_up(ll p, ll pl, ll pr) {
if (tag[p] > 0)
tree[p] = xx[pr] - xx[pl];
else if (pl + 1 == pr)
tree[p] = 0;
else
tree[p] = tree[ls(p)] + tree[rs(p)];
}
void addtag(ll p, ll d, ll pl, ll pr) {
tag[p] += d;
if (tag[p] > 0)
tree[p] = xx[pr] - xx[pl];
else if (pl + 1 == pr)
tree[p] = 0;
else
tree[p] = tree[ls(p)] + tree[rs(p)];
}
void updata(ll l, ll r, ll d, ll p, ll pl, ll pr) {
if (l <= pl && r >= pr) {
addtag(p, d, pl, pr);
return;
}
if (pl + 1 == pr)
return;
ll mid = (pl + pr) >> 1;
if (l <= mid)
updata(l, r, d, ls(p), pl, mid);
if (r > mid)
updata(l, r, d, rs(p), mid, pr);
push_up(p, pl, pr);
}
int main() {
//ios::sync_with_stdio(0), cout.tie(0), cin.tie(0);
int k = 0;
while (~scanf("%d", &n)) {
if (n == 0)
break;
int cnt = 0;
rep(i, 1, n) {
double x1, x2, y1, y2;
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
line[++cnt] = Line(x1, x2, y1, 1);
xx[cnt] = x1;
line[++cnt] = Line(x1, x2, y2, -1);
xx[cnt] = x2;
}
sort(line + 1, line + cnt + 1);
sort(xx + 1, xx + cnt + 1);
int num = unique(xx + 1, xx + cnt + 1) - (xx + 1);
memset(tree, 0, sizeof(tree));
memset(tag, 0, sizeof(tag));
double ans = 0;
rep(i, 1, cnt) {
ans += tree[1] * (line[i].y - line[i - 1].y);
int l = lower_bound(xx + 1, xx + num + 1, line[i].x1) - xx;
int r = lower_bound(xx + 1, xx + num + 1, line[i].x2) - xx;
updata(l, r, line[i].io, 1, 1, num);
}
cout << "Test case #" << ++k << endl;
printf("Total explored area: %.2lf\n", ans);
}
return 0;
}