首页 > 代码库 > bzoj2441 小W的问题
bzoj2441 小W的问题
bzoj2441
按照纵坐标排序,从小到大插入数列中,每个点i维护一个data[i]表示未插入序列中横坐标小于i的数的个数(用线段树)其实点i就是“W”中第一个极小点,那么f[j]就等于1到j-1中所有已插入的data之和(也用线段树),j点就是“W”的极大点,为什么呢?因为现在在未插入数列中的数都是大于j的纵坐标的。这样就能求出以j为右端点的“V”的个数。
用同样的办法求出以j为左端点的“V”的个数g[j]。ans=sum(f[j]*g[j]) j=1...n
bzoj2441 小W的问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。