很久不写划分树了，果然各种NC错误
按照我的理解，划分树即一个线段树（用来确定数组下标和层次）以及一个log2(n)*n的数组，来记录划分信息
这题实现4个操作：
1、插入
按照划分树的定义，如果小于有序表中中间节点的值，就递归插入左子树，否则递归插入右子树。更新当前区间段的划分信息（无非就是往后计算一个）
2、询问s,e区间第k小数
查询s,e区间里面划分到左子树的个数i，如果i>=k，那么显然递归到左子树查询，否则就是递归到右子树查询k-i小的数。注意！这里要重新定位左子树和右子树中的区间，由于是闭区间，那么做端点为s+sum(s-1),右端点为s+sum(e)-1，这个减一丢了。。调了我半天。。哎。。以前写都是左闭右开区间的，结果习惯了。。
3、查询值为k的数的位次
这个需要一个辅助数组，记录值为k的数插在最顶层区间的哪个位置了。这个办好后，就容易了，如果数被划分到了左子树，那么递归查询左子树，否则返回递归查询右子树的值加上当前区间被划分到左子树的个数
4、查询rank k的数
同样是这样，如果当前区间被划分到左子树的个数小于等于k，那么递归查询左子树，否则递归查询右子树中rank为k-左子树的size。
大概思想就是这样了，实现有很多细节，比如说假设p==区间左端点（左区间木有数），那么算sum(p-1)的时候就要特判下了。我喜欢用三元式，很方便。
代码
# include <cstdio>
# include <cstring>
# include <map>
using namespace std
;
# define N 100005
int arr
[20][N
];
struct node
{
int s
,e
,layer
;
int c
;
}st
[4*N
];
int q
[500000][4],c
;
int remap
[N
],position
[N
];map
<int,int> refer
;
void init
(int s
,int e
,int layer
,int pos
=1)
{ st
[pos
].s
=s
;st
[pos
].e
=e
; st
[pos
].layer
=layer
; st
[pos
].c
=st
[pos
].s
;
if(s
!=e
) init
(s
,(s
+e
)/2,layer
+1,pos
<<1),init
((s
+e
)/2+1,e
,layer
+1,(pos
<<1)+1);
}
void insert
(int value
,int pos
=1)
{
if(st
[pos
].s
==st
[pos
].e
) arr
[st
[pos
].layer
][st
[pos
].c
++]=value
;
else
{
if(value
<=(st
[pos
].s
+st
[pos
].e
)/2)
{ arr
[st
[pos
].layer
][st
[pos
].c
]=(st
[pos
].c
==st
[pos
].s
?0:arr
[st
[pos
].layer
][st
[pos
].c
-1])+1; st
[pos
].c
++; insert
(value
,pos
<<1);
}
else
{ arr
[st
[pos
].layer
][st
[pos
].c
]=(st
[pos
].c
==st
[pos
].s
?0:arr
[st
[pos
].layer
][st
[pos
].c
-1]); st
[pos
].c
++; insert
(value
,(pos
<<1)+1);
}
}
}
int q1
(int s
,int t
,int k
,int pos
=1)
{
if(st
[pos
].s
==st
[pos
].e
)
return remap
[arr
[st
[pos
].layer
][st
[pos
].s
]];
else
{
if(arr
[st
[pos
].layer
][t
]-(s
==st
[pos
].s
?0:arr
[st
[pos
].layer
][s
-1])>=k
)//left
return q1
(st
[pos
].s
+(s
==st
[pos
].s
?0:arr
[st
[pos
].layer
][s
-1]),st
[pos
].s
+arr
[st
[pos
].layer
][t
]-1,k
,pos
<<1);
else//right
{ k
-=arr
[st
[pos
].layer
][t
]-(s
==st
[pos
].s
?0:arr
[st
[pos
].layer
][s
-1]);
return q1
((st
[pos
].s
+st
[pos
].e
)/2+1+s
-1-st
[pos
].s
+1-(s
==st
[pos
].s
?0:arr
[st
[pos
].layer
][s
-1]),(st
[pos
].s
+st
[pos
].e
)/2+1+t
-st
[pos
].s
+1-arr
[st
[pos
].layer
][t
]-1,k
,(pos
<<1)+1);
}
}
}
int q2
(int s
,int pos
=1)
{
if(st
[pos
].s
==st
[pos
].e
) return 1;
else if(arr
[st
[pos
].layer
][s
]-(s
==st
[pos
].s
?0:arr
[st
[pos
].layer
][s
-1]))
return q2
(st
[pos
].s
+arr
[st
[pos
].layer
][s
]-1,pos
<<1);
else
return (st
[pos
].c
==st
[pos
].s
?0:arr
[st
[pos
].layer
][st
[pos
].c
-1])+q2
((st
[pos
].s
+st
[pos
].e
)/2+1+s
-st
[pos
].s
+1-arr
[st
[pos
].layer
][s
]-1,(pos
<<1)+1);
}
int q3
(int k
,int pos
=1)
{
if(st
[pos
].s
==st
[pos
].e
) return remap
[arr
[st
[pos
].layer
][st
[pos
].s
]];
else if(k
<=(st
[pos
].c
==st
[pos
].s
?0:arr
[st
[pos
].layer
][st
[pos
].c
-1])) return q3
(k
,pos
<<1);
else return q3
(k
-(st
[pos
].s
==st
[pos
].c
?0:arr
[st
[pos
].layer
][st
[pos
].c
-1]),(pos
<<1)+1);
}
int main()
{
int n
,test
=1;
while(scanf
("%d",&n
)!=EOF
)
{ refer
.clear
();c
=1; memset
(arr
,0,sizeof(arr
));
for(int i
=0;i
<n
;i
++)
{
char tmp
[12]; scanf
("%s",tmp
);
if(*tmp
=='I') q
[i
][0]=0;
else q
[i
][0]=tmp
[6]-48;
switch(q
[i
][0])
{
case 0: scanf
("%d",&q
[i
][1]); refer
[q
[i
][1]]=0;
break;
case 1: scanf
("%d%d%d",&q
[i
][1],&q
[i
][2],&q
[i
][3]);
break;
default: scanf
("%d",&q
[i
][1]);
break;
};
}
for(map
<int,int>::iterator i
=refer
.begin
();i
!=refer
.end
();i
++) remap
[c
]=i
->first
,i
->second
=c
++; init
(1,c
-1,0);
long long t
[4]={0,0,0,0};
int now
=1;
for(int i
=0;i
<n
;i
++)
switch(q
[i
][0])
{
case 0: insert
(refer
[q
[i
][1]]); position
[refer
[q
[i
][1]]]=now
++;
break;
case 1: t
[1]+=q1
(q
[i
][1],q
[i
][2],q
[i
][3]);
break;
case 2: t
[2]+=q2
(position
[refer
[q
[i
][1]]]);
break;
case 3: t
[3]+=q3
(q
[i
][1]);
break;
}; printf
("Case %d:\n%I64d\n%I64d\n%I64d\n",test
++,t
[1],t
[2],t
[3]);
}
return 0;
}