UVa 12697 - Minimal Subarray Length

我，真是個笨蛋

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<utility>
#include<map>
#include<cmath>
#define INF 10000000
using namespace std;
typedef long long int int64;
int64 arr[500050];
int tree[2100000];
int base;
void init(int n){
    base = (1<<((int)(ceil(log2(n+3))))) - 1;
    for(int lx = 1;lx <= 2*base+1;lx++)
        tree[lx] = -1;
    return;
}
void modify(int pos, int val){
    pos += base+1;
    tree[pos] = val;
    for(pos>>=1;pos;pos>>=1)
        tree[pos] = max(tree[pos+pos], tree[pos+pos+1]);
    return;
}
int query(int a, int b){
    a++, b++;
    int ret = -1;
    for(a += base-1, b+= base+1; a^b^1;a>>=1, b>>=1){
        //printf("%d %d\n",a,b);
        if(~a&1) ret = max(ret, tree[a^1]);
        if(b&1) ret = max(ret, tree[b^1]);
    }
    return ret;
}
int main()
{
    int T;scanf("%d", &T);
    while(T--){
        int n; int64 k; scanf("%d %lld", &n, &k);
        map<int64, int> mm;
        arr[0] =  0;
        mm[0] = 0, mm[k] = 0;
        for(int lx = 0;lx < n;lx++){
            int64 inp; scanf("%lld", &inp);
            arr[lx+1] = arr[lx]+inp;
            mm[arr[lx+1]] = 0;
            mm[arr[lx+1]+k] = 0;
        }
        int cc = 0;
        init(mm.size()+1);
        for(map<int64, int>::iterator it = mm.begin(); it != mm.end(); it++)
            it->second = cc++;
        int len = INF;
        for(int lx = 0;lx <= n;lx++){
            int ans = query(0, mm[arr[lx]]);
            //printf("q at %d\n", mm[arr[lx]]);
            if(ans != -1)
                len = min(len, lx-ans);
            //printf("mod at %d\n", mm[arr[lx]+k]);
            modify(mm[arr[lx]+k],lx);
        }
        printf("%d\n", (len == INF) ? -1:len);
    }
    return 0;
}