【Codejam2008

题目大意：

给出一个长度为n(n<=500000)数字串a，求这个串中严格递增的序列个数，序列长度可为1

分析：

什么鬼！上升序列？？相比做的前两场的C题，这次的C题在题目类型上就比较温和了，毕竟是很熟悉的DP模型。不难想到，设 dp[i] 为以i为末尾的严格上升序列的个数。 转移就很容易想到了，

dp[i]=∑j=1i−1dp[j](a[j]<a[i]) ，不炸完才怪咧 这种情况下，暂时不要放弃DP，考虑考虑优化是比较合理的。（当然，对于这道题似乎不用DP也有其他做法） 状态已经是一维，再压缩已不现实，考虑转移优化。 观察转移式，区间求和。。。赤裸裸地告诉你是线段树优化。 然而这个转移式还是有条件的，要求$a[j]&#xff0c;判定条件对数据结构是不友好的&#xff08;因为要你根据条件手动改写数据结构&#xff09;&#xff0c;但对于这种比较基础的判定条件&#xff0c;还是可以做的。 不难想到根据a的值排一次序&#xff0c;在线段树中按照排序后的顺序存储&#xff08;可能在a中多个位置对应线段树中同一个值&#xff09; 设a序列中每个位置对应的线段树中的位置为b[i] 线段树中每个区间存储一个区间和。每次转移就可以直接从1-b[i]-1求一个区间和就可以了&#xff0c;我们从前往后依次枚举&#xff0c;转移完就把当前位置的dp值更改到线段树中&#xff0c;这样做就不用担心把i之后的dp值选用了。 注&#xff1a;代码被学校的增霸卡刷掉了。。。正在补中。。。</p> <script></div><div align="center"><script src="https://www.6miu.com/js/artile.js">$