zcmimi's blog

arrow_back差分约束共1篇文章

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

x>y,看成x\rightarrow y的一条边

若最后的图出现环的话那就是不合法的

但是如果按照普通的建图方式的话每次要添加k(r-l-1-k)条边

我们可以线段树优化建图

因为k \le 3 \times 10^5

所以整个区间最多被划分成3\times 10^5

log n的复杂度是可以接受的

1/1
Search
search