C++基础(线段树学习)

一个细分树的标题，POI2000的推广，首先构建了一个【1，100，000】的细分树。结果超级内存被哈希，结构被优化，却是错误答案，最后所有的int都改成__int64。我终于得到了
标题
描述
超级市场网要求你写一个程序来模拟正在准备的促销活动的费用。
促销必须遵守以下规则:
1 .一位想参加促销活动的顾客在账单上写下自己的个人信息，并把它扔进一个特殊的投票箱。
2。在促销活动的每一天结束时，从投票箱中取出两个法案:
***金额最高的第一个法案被选中，
***然后金额最低的法案被选中；
支付金额最大的顾客将获得一笔奖金，金额相当于他账单上的金额与账单上金额最小的金额之间的差额。
3。为了避免一次购买中多个奖项，根据上述规则选择的两个钞票都不返回投票箱，但是所有剩余的钞票仍然参与促销。
超市的营业额非常大，因此可以假设，在每天结束时，在取出金额最大和最小的钞票之前，投票箱中至少有两张钞票。
你的任务是根据促销活动当天投入投票箱的钞票价格信息，计算整个促销活动中奖品的总成本。
Task
编写一个程序，它:
1 .读取促销活动的每一天投入投票箱的钞票上的价格列表，
2 .计算促销活动连续几天支付的奖金的总成本，
3 .写出结果。
Input
第一行包含一个正整数n，其中1接下来的n行中的每一行都包含一个由单个空格分隔的非负整数序列。文件的第(i+1)行中的数字代表在促销的第I天投入投票箱的钞票的价格。该行中的第一个整数是k，0。在整个促销活动中，投入投票箱的钞票总数不超过10^6.
Output
out应该恰好包含一个整数，它等于整个促销活动中支付的奖品总成本。
示例输入
5
3 1 2 3
2 1 1
4 10 5 5 1
0
1 2
示例输出
19代码
# include
使用命名空间STD
const _ _ int 64 MAXN = 10000；
结构节点
{
__int64 l，r，cnt
NODE *left_child，* right _ child
}；
向量哈希[10001]；
void build ( NODE *v，__int64 l，_ _ int 64 r)
{
NODE * p；
_ _ int 64m；
if(l > = r)
return；
m =(l+r)> > 1；
p =新节点；
p>l=l，p>r=m，p>cnt=0，p > left _ child = p > right _ child = NULL；
v > left _ child = p；
build(p，l，m)；
p =新节点；
p>l=m+1，p>r=r，p>cnt=0，p > left _ child = p > right _ child = NULL；
v > right _ child = p；
build(p，m+1，r)；
}
void ins ( __int64 d，NODE * v)
{
_ _ int 64m；
if(v = = NULL)
return；
if(v > lr)
{
v > cnt++；
m =(v > l+v > r)/2；
if ( d ins(d，v > left _ child)；
else
ins(d，v > right _ child)；
}
}
void del(_ _ int 64d，NODE * v)
{
_ _ int 64m；
if(v = = NULL)
return；
if(v > lr)
{
if(v > CNT > 0)
v > CNT；
m =(v > l+v > r)/2；
if ( d del(d，v > left _ child)；
else
del(d，v > right _ child)；
}
}
_ _ int 64 max(NODE * v)
{
if(v > left _ child = = NULL | | v > right _ child = = NULL)
return v > r；
if(v > right _ child > CNT)
return max(v > right _ child)；
else
return max(v > left _ child)；
}
_ _ int 64min(NODE * v)
{
if(v > left _ child = = NULL | | v > right _ child = = NULL)
return v > l；
if(v > left _ child > CNT)
return min(v > left _ child)；
else
return min(v > right _ child)；
}
_ _ int 64 hash _ max(_ _ int 64 f)
{
vector::iterator p，q；
_ _ int 64 RES；
for ( p=q=hash[f])。begin()；p！=hash[f]。end()；p++)
if(* q q = p；
RES = * q；
hash[f]。擦除(q)；
return RES；
}
_ _ int 64 hash _ min(_ _ int 64 f)
{
vector::iterator p，q；
_ _ int 64 RES；
for ( p=q=hash[f])。begin()；p！=hash[f]。end()；p++)
if(* q > * p)
q = p；
RES = * q；
hash[f]。擦除(q)；
return RES；
}
int main()
{
NODE * head；
__int64 c，k，I，j，d，maxnum，minnum，RES = 0；
head =新节点；
head>cnt=0，head>l=0，head>r=MAXN，head > left _ child = head > right _ child = NULL；
build(head，0，MAXN)；
scanf("%I64d "，& c)；
for(I = 0；i {
scanf("%I64d "，& k)；
for(j = 0；j {
scanf("%I64d "，& d)；
哈希[d/100]。push _ back(d)；
ins(d/100，头)；
}
maxnum = max(head)；
minnum=min(头)；
RES+= hash _ max(maxnum)hash _ min(minnum)；
del(maxnum，head)；
del(minnum，head)；
}
printf("%I64d\n "，RES)；
}
刚开始接触段树，还是无法离散化~继续学习。