poj2777

题目链接

线段树练习_poj2777

题解

很膨胀+1

写线段树的题都很膨胀,但是每次调的时候像个sb

区间修改区间查询 \(lazy\)标记可以保证不出错误的打完.

不同的题目有不同的 \(pushup/pushdown\)的操作.应该也没什么问题.

但是读优写错是几个意思….

拿数据硬怼.发现读优写错…


对于这道题,区间染色问题.

我们没办法做到让每一个节点都存30个\(bool\)值.

所以 状压

我们把30个状态压缩到一个int类型里面,用二进制的每一位表示每一种状态

\(int\)类型的最大值大于\(2^{30}\),所以可以.

\(solve\)函数的时间复杂度是\(O(30)\)常数级别的.

所以总的时间复杂度是 \(O(Mlog_2N)\)

仔细想想这个状压还是蛮有意思的呢.

我们用 \(sum\)&1,判读最后一位是否为1,每次把\(sum\)右移一个.

\(pushup\)的时候用|,两个里面都出现了这种颜色,不变,只有一个出现,这个值就变化了.

注意在\(update\)的时候我们是要状压到第x位中.

所以加值的时候 1<<(x-1)


By:Wahacer

2017.12.20

11:09

发表评论

电子邮件地址不会被公开。 必填项已用*标注