分析：
首先考虑如何计算整个数组有多少个good区间
容易发现一个区间是good区间当且仅当max-min-len=-1，且任意区间max-min-len>=-1
我们可以枚举右端点，然后维护前面每个位置到当前右端点的max-min-len值，容易发现我们只需要维护区间最小值和最小值的个数就行了，于是用线段树即可
于是我们可以得到以某个点为右端点的时候合法区间总数，那么我们把每次的结果加起来，就得到了整个数组有多少个good区间
每次右端点移动怎么更新呢？显然我们只需要用一个max单调栈，一个min单调栈来帮助寻找修改区间，容易知道修改区间的个数是O(n)级别的，所以整个修改是O(nlogn)的
好，现在我们回到原来的问题，如何求[l,r]内有多少个good区间
在这个问题中，我们实际上要额外知道“每个区间的历史答案和”，这是什么意思呢，比如说在i=7的时候，[4,7]里的答案存的是有多少个合法的位置是和7匹配的
但i=6的时候,[4,7]里的答案存的是有多少个合法的位置是和6匹配的
我们自然而然就考虑到把每个右端点时刻，一个区间的产生的答案值加起来就行了，但这个时间复杂度是巨大的
这里我们仍然可以用延迟标记来解决，比如右端点i枚举完了，我们可以给[1,i]上个tag，表示这整个区间的历史答案需要加上现在时刻的答案
时间复杂度O(nlogn)
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define mp make_pair
4 const int maxn=120000;
5 struct wjmzbmr
6 {
7 int mi,num,tag;
8 int time;
9 long long ans;
10 }tree[maxn*4+5];
11 vector<pair<int,int> > q[maxn+5];
12 long long ans[maxn+5];
13 int a[maxn+5],s[maxn+5],s1[maxn+5];
14 int len,len1;
15 int n,m;
16 void addtag(int k,int x)
17 {
18 tree[k].tag+=x;
19 tree[k].mi+=x;
20 }
21 void addtime(int k,int x)
22 {
23 tree[k].time+=x;
24 tree[k].ans+=1LL*x*tree[k].num;
25 }
26 void pushdown(int k)
27 {
28 if(tree[k].tag)
29 {
30 addtag(k*2,tree[k].tag);
31 addtag(k*2+1,tree[k].tag);
32 tree[k].tag=0;
33 }
34 if(tree[k].time)
35 {
36 if(tree[k].mi==tree[k*2].mi) addtime(k*2,tree[k].time);
37 if(tree[k].mi==tree[k*2+1].mi) addtime(k*2+1,tree[k].time);
38 tree[k].time=0;
39 }
40 }
41 void update(int k)
42 {
43 tree[k].mi=min(tree[k*2].mi,tree[k*2+1].mi);
44 tree[k].ans=tree[k*2].ans+tree[k*2+1].ans;
45 tree[k].num=0;
46 if(tree[k].mi==tree[k*2].mi) tree[k].num+=tree[k*2].num;
47 if(tree[k].mi==tree[k*2+1].mi) tree[k].num+=tree[k*2+1].num;
48 }
49 void build(int k,int l,int r)
50 {
51 if(l>r) return;
52 if(l==r)
53 {
54 tree[k].num=1;
55 tree[k].mi=-1;
56 return;
57 }
58 int mid=(l+r)>>1;
59 build(k*2,l,mid);
60 build(k*2+1,mid+1,r);
61 update(k);
62 }
63 void modify(int k,int l,int r,int ql,int qr,int x)
64 {
65 if(r<ql||l>qr||l>r) return;
66 if(l>=ql&&r<=qr)
67 {
68 addtag(k,x);
69 return;
70 }
71 if(l==r) return;
72 pushdown(k);
73 int mid=(l+r)>>1;
74 modify(k*2,l,mid,ql,qr,x);
75 modify(k*2+1,mid+1,r,ql,qr,x);
76 update(k);
77 }
78 void modify1(int k,int l,int r,int ql,int qr,int x)
79 {
80 if(r<ql||l>qr||l>r) return;
81 if(l>=ql&&r<=qr)
82 {
83 if(tree[k].mi==-1)
84 addtime(k,x);
85 return;
86 }
87 if(l==r) return;
88 pushdown(k);
89 int mid=(l+r)>>1;
90 modify1(k*2,l,mid,ql,qr,x);
91 modify1(k*2+1,mid+1,r,ql,qr,x);
92 update(k);
93 }
94 long long query(int k,int l,int r,int ql,int qr)
95 {
96 if(r<ql||l>qr||l>r) return 0;
97 if(l>=ql&&r<=qr) return tree[k].ans;
98 if(l==r) return 0;
99 pushdown(k);
100 int mid=(l+r)>>1;
101 long long ans=query(k*2,l,mid,ql,qr)+query(k*2+1,mid+1,r,ql,qr);
102 update(k);
103 return ans;
104 }
105 int main()
106 {
107 scanf("%d",&n);
108 for(int i=1;i<=n;++i) scanf("%d",&a[i]);
109 scanf("%d",&m);
110 for(int i=1;i<=m;++i)
111 {
112 int l,r;
113 scanf("%d%d",&l,&r);
114 q[r].push_back(mp(l,i));
115 }
116 build(1,1,n);
117 for(int i=1;i<=n;++i)
118 {
119 while(len&&a[s[len]]<a[i]) modify(1,1,n,s[len-1]+1,s[len],a[i]-a[s[len]]),--len;
120 s[++len]=i;
121 //for(int j=1;j<=len;++j) printf("%d ",a[s[j]]);printf("\n");
122 while(len1&&a[s1[len1]]>a[i]) modify(1,1,n,s1[len1-1]+1,s1[len1],a[s1[len1]]-a[i]),--len1;
123 s1[++len1]=i;
124 //for(int j=1;j<=len1;++j) printf("%d ",a[s1[j]]);printf("\n");
125 modify1(1,1,n,1,i,1);
126 for(auto x:q[i]) ans[x.second]=query(1,1,n,x.first,i);
127 //printf("%lld\n",query(1,1,n,1,i));
128 //if(i==4) printf("%d\n",tree[2].ans);
129 modify(1,1,n,1,i,-1);
130
131 }
132 for(int i=1;i<=m;++i) printf("%lld\n",ans[i]);
133 return 0;
134 }
