题目地址：https://nanti.jisuanke.com/t/41296

题目：

给出一个序列，问有多少个区间使得这个区间内所有的数sort之后相邻两数的差值不超过1

解题思路：

max/min：区间最大/小值，cnt：区间不同数的个数，满足条件的Continuous Intervals的一个性质：

max-min+1=cnt,即max-min-cnt=-1，且最小值是-1

枚举区间右边界R，那么区间左边界L的取值范围是一个区间：[1，R]

边输入边处理，若处理到第i个数，[i,i]定是一个满足条件的区间，其他需要判断的区间是[j,i](j<i)，而[j,i]只是在[j,i-1]后面加了个a[i]，[j,i-1]在前面已经处理过了。

对于a[i]：

1⃣️如果它能取代[j,i-1]中的最小值，那么[j,i]这个区间的min就要被更换，对应的式子max-min-cnt就要改变相应的值；

2⃣️同理，如果它能取代[j,i-1]中的最大值，那么[j,i]对应的式子也要改变相应的值，

3⃣️同时也要更新区间的cnt值。

1⃣️2⃣️可以用单调栈和线段树的区间更新解决：

考虑如果要找一个数x左边第一个小于它的数，记为L[x]，那么在使用单调栈的过程中，每次处理完，单调栈中存的数（栈底称为最下面，栈顶称为最上面）下面的数一定是L[紧邻的上面的数]。若此时单调栈中下面的数是a，上面的数是b，那么L[b]=a，原序列中[pos[a]+1,pos[b]-1]之间的数都因为大于b而被移除了栈，所以对于pos[a]+1 ≤ j ≤pos[b]（j的范围下同），[j,pos[b]]的区间最小值是b，若待插入的是第i个数k，且k<=b，即k可以取代b成为[j,pos[b]]的区间最小值，那么[j,i]的区间最小值就要更新成k了，对应式子变成max-（min-(b-k)）-cnt=max-min-cnt+(b-k),线段树区间更新即可，但是k<=b ,a<b，k和a的关系未知，仍要继续判断处理

考虑找一个数x左边第一个大于它的数，也是同样的处理思路，某些区间的式子变成max+-min-cnt

3⃣️用线段树区间更新解决：

我们没必要求出每个区间cnt的值具体是多少，只要能确定a[i]=k的出现对以a[i]为最后一个元素的区间的cnt是否有改变，若k上一次出现的位置是pos[k], 那么pos[k]+1 ≤ j ≤ i, [j,i]区间内都增加了一个新的元素，式子变成max-min-(cnt+1)=max-min-cnt-1

最后就是如何利用线段树快速统计区间max-min-cnt值=-1的所有区间数，每次添加一个元素[i,i]这个区间的式子值是-1，且区间式子值不可能比-1小，所以如果两边都是-1的话，统计和，否则统计式子值小的那一侧，总之方法很巧妙（我想不到的那种）

ac代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
typedef long long ll;
int t, n, k;
struct node{
    int pos, v;
}mx[maxn], mn[maxn];
int nx, nn;
int sum[maxn*4], lazy[maxn*4], val[maxn*4];//val=max-min-cnt
unordered_map<int, int> m;//记录上一次出现的位置
void push_up(int id)
{
    val[id] = min(val[id<<1], val[id<<1|1]);
    if(val[id<<1] == val[id<<1|1]) sum[id] = sum[id<<1] + sum[id<<1|1];
    else if(val[id<<1] < val[id<<1|1]) sum[id] = sum[id<<1];
    else sum[id] = sum[id<<1|1];
}
void push_down(int id)
{
    lazy[id<<1] += lazy[id];
    lazy[id<<1|1] += lazy[id];
    val[id<<1] += lazy[id];//只更新到了val[id]，下面的也要更新
    val[id<<1|1] += lazy[id];
    lazy[id] = 0;
}
void build(int id, int l, int r, int p)
{
    if(l == r)
    {
        val[id] = -1;//【p，p】满足条件
        sum[id] = 1;
        return ;
    }
    int mid = (l + r) >> 1;
    if(p <= mid) build(id<<1, l, mid, p);
    else build(id<<1|1, mid+1, r, p);
    push_up(id);
}
void update(int id, int l, int r, int ql, int qr, int v)//区间更新
{
    if(ql <= l && r <= qr)
    {
        val[id] += v;
        lazy[id] += v;
        return ;
    }
    if(lazy[id]) push_down(id);
    int mid = (l + r) >> 1;
    if(ql <= mid) update(id<<1, l, mid, ql, qr, v);
    if(qr > mid) update(id<<1|1, mid+1, r, ql, qr, v);
    push_up(id);
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    int Case = 0;
    scanf("%d", &t);
    while(t--)
    {
        ll ans = 0;
        memset(sum, 0, sizeof sum);
        memset(lazy, 0, sizeof lazy);
        mx[0]={0,0}, mn[0]={0,0};
        nx = nn = 0;
        m.clear();
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &k);
            build(1, 1, n, i);
            while(nx > 0 && mx[nx].v <= k) // max
            {
                int pos = mx[nx].pos;
                int v = k-mx[nx].v;
                update(1, 1, n, mx[--nx].pos+1, pos, v);
            }
            mx[++nx] = {i, k};
            while(nn >0 && mn[nn].v >= k) // min
            {
                int pos = mn[nn].pos;
                int v = mn[nn].v-k;
                update(1, 1, n, mn[--nn].pos+1, pos, v);
            }
            mn[++nn] = {i, k};
            int L;
            if(m[k]) L = m[k] + 1;
            else L = 1;
            m[k] = i;
            update(1, 1, n, L, i, -1);
            ans += sum[1];
        }
        printf("Case #%d: %lld\n", ++Case, ans);
    }
}