【BZOJ1901】Dynamic Rankings Vol.2

【为什么我每天光搞这些东西

去学了一下整体二分。。恩之后再学cdq分治吧

两者的思想好像都差不多。。

整体二分似乎最经典的用途就是求区间第k大,不过是离线的,强制在线就无力了(就得用主席树了)

大概是这样一个步骤:

  1. 将所有修改拆成两部分:a[i]-=a[i], a[i]+=b;
  2. 二分出一个答案m;
  3. 在所有询问中,若其区间中包括的数中小于等于m的个数比该询问中的k要大或者相等,说明该询问的答案在[l,m],丢到左边,否则说明在[m+1,r],丢到右边;
  4. 在所有修改中,若其修改对[l,m]造成了影响(即修改后会让[l,m]中在此范围内的数的个数变化)则丢到左边,否则一定会对[m+1,r]造成影响,丢到右边;
  5. 分别处理左边和右边。
  6. 当l==r时若[l,r]中包含了询问操作,则该询问操作的答案为l。

好像还是比较容易理解的。。【才怪

照着某神犇的代码蒯了一遍

说点什么

您将是第一位评论人!

提醒
wpDiscuz