Description
\(n\) 座城市在数轴上, 第 \(i\) 座城市有一条连向第 \(i+1\) 座城市的单项边. 每座城市有一个类型 A/B 以及一个非负整数人口, A 类城市的人觉得自己的城市比 B 类城市高级, 所以若一座 A 类城市能通过单向道路到达一个拥有更多人口的 B 类城市, 这座 A 类城市中的人就会不高兴.
有 \(Q\) 次操作, 操作分 \(2\) 种:
UPDATE x y 把 \(x\) 城市的人口修改为 \(y\)
REVERSE l r 把城市 \(l\) 到 \(r\) 之间的所有道路都反向
每次操作后你需要输出共有多少人不高兴.
- Solution
- subtask 3
资瓷单点修改, 求一个区间内值在某个范围内的数的个数.
带修主席树 / 树套树即可.
subtask 4
来源: http://www.bubuko.com/infodetail-3217236.html