目录
- 注意事项
- Code
这题我调了大半天，搞得我心力交瘁，过了发篇题解祝贺一下。
传送门
题意是说，给定排列，求区间内有多少个连续子区间，满足出现的数连续。
注意这个连续的条件可以转换成 \(\max - \min = len - 1 = r - l\)，即 \(\max - \min +\ l - r = 0\)。接下来我们照搬一个常见的套路：右移 \(r\)，更新，然后处理右端点为 \(r\) 的询问。
这一切都围绕着 \(\max - \min+\ l - r\) 这个东西的维护。首先，区间数 \(0\) 是一个复杂度无 polylog 的做法，但我们注意到对于任意区间，\(\max - \min +\ l - r \ge 0\) 是恒满足的，所以问题变成了区间最小值个数，这个是可以线段树上搞的。
接下来考虑加进来一个新的数怎么更新。显然分成两部分：
- \(\max - \min\)，这两个本质相同。考虑维护两个单调栈，一个存储后缀最小值，一个存最大值。每次插入一个数，将弹掉的数和插入的数之间进行区间加操作。注意到根据单调栈的性质，每个数最多只会参与两次区间修改，所以区间修改次数是线性的。
简单的示意图：
- \(l - r\)，就是个平凡的区间修改。
所以我们维护了这个值，同时维护最小值及其出现次数。现在我们发现一件事——我们维护的是区间的子区间，所以我们还要维护区间历史 \(\min\) 次数和。
做这种事情有一个高明的技巧：再打一个时间标记。注意到所求的区间在没有更新的时间内都可以算作答案，所以每次下传时间 tag 时，要将距离上一次更新的所有历史都算上。然后就做完了。
注意事项
- 单调栈对应的区间，注意删除最后一个元素的时候能不能全部更新（我就这里调了三个小时 T_T）；
- pushdown 的时候处理 tag 的顺序。
Code
#include <utility>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int max_n = 120000, max_s = 131072, max_trs = max_s*4+1, INF = 0x3f3f3f3f;
struct rg
{
int l, r, id;
ll ans;
}
qry[max_n];
pair<int, int> smx[max_n+1], smn[max_n+1];
int a[max_n], mn[max_trs], tag[max_trs], htm[max_trs];
ll cmn[max_trs], hcmn[max_trs];
inline int ls(int x) { return (x << 1); }
inline int rs(int x) { return (x << 1) | 1; }
void build(int l, int r, int id)
{
cmn[id] = 1;
mn[id] = l;
if (l == r) return;
int mid = (l + r) >> 1;
build(l, mid, ls(id));
build(mid + 1, r, rs(id));
}
inline void updmn(int& mn, ll &mnc, int nmn, ll ncmn)
{
if (mn > nmn)
mn = nmn, mnc = ncmn;
else if (mn == nmn)
mnc += ncmn;
}
inline void updata(int id, int vl)
{
tag[id] += vl, mn[id] += vl;
}
inline void pushdtg(int id, int vl)
{
htm[id] += vl;
hcmn[id] += 1ll * vl * cmn[id];
}
inline int my_min(int a, int b) { return (a < b)? a:b; }
inline void pushup(int id)
{
mn[id] = my_min(mn[ls(id)], mn[rs(id)]), cmn[id] = 0;
if (mn[id] == mn[ls(id)]) cmn[id] += cmn[ls(id)];
if (mn[id] == mn[rs(id)]) cmn[id] += cmn[rs(id)];
hcmn[id] = hcmn[ls(id)] + hcmn[rs(id)];
}
inline void pushdown(int id)
{
updata(ls(id), tag[id]), updata(rs(id), tag[id]);
tag[id] = 0;
if (mn[id] == mn[ls(id)]) pushdtg(ls(id), htm[id]);
if (mn[id] == mn[rs(id)]) pushdtg(rs(id), htm[id]);
htm[id] = 0;
}
void modify(int L, int R, int l, int r, int id, int vl)
{
if (L <= l && r <= R)
{
updata(id, vl);
return;
}
pushdown(id);
int mid = (l + r) >> 1;
if (L <= mid && l <= R)
modify(L, R, l, mid, ls(id), vl);
if (L <= r && mid < R)
modify(L, R, mid + 1, r, rs(id), vl);
pushup(id);
}
ll query(int L, int R, int l, int r, int id)
{
if (L <= l && r <= R)
return hcmn[id];
pushdown(id);
int mid = (l + r) >> 1; ll ret = 0;
if (L <= mid && l <= R)
ret += query(L, R, l, mid, ls(id));
if (L <= r && mid < R)
ret += query(L, R, mid + 1, r, rs(id));
return ret;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
build(1, n, 1);
cin >> q;
for (int i = 0; i < q; i++)
cin >> qry[i].l >> qry[i].r, qry[i].id = i, qry[i].l--, qry[i].r--;
sort(qry, qry + q, [](const rg& lhs, const rg& rhs) { return lhs.r < rhs.r; });
int mxtp = 0, mntp = 0, lst;
for (int i = 0, qtr = 0; i < n; i++)
{
updata(1, -1);
while (mxtp > 0 && smx[mxtp].first < a[i])
modify(smx[mxtp-1].second + 1, smx[mxtp].second, 1, n, 1, a[i] - smx[mxtp].first), mxtp--;
smx[++mxtp].first = a[i], smx[mxtp].second = i + 1;
while (mntp > 0 && smn[mntp].first > a[i])
modify(smn[mntp-1].second + 1, smn[mntp].second, 1, n, 1, smn[mntp].first - a[i]), mntp--;
smn[++mntp].first = a[i], smn[mntp].second = i + 1;
pushdtg(1, 1);
while (qtr < q && qry[qtr].r <= i)
qry[qtr].ans = query(qry[qtr].l + 1, i + 1, 1, n, 1), qtr++;
}
sort(qry, qry + q, [](const rg& lhs, const rg& rhs) { return lhs.id < rhs.id; });
for (int i = 0; i < q; i++)
cout << qry[i].ans << endl;
return 0;
}