CF997E Good Subsegments

在 526F 的基础上增强，需要回答区间询问而不是只求区间 $[1, n]$ 。

还是利用扫描线，对于区间 $[l, r]$ ，对于每次 $i \in [l, r]$ ，都查询一次 $[l, i]$ ，但是复杂度显然起飞。

考虑每次扫完后，将当前的答案留下，那么只用在 $r$ 处查询 $[l, r]$ 即可。

考虑怎么将这个答案留下，将整个线段树都遍历一次显然复杂度是错误的。发现很多情况下并没有用到这个信息，或者随着 $r$ 的增加答案并没有改变，只有用到的时候才需要将其继续递归。考虑增加一种标记，表示当前答案需要将此时 $0$ 的个数算几次。这样想着似乎很简单，但实际实现的时候需要考虑其中是否有冲突。

首先这样做的时候一定要保证 $cnt$ 需要是正确的，也就是 $cnt$ 发生变化的时候一定需要把标记下放了。

接着考虑这样一种情况，此时父节点需要向两个子节点下放，但是其中一个子节点原来并不是 $0$ ，也就是不算作答案。可能会想先下放答案标记判断是否是 $0$ 再下放最小值标记，但事实是这样判断得到的最小值不是真实的最小值，因为还有上一次修改没有下放；如果先下放最小值标记，再下放答案标记，因为这次修改也算上了，那么不能判断是否是合法的。我们需要正确地处理两种标记的矛盾。事实上，我们发现，每次 $r$ 移动完成后，贡献答案的是值为 $0$ 的，其父节点区间的最小值也一定为 $0$ ，在区间加后，该节点一定和父节点同时加上一个数，也就是说，如果移动前需要将答案更新，那么此时子节点和父节点最小值相同，并且位置没有发生变化。我们先将最小值标记下放，再下放答案标记，那么上次的修改完全完成了，而本次的修改不影响我们判断子节点是否贡献答案。

查看代码

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 12e4 + 10;
int n, m, w[N];
LL ans[N];
struct Query
{
    int l, id;
};
vector <Query> q[N];
struct Node
{
    int l, r, tag, mn, cnt, times;
    LL ans;
} tr[N << 2];
void pushup (int x)
{
    tr[x].mn = min(tr[x << 1].mn, tr[x << 1 | 1].mn);
    tr[x].cnt = 0;
    tr[x << 1].mn == tr[x].mn && (tr[x].cnt += tr[x << 1].cnt);
    tr[x << 1 | 1].mn == tr[x].mn && (tr[x].cnt += tr[x << 1 | 1].cnt);
    tr[x].ans = tr[x << 1].ans + tr[x << 1 | 1].ans;
}
void add_mn (int x, int k)
{
    tr[x].mn += k, tr[x].tag += k;
}
void add_times (int x, int k)
{
    tr[x].ans += (LL)k * tr[x].cnt, tr[x].times += k;
}
void pushdown (int x)
{
    add_mn(x << 1, tr[x].tag), add_mn(x << 1 | 1, tr[x].tag);
    tr[x].tag = 0;
    tr[x].mn == tr[x << 1].mn && (add_times(x << 1, tr[x].times), 0);
    tr[x].mn == tr[x << 1 | 1].mn && (add_times(x << 1 | 1, tr[x].times), 0);
    tr[x].times = 0;
}
void build (int l = 1, int r = n, int x = 1)
{
    tr[x].l = l, tr[x].r = r;
    if (l == r)
        return tr[x].mn = l, tr[x].cnt = 1, void();
    int mid = l + r >> 1;
    build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1);
    pushup(x);
}
void modify (int l, int r, int k, int x = 1)
{
    if (l > r || tr[x].l > r || l > tr[x].r)
        return;
    if (tr[x].l >= l && tr[x].r <= r)
        return add_mn(x, k);
    pushdown(x);
    modify(l, r, k, x << 1), modify(l, r, k, x << 1 | 1);
    pushup(x);
}
LL query (int l, int r, int x = 1)
{
    if (l > tr[x].r || tr[x].l > r)
        return 0;
    if (tr[x].l >= l && tr[x].r <= r)
        return tr[x].ans;
    pushdown(x);
    return query(l, r, x << 1) + query(l, r, x << 1 | 1);
}
int top1, stk1[N], top2, stk2[N];
int main ()
{
    read(n);
    for (int i = 1; i <= n; i++)
        read(w[i]);
    build();
    read(m);
    for (int i = 1, l, r; i <= m; i++)
    {
        read(l), read(r);
        q[r].push_back((Query){l, i});
    }
    for (int i = 1; i <= n; i++)
    {
        while (top1 && w[stk1[top1]] > w[i])
            modify(stk1[top1 - 1] + 1, stk1[top1], w[stk1[top1]]), top1--;
        modify(stk1[top1] + 1, i, -w[i]);
        stk1[++top1] = i;
        while (top2 && w[stk2[top2]] < w[i])
            modify(stk2[top2 - 1] + 1, stk2[top2], -w[stk2[top2]]), top2--;
        modify(stk2[top2] + 1, i, w[i]);
        stk2[++top2] = i;
        modify(1, n, -1);
        add_times(1, 1);
        for (Query j : q[i])
            ans[j.id] = query(j.l, i);
    }
    for (int i = 1; i <= m; i++)
        write(ans[i]), puts("");
    return 0;
}