原始題目：(非作業)
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...
還有哪裡可以改進效能的嗎？
求和的地方實在想不到其他優化的方法了...
有沒有辦法減少讀取一個區間後, 判斷對數列影響的時間呢？
或是有其他方法？