发现网上并没有这一题的Splay做法。。。SplayTree模板点这里 其实是水题，所以不做讲解。 这里只是来贡献代码。。。
树状数组：
/* ID: Sunshine_cfbsl LANG: C++ */ #include<cstdio> #include<algorithm> #include<cstring> #include<iostream> using namespace std; int C[32010], n, ans[15010]; int lowbit(int x) { return x & (-x); } int sum(int x) { int ret = 0; while(x > 0) { ret += C[x]; x -= lowbit(x); } return ret; } void add(int x) { while(x <= 32001) { C[x]++; x += lowbit(x); } } int main() { int i, tmp; scanf("%d", &n); for(i = 1; i <= n; i++) { scanf("%d", &tmp); ans[sum(++tmp)]++; add(tmp); scanf("%d", &tmp); } for(i = 0; i < n; i++) printf("%d\n", ans[i]); return 0; }SplayTree：
/* ID: Sunshine_cfbsl LANG: C++ */ #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN = 150010; struct Splay_Tree { int fa[MAXN], ch[MAXN][2], data[MAXN], size[MAXN], v[MAXN], r, pn; void clear(int x) { r = pn = 1; memset(fa, 0, sizeof(fa)); memset(ch, 0, sizeof(ch)); memset(data, 0, sizeof(data)); memset(v, 0, sizeof(v)); memset(size, 0, sizeof(size)); size[1] = v[1] = 1; data[1] = x; } void maintain(int p) { size[p] = size[ch[p][0]]+size[ch[p][1]]+v[p]; } void Rotate(int p, bool t) { int f = fa[p]; fa[ch[f][t^1] = ch[p][t]] = f; fa[ch[fa[f]][ch[fa[f]][1]==f] = p] = fa[f]; ch[fa[f] = p][t] = f; maintain(f); } void splay(int x) { int p; while(fa[x]) { p = fa[x]; if(!fa[p]) { Rotate(x, x==ch[p][0]); break; } bool f = x==ch[p][0], f1 = p==ch[fa[p]][0], f2 = p==ch[fa[p]][1]; Rotate(f?f1?p:x:f2?p:x, f); Rotate(x, f1); } maintain(x); r = x; } void insert(int x) { int p = r; while(true) { size[p]++; if(x == data[p]) { v[p]++; break; } if((x<data[p] && !ch[p][0]) || (x>data[p] && !ch[p][1])) { fa[++pn] = p; ch[p][x>data[p]] = pn; data[pn] = x; size[pn] = v[pn] = 1; p = pn; break; } p = ch[p][x>data[p]]; } splay(p); } }tree; int main() { int i, n, tmp, cnt[MAXN]; scanf("%d", &n); scanf("%d", &tmp); tree.clear(tmp); cnt[0]++; scanf("%d", &tmp); for(i = 2; i <= n; i++) { scanf("%d", &tmp); tree.insert(tmp); if(tree.ch[tree.r][0]) cnt[tree.size[tree.ch[tree.r][0]]+tree.v[tree.r]-1]++; else cnt[tree.v[tree.r]-1]++; scanf("%d", &tmp); } for(i = 0; i < n; i++) printf("%d\n", cnt[i]); return 0; }