南
昌
网络
赛
题
解
PERFECT NUMBER PROBLEM
#include<stdio.h>
intmain(){
intx[5]={1,2,4,6,12};
inti;
for(i=0;i<5;i++){
printf("%d",(1<<x[i])*((1<<x[i]+1)-1));
}
return0;
}
Greedy HOUHOU
考
虑
用
线
段
树
维
护
这
个
序
列
,
对
于
线
段
树
的
一个
节
点
,
我
们
用
表
示
当
选
取
的
区
间
恰
好
是
这
个
节
点
对
应
区
间
时
的
最
优
解
,
用
和
表
示
节
点
的
左
儿
子
和右
儿
子
标
号
,
显
然
,
,
是
个
未
知
数
,
现
在
考
虑
如
何
求
,
我
们
设
节
点
的
最
小
值
为
,
再
设
节
点
的
左
儿
子
为
,
右
儿
子
为
,
显
然
,
一
定
会
被
HOUHOU
吃
掉
,
然
后
考
虑
节
点
,
如
果
节
点
tl
的
最
小
值
不
小
于
,
那
么
,
节
点
tl
对
应
的
整
个
区
间
HOUHOU
都
会
忽
略
掉
,
这
个
时
候
我
们
只
需
要
考
虑
节
点
,
反
之
,
节
点
的
最
小
值
一
定
会
被
吃
掉
,
那
么
节
点
对
的
贡
献
一
定
为
(
原
因
留
给
读
者
思
考
)
。
根
据
上
述过
程
,
在
计
算
的
时
候
,
我
们
需
要
递
归
搜
索
节
点
及
它
的
后
代
,
但
是
对
于任
意
一个
节
点
,
我
们
要
么
前
往
它
的
左
儿
子
,
要
么
前
往
它
的
右
儿
子
,
换
句
话说
,
我
们
在
给
一个
节
点
计
算
的
值
时
,
至
多
需
要
搜
索
个
节
点
,
那
么
计
算
/
更
新
一个
节
点
信
息
的
时
间
复
杂
度
为
,
由
于
线
段
树
只
有
个
节
点
,
因
此
建
树
的
复
杂
度
为
。
有
了以
上
的
分
析
,
查
询
和
更
新操
作
就
很
容
易
了
,
对
于
查
询
,
线
段
树
的
区
间
查
询
至
多
需
要
查
个
节
点
,
如
果
我
们
把
这
些
节
点
按
他们
维
护
的
区
间
的
左
端
点
升
序
排
序
,
那
么
影
响
第
个
节
点
答
案
的
是
第
个
区
间
的
最
小
值
,
那
么
我
们
在
查
询
第
个
节
点
的
时
候
,
将
第
个
节
点
的
最
小
值
记
录
下,
然
后
利
用
上
述过
程
递
归
搜
索
第
个
节
点
对
应
的
子
树
就
可
以
得
到
这
个
节
点
贡
献
的
答
案
,
因
此
,
单
次
查
询
的
时
间
复
杂
度
为
,
更
新操
作
同
理
,
单
次
更
新
需
要
更
新
个
节
点
,
每
个
节
点
更
新
信
息
的
时
间
复
杂
度
为
,
因
此
单
次
更
新
的
时
间
复
杂
度
也
是
。
k f[k]
ls rs k
f[k] = f[ls] + v v v ls w
rs tl tr w rs
w
tr tl tr v
f[rs] − f[tl] f[k]
rs
v log n
O(log n) n
O(n log n)
log n
i i − 1 i
i − 1 i
O((log n) )
2
log n
O(log n) O((log n) )
2