很久不寫(xiě)劃分樹(shù)了，果然各種NC錯(cuò)誤
按照我的理解，劃分樹(shù)即一個(gè)線段樹(shù)（用來(lái)確定數(shù)組下標(biāo)和層次）以及一個(gè)log2(n)*n的數(shù)組，來(lái)記錄劃分信息
這題實(shí)現(xiàn)4個(gè)操作：
1、插入
按照劃分樹(shù)的定義，如果小于有序表中中間節(jié)點(diǎn)的值，就遞歸插入左子樹(shù)，否則遞歸插入右子樹(shù)。更新當(dāng)前區(qū)間段的劃分信息（無(wú)非就是往后計(jì)算一個(gè)）
2、詢問(wèn)s,e區(qū)間第k小數(shù)
查詢s,e區(qū)間里面劃分到左子樹(shù)的個(gè)數(shù)i，如果i>=k，那么顯然遞歸到左子樹(shù)查詢，否則就是遞歸到右子樹(shù)查詢k-i小的數(shù)。注意！這里要重新定位左子樹(shù)和右子樹(shù)中的區(qū)間，由于是閉區(qū)間，那么做端點(diǎn)為s+sum(s-1),右端點(diǎn)為s+sum(e)-1，這個(gè)減一丟了。。調(diào)了我半天。。哎。。以前寫(xiě)都是左閉右開(kāi)區(qū)間的，結(jié)果習(xí)慣了。。
3、查詢值為k的數(shù)的位次
這個(gè)需要一個(gè)輔助數(shù)組，記錄值為k的數(shù)插在最頂層區(qū)間的哪個(gè)位置了。這個(gè)辦好后，就容易了，如果數(shù)被劃分到了左子樹(shù)，那么遞歸查詢左子樹(shù)，否則返回遞歸查詢右子樹(shù)的值加上當(dāng)前區(qū)間被劃分到左子樹(shù)的個(gè)數(shù)
4、查詢r(jià)ank k的數(shù)
同樣是這樣，如果當(dāng)前區(qū)間被劃分到左子樹(shù)的個(gè)數(shù)小于等于k，那么遞歸查詢左子樹(shù)，否則遞歸查詢右子樹(shù)中rank為k-左子樹(shù)的size。
大概思想就是這樣了，實(shí)現(xiàn)有很多細(xì)節(jié)，比如說(shuō)假設(shè)p==區(qū)間左端點(diǎn)（左區(qū)間木有數(shù)），那么算sum(p-1)的時(shí)候就要特判下了。我喜歡用三元式，很方便。
代碼
# 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;
}