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

原文地址:https://www.cnblogs.com/bytebull/p/5928057.html