原始题目：(非作业)
http://acm.cs.nthu.edu.tw/problem.php?hash=9c16f6606460d1543759fc966b9bb797#
简单叙述一下题目：
给一串有n个数字的数列
以及q个[a,b]的区间
如果第i个区间之后有两个点数总和小于第i个区间的区间,则得到A+的人加1
我的作法
求区间总和：
(1)建立一个n*n的方阵来存
summap[1][2]: 从1 ~ 2的总和
summap[3][6]: 从3 ~ 6的总和
在读取序列时一起进行, 所以花了(n)* (n+1) / 2的时间来进行
(2)读到区间后线性加总
譬如读取到2 6的区间, 就把数列中从[1] ~ [5]的元素加总
最差状况每个区间都是[1, n]的话,需要进行n * q次
储存：
(1)list：
宣告一个struct 来纪录
sum(区间的和),
counter(判断其后是否有两个小于自己的sum的数量)
先把数列完整读入后,建立一个list来存以上的结构
每读入一组区间, 建立一个结构来存,
然后判断读入的这个结构对list中的元素的counter的贡献
(如果conuter == 2则ans++, 之后把该元素从list中erase)
(2)阵列：
建立两个大小为n的阵列,分别存sum, counter
每读取一个区间就扫一次sum阵列
如果sum[i] > sum_current_input则counter++
如果counter == 2时, ans加1次(不会重复加, 因为只有counter < 2时才会递增counter
结果：
summap目前会RE , 还在找问题, 可是summap效能分析起来比线性求和还要差...
所以考虑往别的方向找答案
线性求和的方式搭配list, array都是TLE...
还有哪里可以改进效能的吗？
求和的地方实在想不到其他优化的方法了...
有没有办法减少读取一个区间后, 判断对数列影响的时间呢？
或是有其他方法？