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 n integer 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].
这道题额，对于每个点建一棵线段树，表示以它为左端点的所有区间……口胡不清。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=;
int a[maxn],Hash[maxn],ok[maxn];
int pre[maxn],nxt[maxn],head[maxn],fa[maxn],son[maxn];
int sum[maxn*],ch[maxn*][],rt[maxn],cnt;
void Insert(int pre,int &rt,int l,int r,int g,int d){
rt=++cnt;
ch[rt][]=ch[pre][];
ch[rt][]=ch[pre][];
sum[rt]=sum[pre]+d;
if(l==r)return;
int mid=(l+r)>>;
if(mid>=g)Insert(ch[pre][],ch[rt][],l,mid,g,d);
else Insert(ch[pre][],ch[rt][],mid+,r,g,d);
} int Query(int rt,int l,int r,int a,int b){
if(l>=a&&r<=b)return sum[rt];
int mid=(l+r)>>,ret=;
if(mid>=a)ret=Query(ch[rt][],l,mid,a,b);
if(mid<b)ret+=Query(ch[rt][],mid+,r,a,b);
return ret;
}
void Init(){
memset(rt,,sizeof(rt));
memset(head,,sizeof(head));
memset(pre,,sizeof(pre));
memset(son,,sizeof(son));
memset(nxt,,sizeof(nxt));
memset(fa,,sizeof(fa));
memset(sum,,sizeof(sum));
memset(ok,,sizeof(ok));cnt=;
}
int main(){
int T,Q,n,l,r;a[]=-;
scanf("%d",&T);
while(T--){
Init();
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<=n;i++)
Hash[i]=a[i];
sort(Hash+,Hash+n+);
for(int i=;i<=n;i++)
a[i]=lower_bound(Hash+,Hash+n+,a[i])-Hash;
for(int i=;i<n;i++)
if(a[i-]<=a[i]&&a[i]<=a[i+])
ok[i]=;
for(int i=;i<=n;i++){
pre[i]=head[a[i]];
nxt[pre[i]]=i;
head[a[i]]=i;
}
for(int i=;i<n;i++)
if(ok[i]){
int j=pre[i];
while(j&&(a[j-]!=a[i-]||a[j+]!=a[i+])){j=pre[j];}
fa[i]=j;son[j]=i;
}
for(int i=;i<n;i++){
if(!fa[i]&&ok[i])
Insert(rt[],rt[],,n,i,);
} for(int i=;i<n;i++){
if(!ok[i]){
rt[i]=rt[i-];
continue;
}
Insert(rt[i-],rt[i],,n,i,-);
if(son[i])Insert(rt[i],rt[i],,n,son[i],);
}
scanf("%d",&Q);
while(Q--){
scanf("%d%d",&l,&r);
printf("%d\n",r->=l?Query(rt[l],,n,,r-):);
}
}
return ;
}