#include <iostream>#include <map>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int MAXN = 30010,MAXLOG = 20;struct ChairTree{int l,r;int ans;}ct[MAXN*MAXLOG];int ctRoot[MAXN];int ctTop;int num[MAXN],tnum[MAXN],pre[MAXN];int CreatNewNode(){ct[ctTop].l = -1,ct[ctTop].r = -1;ct[ctTop].ans = 0;return ctTop++;}void InitZeroLayer(int &root,int l,int r){root = CreatNewNode();if(l == r)return ;int mid = (l+r)>>1;InitZeroLayer(ct[root].l,l,mid);InitZeroLayer(ct[root].r,mid+1,r);}int BS(int L,int R,int x){int mid;while(L <= R){mid = (L+R)>>1;if(tnum[mid] == x)return mid;if(tnum[mid] < x)L = mid+1;elseR = mid-1;}return -1;}void PushUp(int root){ct[root].ans = ct[ct[root].l].ans + ct[ct[root].r].ans;}void Update(int pre,int &root,int L,int R,int goal,int info){if(root == -1 || root == pre){root = CreatNewNode();ct[root].ans = ct[pre].ans;}if(L == R){ct[root].ans += info;return ;}int mid = (L+R)>>1;if(goal <= mid){if(ct[root].r == -1)ct[root].r = ct[pre].r;Update(ct[pre].l,ct[root].l,L,mid,goal,info);}else{if(ct[root].l == -1)ct[root].l = ct[pre].l;Update(ct[pre].r,ct[root].r,mid+1,R,goal,info);}PushUp(root);}void InitCt(int n){memset(pre,-1,sizeof(pre));sort(tnum+1,tnum+n+1);int site,tn,i;for(tn = 1,i = 2;i <= n; ++i)if(tnum[i] != tnum[tn])tnum[++tn] = tnum[i];memset(ctRoot,-1,sizeof(ctRoot));ctTop = 0;InitZeroLayer(ctRoot[0],1,n);for(i = 1;i <= n; ++i){site = BS(1,tn,num[i]);if(pre[site] == -1)Update(ctRoot[i-1],ctRoot[i],1,n,i,1);else{Update(ctRoot[i-1],ctRoot[i],1,n,pre[site],-1);Update(ctRoot[i-1],ctRoot[i],1,n,i,1);}pre[site] = i;}}int Query(int root,int goal,int L,int R){if(goal == L)return ct[root].ans;int mid = (L+R)>>1;if(mid+1 <= goal)return Query(ct[root].r,goal,mid+1,R);return Query(ct[root].l,goal,L,mid) + ct[ct[root].r].ans;}int main(){int i,l,r,q,n;while(scanf("%d",&n) != EOF){for(i = 1;i <= n; ++i){scanf("%d",&num[i]);tnum[i] = num[i];}InitCt(n);scanf("%d",&q);while(q–){scanf("%d %d",&l,&r);printf("%d\n",Query(ctRoot[r],l,1,n));}}return 0;}
，不是每个人都一定快乐，不是每种痛都一定要述说。
