题意:序列长度为n(1<= n <= 200,000)的序列，有Q(<=200,000)次区间查询，问区间[l,r]中有多少个不同的连续递增的三元组。
思路:连续三元组->递推O(n)将第一次出现该三元组的下标记录到树状数组中，并且用一个Next[]来表示递推关系，即同一个三元组下一次出现的位置是Next[x];这很关键，在之后按照左边界处理时(有点像莫队算法)，一直递推在l+1左侧重复出现的三元组，为了把该三元组推到出现在[l,r]或者[r+1,..]中，这样不重不漏。
使用map维护出现的id即可，题目很经典~~
#include<bits/stdc++.h> using namespace std; #define rep0(i,l,r) for(int i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <= (r);i++) #define rep_0(i,r,l) for(int i = (r);i > (l);i--) #define rep_1(i,r,l) for(int i = (r);i >= (l);i--) #define MS0(a) memset(a,0,sizeof(a)) #define MS1(a) memset(a,-1,sizeof(a)) #define MSi(a) memset(a,0x3f,sizeof(a)) #define inf 0x3f3f3f3f #define lson l, m, rt << 1 #define rson m+1, r, rt << 1|1 typedef pair<int,int> PII; #define A first #define B second #define MK make_pair typedef __int64 ll; typedef unsigned int uint; template<typename T> void read1(T &m) { T x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} m = x*f; } template<typename T> void read2(T &a,T &b){read1(a);read1(b);} template<typename T> void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);} template<typename T> void out(T a) { if(a>9) out(a/10); putchar(a%10+'0'); } int T,kase = 1,i,j,k,n,m,l,r; #define N 200200 map<pair<PII,int>,int> mp; int a[N],B[N],Next[N],x[N],y[N],o[N],ans[N]; bool cmp(int a,int b){return x[a] < x[b];} #define lowbit(x) (x&(-x)) void update(int p,int d) { while(p <= n) B[p] += d,p += lowbit(p); } int query(int x) { int ans = 0; while(x) ans += B[x],x -= lowbit(x); return ans; } int main() { //freopen("data.txt","r",stdin); //freopen("out.txt","w",stdout); read1(T); while(T--){ mp.clear(); read1(n); rep1(i,1,n) B[i] = Next[i] = 0; rep1(i,1,n) read1(a[i]); rep1(i,3,n){ if(a[i] >= a[i-1] && a[i-1] >= a[i-2]){ int x = mp[MK(MK(a[i],a[i-1]),a[i-2])]; if(x == 0) update(i,1); else Next[x] = i;//递推 mp[MK(MK(a[i],a[i-1]),a[i-2])] = i; } } read1(m); rep0(i,0,m) read2(x[i],y[i]),o[i] = i; sort(o,o+m,cmp); int p = 1; rep0(i,0,m){ int l = x[o[i]],r = y[o[i]]; while(p <= l+1){ if(Next[p]) update(Next[p],1);//递推到下一个~~ p++; } if(r > l + 1) ans[o[i]] = query(r) - query(l+1); else ans[o[i]] = 0; } rep0(i,0,m){ printf("%d ",ans[i]); } } return 0; }