记录编号	367841	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[東方] 博丽灵梦 梦想妙珠	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	2.122 s
提交时间	2017-02-02 14:20:46	内存使用	1.32 MiB

#include <cstdio>
#include <cstring>
#include <cctype>
#include <list>
#include <queue>
#include <vector>
using namespace std;
namespace IO{
  char buf[1<<18], *fs, *ft;
  inline char readc(){
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
  }
  inline int readint(){
    char c; int r;
    while(c = readc()){if(c >= '0' && c <= '9'){r = c^0x30;break;}}
    while(isdigit(c = readc()))r = (r<<3)+(r<<1)+(c^0x30);
    return r;
  }
}; using IO::readint; using IO::readc;
struct node{
  node *ls, *rs;
  int cnt;
  #define CNT(x) ((x)?(x)->cnt:0)
  node(){memset(this, 0, sizeof(node));}
  void pushup(){cnt = CNT(ls)+CNT(rs);}
};
node *build(int l, int r){
  if(l > r)return NULL;
  node *d = new node();
  if(l < r){
    int m = (l+r)>>1;
    d->ls = build(l, m);
    d->rs = build(m+1, r);
  }
  return d;
}
node *insert(node *x, int p, int L, int R){
  if(!x)return NULL;
  node *d = new node(); *d = *x;
  if(L == R && p == R){d->cnt++; return d;}
  else{
    int M = (L+R)>>1;
    if(p <= M)d->ls = insert(d->ls, p, L, M);
    else if(p > M)d->rs = insert(d->rs, p, M+1, R);
    d->pushup();return d;
  }
}
int query(node *x, int p, int L, int R){
  if(!x)return 0;
  if(p == L && p == R)return x->cnt;
  int M = (L+R)>>1;
  if(p <= M)return query(x->ls, p, L, M);
  else if(p > M)return query(x->rs, p, M+1, R);
}
int col[100001];
node *roots[100001];
int main(){
  freopen("mengxiangmiaozhu.in", "r", stdin);
  freopen("mengxiangmiaozhu.out", "w", stdout);
  int n = readint();
  int maxc = 0;
  for(int i = 1; i <= n; i++)col[i] = readint(), maxc = max(maxc, col[i]);
  roots[0] = build(1, maxc);
  for(int i = 1; i <= n; i++)roots[i] = insert(roots[i-1], col[i], 1, maxc);
  int q = readint();
  while(q--){
    int l = readint(); int r = readint();
    int c = readint();
    printf("%d\n", query(roots[r], c, 1, maxc) - query(roots[l-1], c, 1, maxc));
  }
  return 0;
}