值域线段树及离散化模板

例


就是说给一个序列a，将其中几个元素删去使其严格递增，求删去的数的总和的最小值
首先想着DP
\(f[i]\)表示将\([1,i]\)中几个元素删去使其严格递增,未删去的数的总和的最大值
易知\(f[i]=a[i]+max(f[j])\)其中\(j\)满足\(j<i,a[j]<a[i]\)
复杂度\(O(n^2)\)
像这种每次在不同限定下取某些元素中的最值/和···
用值域线段树
step1:将数组\(a[i]\)离散化成\(b[i]\)
离散化精简代码:

先鸽着

step2:开线段树
大小:数组不同元素的个数
step3:在dp遍历数组时更新值域线段树:
新加入一个\(f[i]\)，与线段树\(b[i]\)的位置取MAX存入线段树\(b[i]\)的位置
step4:计算\(f[i]\)时，\(max(f[j])\)可直接替换为\(O(logn)\)的\(query(1,b[i]-1)\)
总体\(O(nlogn)\)
ACcode
先鸽着

值域线段树及离散化模板

原文：https://www.cnblogs.com/zhangshaojia/p/14999296.html