學習了一下動態開樹的技巧&&值域線段樹……

PRoblem Description 酷愛日料的小Z經常光顧學校東門外的回轉壽司店。在這里，一盤盤壽司 通過傳送帶依次呈現在小Z眼前。 不同的壽司帶給小Z的味覺感受是不一樣的，我們定義小Z對每盤壽司都 有一個滿意度，例如小Z酷愛三文魚，他對一盤三文魚壽司的滿意度為10; 小Z覺得金槍魚沒有什么味道，他對一盤金槍魚壽司的滿意度只有5;小Z最近 看了電影“美人魚”，被里面的八爪魚惡心到了，所以他對一盤八爪魚刺身的 滿意度是-100。 特別地，小Z是個著名的吃貨，他吃回轉壽司有一個習慣，我們稱之 為“狂吃不止”。具體地講，當他吃掉傳送帶上的一盤壽司后，他會毫不猶豫 地吃掉它后面的壽司，直到他不想再吃壽司了為止。 今天，小Z再次來到了這家回轉壽司店，N盤壽司將依次經過他的面前， 其中，小Z對第i盤壽司的滿意度為Ai。小Z可以選擇從哪盤壽司開始吃，也可 以選擇吃到哪盤壽司為止，他想知道共有多少種不同的選擇，使得他的滿意度 之和不低于L，且不高于R。注意，雖然這是回轉壽司，但是我們不認為這是 一個環上的問題，而是一條線上的問題。即，小Z能吃到的是輸入序列的一個 連續子序列;最后一盤轉走之后，第一盤并不會再出現一次。 Input 第一行包含三個整數N，L和R，分別表示壽司盤數，滿意度的下限和上 限。 第二行包含N個整數Ai，表示小Z對壽司的滿意度。 對20%的數據，1≤N≤2000. 另有30%的數據，Ai≥0. 對100%的數據，N≤100000，|Ai|≤100000，0≤L, R≤109. Output 僅一行，包含一個整數，表示共有多少種選擇可以使得小Z的滿意度之和 不低于L且不高于R。 Sample Input 【輸入樣例1】 5 5 9 1 2 3 4 5 【輸入樣例2】 4 2 4 2 -1 2 3 Sample Output 【輸出樣例1】 6 【輸出樣例2】 5 首先預處理出前綴和s[i],先在值域線段樹中插入值0，每次對于s[i],查詢值域屬于[s[i]-R,s[j]-L]的前綴個數，累加答案，在將當前前綴插入線段樹。注意longlong的使用，被算法庫的find坑了QAQ……以后起變量名最好起好一點……不然就會造成編譯錯誤調了大半天……