题目地址：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+
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);
}
}
京公网安备 11010502036488号