某島

… : "…アッカリ~ン . .. . " .. .
September 1, 2012

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