Lamis is a smart girl. She is interested in problems about sequences and their intervals.

Here she shows you a sequence of length nn with positive integers, denoted by a1,a2,a3,?,ana1,a2,a3,?,an. She is amazed at those intervals, which is a consecutive subsequence of a1,a2,?,ana1,a2,?,an, with several continuous numbers, and names them continuous intervals.

More precisely, consider a interval al,al+1,?,ar?1,aral,al+1,?,ar?1,ar for instance where 1≤l≤r≤n1≤l≤r≤n. If, after sorting the interval, the difference of any two neighbouring items is less than or equal to 11, the interval will be considered as continuous.

As her best friends, you came from far and wide and travelled thousands of miles to Ningxia, to help her count the number of continuous intervals of the sequence.

Input
The input contains several test cases, and the first line is a positive integer TT indicating the number of test cases which is up to 10001000.

For each test case, the first line contains an integer n (1≤n≤105)n (1≤n≤105) which is the length of the given sequence. The second line contains nn integers describing all items of the sequence, where the ii-th one is denoted by ai (1≤ai≤109)ai (1≤ai≤109).

We guarantee that the sum of nn in all test cases is up to 106106.

Output
For each test case, output a line containing Case #x: y, where x is the test case number starting from 11, and y is the number of continuous intervals in this test case.

Example
Input
2
4
1 2 1 2
4
1 3 2 4
Output
Case #1: 10
Case #2: 8
題意：找出區(qū)間max-區(qū)間min+1區(qū)間數(shù)字種類(lèi)數(shù)的區(qū)間個(gè)數(shù)。
找出max-min+1=cnt的區(qū)間個(gè)數(shù)，就是求max-min-cnt-1的區(qū)間個(gè)數(shù)。這樣就轉(zhuǎn)換成了求區(qū)間max-min-cnt最小的問(wèn)題。并且要維護(hù)最小值的個(gè)數(shù)。對(duì)于區(qū)間最大值，我們可以用單調(diào)棧維護(hù)，并且記錄下來(lái)他們的位置。對(duì)于區(qū)間最小值也是一樣，也是用單調(diào)炸維護(hù)。對(duì)于求區(qū)間個(gè)數(shù)，就是普通操作。具體解釋看代碼。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e5+100; struct node{int l;int r;int sum;int _max;int lazy; }p[maxx<<2]; struct Node{int pos;int k;Node(int x=0,int y=0){pos=x;k=y;} }_max[maxx],_min[maxx]; int n;inline void pushup(int cur)//維護(hù)最小值并且記錄最小值的個(gè)數(shù) {p[cur]._max=min(p[cur<<1]._max,p[cur<<1|1]._max);if(p[cur<<1]._max==p[cur<<1|1]._max) p[cur].sum=p[cur<<1].sum+p[cur<<1|1].sum;else p[cur].sum=min(p[cur<<1]._max,p[cur<<1|1]._max)==p[cur<<1]._max?p[cur<<1].sum:p[cur<<1|1].sum; } inline void pushdown(int cur) {if(p[cur].lazy){p[cur<<1]._max+=p[cur].lazy;p[cur<<1|1]._max+=p[cur].lazy;p[cur<<1].lazy+=p[cur].lazy;p[cur<<1|1].lazy+=p[cur].lazy;p[cur].lazy=0;} } inline void build(int l,int r,int cur) {p[cur].l=l;p[cur].r=r;p[cur].lazy=0;p[cur].sum=p[cur]._max=0;if(l==r){p[cur].sum=1;//對(duì)于每一個(gè)數(shù)來(lái)說(shuō)，它本身就是那樣的一個(gè)區(qū)間。return ;}int mid=l+r>>1;build(l,mid,cur<<1);build(mid+1,r,cur<<1|1); } inline void update(int l,int r,int v,int cur) {int L=p[cur].l;int R=p[cur].r;if(l<=L&&R<=r){p[cur].lazy+=v;p[cur]._max+=v;return ;}pushdown(cur);int mid=L+R>>1;if(r<=mid) update(l,r,v,cur<<1);else if(l>mid) update(l,r,v,cur<<1|1);else {update(l,mid,v,cur<<1);update(mid+1,r,v,cur<<1|1);}pushup(cur); } inline ll query(int l,int r,int cur) {int L=p[cur].l;int R=p[cur].r;if(l<=L&&R<=r) {if(p[cur]._max==-1) return p[cur].sum;else return 0;//只有最小值是-1的時(shí)候才是我們要找的那種區(qū)間，否則就不是。}pushdown(cur);int mid=L+R>>1;if(r<=mid) return query(l,r,cur<<1);else if(l>mid) return query(l,r,cur<<1|1);else return query(l,mid,cur<<1)+query(mid+1,r,cur<<1|1); } inline void solve() {int t,k,v,pp,kk=0;scanf("%d",&t);while(t--){ll ans=0;scanf("%d",&n);build(1,n,1);int s=0,e=0;map<int,int> mp;for(int i=1;i<=n;i++){scanf("%d",&k);while(s&&_max[s].k<k)//單調(diào)炸維護(hù)區(qū)間最大值，如果當(dāng)前值大于之前最大值。{pp=_max[s].pos;v=k-_max[s].k;//v是加入k之后，對(duì)于那個(gè)區(qū)間max-min-cnt的貢獻(xiàn)update(_max[--s].pos+1,pp,v,1);//更新k是最大值的那個(gè)區(qū)間}_max[++s]=Node(i,k);//把當(dāng)前值加入到棧中。while(e&&_min[e].k>k)//最小值一樣。{pp=_min[e].pos;v=_min[e].k-k;update(_min[--e].pos+1,pp,v,1);}_min[++e]=Node(i,k);update(mp[k]+1,i,-1,1);//mp[k]記錄的是k上一次出現(xiàn)的位置，對(duì)于這個(gè)位置前的位置，加入的這個(gè)k是沒(méi)有貢獻(xiàn)的，只對(duì)這個(gè)位置到i之間的位置有貢獻(xiàn)，數(shù)的種類(lèi)增加，cnt增加，對(duì)于max-min-cnt就-1了。mp[k]=i;ans+=query(1,i,1);//1~i的所要求的區(qū)間數(shù)。}printf("Case #%d: %lld\n",++kk,ans);} }int main() {solve();return 0; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的Continuous Intervals Gym - 102222L（2018宁夏邀请赛暨2019银川icpc网络预选赛）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。