[FHC 2016 Qualification Round]The Price is Correct

首先可以發現以下性質:
如果Sum{[l,r]}<=P，那麼對於所有的l<=x<=r，Sum{[x,r]}也會<=P
如果Sum{[l,r]}>P，那麼對於所有的1<=x<=l(一個是數字一個是字母別搞混XD)，Sum{[x,r]}也會>P

因此我們可以考慮枚舉r，找出最小的l，那麼結尾為r的合法區間數量就是r-l+1了
可以考慮二分搜這個l，複雜度O(NlogN)
不過這裡提供單調對列O(N)的作法
仔細想想可以發現，最小的l在r慢慢增加時不會變小
因此可以用雙指標由左而右掃過去，右指標每增加1就把左指標往右移直到區間合法為止(有可能不需移動)
具體實作可以用queue<int>存前綴和
也不知道還有甚麼BUG，真正的結果要等比賽結束才會知道Orz

ps.最後四題全對耶真開心 :D

code:

#include<cstdio>
#include<cassert>
#include<queue>
#define scanf(x,...) assert(scanf(__VA_ARGS__)==x)
using namespace std;
int N,P;
int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    int testcase;scanf(1,"%d",&testcase);
    while(testcase--)
    {
        scanf(2,"%d%d",&N,&P);
        long long sum=0LL;
        queue<int>q;
        q.push(sum);
        long long ans=0LL;
        for(int i=0,v;i<N;i++)
        {
            scanf(1,"%d",&v);
            q.push(sum+=v);
            while(q.front()<sum-P)q.pop();
//            printf("sz=%d\n",(int)q.size());
            ans+=(long long)q.size()-1LL;
        }
        static int kase=1;
        printf("Case #%d: %lld\n",kase++,ans);
    }
    scanf(-1,"%d",&testcase);
    return 0;
}