xiaoxin and his watermelon candy
xiaoxin is very smart since he was a child. He arrange these candies in a line and at each time before eating candies, he selects three continuous watermelon candies from a specific range [L, R] to eat and the chosen triplet must satisfies:
if he chooses a triplet (ai,aj,ak) then:
1. j=i+1,k=j+1
2. ai≤aj≤ak
Your task is to calculate how many different ways xiaoxin can choose a triplet in range [L, R]?
two triplets (a0,a1,a2) and (b0,b1,b2) are thought as different if and only if:
a0≠b0 or a1≠b1 or a2≠b2
For each test case, the first line contains a single integer n(1≤n≤200,000)which represents number of watermelon candies and the following line contains ninteger numbers which are given in the order same with xiaoxin arranged them from left to right.
The third line is an integer Q(1≤200,000) which is the number of queries. In the following Q lines, each line contains two space seperated integers l,r(1≤l≤r≤n) which represents the range [l, r].
5
1 2 3 4 5
3
1 3
1 4
1 5
2
3
#pragma comment(linker, "/STACK:10240000,10240000")
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include<map>
using namespace std;
const int N = 1e6+, M = , mod = 1e9+, inf = 0x3f3f3f3f;
typedef long long ll;
//不同为1,相同为0 map< pair< int, pair< int,int> > ,int> mp;
int T,a[N],n,m,b[N],c,C[N],nex[N],p[N],H[N];
struct data{int l,r,id,ans;}Q[N];
int cmp1(data a,data b) {if(a.l==b.l) return a.r<b.r;else return a.l<b.l;}
int cmp2(data a,data b) {return a.id<b.id;}
int lowbit(int x) {
return x&(-x);
}
void add(int x, int add) {
for (; x <= n; x += lowbit(x)) {
C[x] += add;
}
}
int sum(int x) {
int s = ;
for (; x > ; x -= lowbit(x)) {
s += C[x];
}
return s;
}
int main() {
scanf("%d",&T);
while(T--) {
mp.clear();
memset(H,,sizeof(H));
memset(p,,sizeof(p));
memset(b,-,sizeof(b));
memset(C,,sizeof(C));memset(nex,,sizeof(nex));
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]), b[i] = -,nex[i] = ;
int k = ;
for(int i=;i<=n;i++) {
if(a[i]>=a[i-]&&a[i-]>=a[i-]) {
if(mp[make_pair(a[i-],make_pair(a[i-],a[i]))]) b[i] = mp[make_pair(a[i-],make_pair(a[i-],a[i]))];
else b[i] = k,mp[make_pair(a[i-],make_pair(a[i-],a[i]))] = k,H[k] = , k++;
}
else b[i] = -;
}
for(int i=n;i>=;i--)
if(b[i]!=-)
nex[i]=p[b[i]],p[b[i]]=i;
for(int i=;i<k;i++)
add(p[i],);
int q;
scanf("%d",&q);
for(int i=;i<=q;i++) {
scanf("%d%d",&Q[i].l,&Q[i].r);Q[i].id = i;
}
sort(Q+,Q+q+,cmp1);
int l = ;
for(int i=;i<=q;i++) {
while(l<Q[i].l+) {
if(nex[l] ) add(nex[l],);l++;
}
if(Q[i].l+>Q[i].r) Q[i].ans = ;
else Q[i].ans = sum(Q[i].r) - sum(Q[i].l+-);
}
sort(Q+,Q+q+,cmp2);
for(int i=;i<=q;i++) {
printf("%d\n",Q[i].ans);
}
}
return ;
}