UVa 12345. Dynamic len(set(a[L:R]))

Brief description:

… 给定一个数列,维护以下两种操作。

  • 询问某段区间内出现了多少种不同的数字。
  • 修改某个位置的值。

Analysis:

。略)

树状数组套主席树。。(1s + .. .
http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=2962041

树状数组套Splay。。(3s +- .. .
暴力的话姿势正确貌似也能过。。(3s +- ..

External link:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3767
http://user.qzone.qq.com/251815992/blog/1346399378