HDU 5654 xiaoxin and his watermelon candy

Problem Description

During his six grade summer vacation, xiaoxin got lots of watermelon candies from his leader when he did his internship at Tencent. Each watermelon candy has it's sweetness which denoted by an integer number.

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

Input

T(T≤10) which represents the number of test cases.

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].

Output

For each query, print an integer which represents the number of ways xiaoxin can choose a triplet.

Sample Input

1
5
1 2 3 4 5
3
1 3
1 4
1 5      

Sample Output

1

2

3

線上要可持久化線段樹，離線直接樹狀數組就可以。

#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<string>
#include<map>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int low(int x){ return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
int T, n, m;
int a[maxn], f[maxn], ans[maxn], tot, p[maxn];

struct point
{
  int l, r, id;
  void read(int x){ scanf("%d%d", &l, &r); id = x; }
  bool operator<(const point&a)const
  {
    return r == a.r ? l == a.l ? id < a.id : l < a.l : r < a.r;
  }
  point(int l = 0, int r = 0, int id = 0) :l(l), r(r), id(id){}
}q[maxn];

void add(int x, int y)
{
  for (int i = x; i <= n; i += low(i)) f[i] += y;
}

int sum(int x)
{
  int ans = 0;
  for (int i = x; i; i -= low(i)) ans += f[i];
  return ans;
}

int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), f[i] = 0;
    scanf("%d", &m);
    for (int i = 0; i < m; i++) q[i].read(i), ans[i] = 0;
    sort(q, q + m);
    map<point, int> M;    tot = 0;
    for (int i = 1, j = 0; i <= n; i++)
    {
      if (i + 2 <= n&&a[i] <= a[i + 1] && a[i + 1] <= a[i + 2])
      {
        if (!M[point(a[i], a[i + 1], a[i + 2])])
        {
          M[point(a[i], a[i + 1], a[i + 2])] = ++tot;
          p[tot] = 0;
        }
        int x = M[point(a[i], a[i + 1], a[i + 2])];
        add(p[x] + 1, 1);    add(i + 1, -1);     p[x] = i;
      }
      for (; j < m&&q[j].r <= i + 2; j++)
      {
        if (q[j].r - q[j].l < 2) continue;
        ans[q[j].id] = sum(q[j].l);
      }
    }
    for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
  }
  return 0;
}