目前能过的做法都是离线的，难道这个题强制离线吗? 我的主席树在线做法TLE了#8,#9, #10三个点。 https://www.luogu.com.cn/record/34870857

#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

#define LOCAL 0
#define CONFIG_USE_PERSISTENT_SEGMENTTREE 1
#define CONFIG_USE_BITTREE 0 //offline
#define MAXN 1000000
#define MAXM 1000000

int32_t digits[MAXN+1];
int32_t buffer[MAXN+1];

#if CONFIG_USE_PERSISTENT_SEGMENTTREE 
struct SegmentNode {
  int32_t sum;
  uint32_t lc;
  uint32_t rc;
};

int last[MAXN+1];
SegmentNode tree[MAXN*22+1];
uint32_t roots[MAXN+1];
int id = 0;

//interval [low, high)
uint32_t PersistentSegmentTreeBuild(int low, int high)
{
  uint32_t root = ++id;
  tree[root].sum = 0;
  if (low+1==high) {
    tree[root].lc = 0;
    tree[root].rc = 0;
  } else {
    int mid = (low+high)/2;
    tree[root].lc = PersistentSegmentTreeBuild(low, mid);
    tree[root].rc = PersistentSegmentTreeBuild(mid, high);
  }
  return root;
}

//interval [low, high)
uint32_t PersistentSegmentTreeAdd(uint32_t index, int low, int high, int key)
{
  uint32_t idx = ++id;
  tree[idx].sum = tree[index].sum + 1;
  if (low+1==high) {
    tree[idx].lc = 0;
    tree[idx].rc = 0;
  } else {
    int mid = (low+high)/2;
    if (key < mid) {
      tree[idx].rc = tree[index].rc;
      tree[idx].lc = PersistentSegmentTreeAdd(tree[index].lc, low, mid, key);
    } else {
      tree[idx].lc = tree[index].lc;
      tree[idx].rc = PersistentSegmentTreeAdd(tree[index].rc, mid, high, key);
    }
  }
  return idx;
}

//[left, right) interval
uint32_t RangeRank(int total, int left, int right, int key)
{
  uint32_t rank = 0;
  int lroot, rroot;
  int low, high, mid;
  lroot = roots[left];
  rroot = roots[right];
  low = 0;
  high = total;
  while (low+1 != high) {
    mid = (low+high)/2;
    if (key < mid) {
      lroot = tree[lroot].lc;
      rroot = tree[rroot].lc;
      high = mid;
    } else {
      rank += tree[tree[rroot].lc].sum - tree[tree[lroot].lc].sum;
      lroot = tree[lroot].rc;
      rroot = tree[rroot].rc;
      low = mid;
    }
  }
  return rank;
}
#endif

int ReadInteger(void)
{
  int x=0, sign=1;
  int ch;
  ch = getchar();
  while (ch<'0' || ch>'9') {
    if (ch=='-') {
      sign = -1;
    }
    ch = getchar();
  }
  while (ch>='0' && ch<='9') {
    x = x*10 + ch-'0';
    ch = getchar();
  }
  return x*sign;
}

int main(void)
{
#if LOCAL
  freopen("test.in", "r", stdin);
  freopen("test.out", "w", stdout);
#endif
  int n, m;
  int left, right;
  int total;
  n = ReadInteger();
  digits[0] = 0;
  for (int i=1; i<=n; ++i) {
    digits[i] = ReadInteger();
  }
  memcpy(buffer, digits, (1+n)*sizeof(digits[0]));
  sort(buffer+1, buffer+n+1);
  total = unique(buffer+1, buffer+n+1)-(buffer+1);
  for (int i=1; i<=n; ++i) {
    digits[i] = lower_bound(buffer+1, buffer+total+1, digits[i]) - (buffer+1);  //index starts from 0
  }
  memset(buffer, 0, total*sizeof(buffer[0]));
  m = ReadInteger();
#if CONFIG_USE_PERSISTENT_SEGMENTTREE
  uint32_t rank;
  for (int i=1; i<=n; ++i) {
    if (buffer[digits[i]] == 0) {
      last[i] = 0;
    } else {
      last[i] = buffer[digits[i]];
    }
    buffer[digits[i]] = i;
  }
  roots[0] = PersistentSegmentTreeBuild(0, n);
  for (int i=1; i<=n; ++i) {
    roots[i] = PersistentSegmentTreeAdd(roots[i-1], 0, n, last[i]);
  }
  for (int i=0; i<m; ++i) {
    left = ReadInteger();
    --left;   //index starts from 0
    right = ReadInteger();
    rank = RangeRank(n, left, right, left+1);
    printf("%d\n", rank); 
  }
#endif
  return 0;
}