codefoces 1042D. Petya and Array(查询比当数大的个数) Splay或树状数组+离散化

题意：问你有多少对$\sum_{l}^{r} &lt; t$l∑r​<t
前缀和可以sum[r] - sum[l-1] < t,即sum[r] < sum[l-1] + t。枚举r，即到当前有多少个sum[l-1]+t大于sum[r]。
就变成了一个查询问题，因为这题不是强制在线的，所以可以利用树状数组+离散化解决。

代码如下：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAX = 200010;
int N;
ll t;
ll a[MAX],pos[MAX*4];
ll sum[MAX];
int cnt;
ll dat[MAX*4];
ll Sum(int i){
    ll res = 0;
    while(i > 0){
        res += dat[i];
        i -= (i&-i);
    }
    return res;
}
void add(int i){
    while(i <= cnt){
        dat[i] += 1;
        i += (i&-i);
    }
}
int gethash(ll x){
    int v = lower_bound(pos+1,pos+cnt+1,x)-pos;
    return v;
}
void Display(){
    printf("pos =================\n");
    for(int i=1;i<=cnt;++i){
        printf("%lld ",pos[i]);
    }
    printf("\n");
}
int main(void){
    scanf("%d%lld",&N,&t);
    for(int i=1;i<=N;++i){
        scanf("%lld",&a[i]);
        sum[i] = sum[i-1] + a[i];
        pos[++cnt] = sum[i];
        pos[++cnt] = sum[i] + t;
    }
    pos[++cnt] = t;
    sort(pos+1,pos+cnt+1);
    cnt = unique(pos+1,pos+cnt+1)-(pos+1);
   // Display();
    ll res = 0;
    add(gethash(t));
    for(int i=1;i<=N;++i){
        int v = gethash(sum[i]);
        int temp = (i-Sum(v));
        res += temp;
        add(gethash(sum[i]+t));
 //       printf("tmp = %d,res = %lld\n",temp,res);
    }
    printf("%lld\n",res);

    return 0;
}

还一种做法，就是直接利用Splay在线查询即可。
代码如下：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAX = 200010;
int ch[MAX*2][2],Size[MAX*2],f[MAX*2],cnt[MAX*2];
ll key[MAX*2];
int sz,root;
inline int get(int x){
    return ch[f[x]][1] == x;
}
inline void clean(int x){
    ch[x][0] = ch[x][1] = f[x] = cnt[x] = key[x] = Size[x] = 0;
}
inline void update(int x){
    if(x){
        Size[x] = cnt[x];
        if(ch[x][0])    Size[x] += Size[ch[x][0]];
        if(ch[x][1])    Size[x] += Size[ch[x][1]];
    }
}
inline void Rotate(int x){
    int y = f[x],z = f[y];
    int kind = get(x);
    ch[y][kind] = ch[x][!kind];
    f[ch[y][kind]] = y;
    f[y] = x;ch[x][!kind] = y;
    f[x] = z;
    if(z)   ch[z][ch[z][1] == y] = x;
    update(y);update(x);
}
void splay(int x){
    for(int fa;(fa = f[x]);Rotate(x)){
        if(f[fa])   Rotate((get(x) == get(fa))? fa:x);
    }
    root = x;
}
bool Insert(ll x){
    if(root == 0){
        sz++;
        Size[sz] = cnt[sz] = 1;
        ch[sz][0] = ch[sz][1] = f[sz] = 0;
        root = sz;key[sz] = x;
        return true;
    }
    int now = root,fa = 0;
    while(true){
        if(key[now] == x){
            cnt[now]++;
            update(fa);
            splay(now);
            return false;
        }
        fa = now;
        now = ch[now][x > key[now]];
        if(now == 0){
            sz++;
            Size[sz] = cnt[sz] = 1;
            ch[sz][0] = ch[sz][1] = 0;
            key[sz] = x;f[sz] = fa;
            ch[fa][x > key[fa]] = sz;
            splay(sz);
            return true;
        }

    }
}
int QueryNumRank(ll x){
    int ans = 0,now = root;
    while(true){
        if(x < key[now])
            now = ch[now][0];
        else{
            ans += ch[now][0]?Size[ch[now][0]]:0;
            if(key[now] == x){
                splay(now);
                return ans+1;
            }
            ans += cnt[now];
            now = ch[now][1];
        }
    }
}
int QueryPre(){
    int k = ch[root][0];
    while(ch[k][1]) k = ch[k][1];
    return k;
}
void del(ll x){
    QueryNumRank(x);//rotate x to root;
    if(cnt[root] > 1)   cnt[root]--;
    else if(!ch[root][0] && !ch[root][1]){
        clean(root);
        root = 0;
    }
    else if(!ch[root][0]){
        int tmp = root;
        root = ch[root][1];
        f[root] = 0;
        clean(tmp);
    }
    else if(!ch[root][1]){
        int tmp = root;
        root = ch[root][0];
        f[root] = 0;
        clean(tmp);
    }
    else{
        int t = QueryPre();
        int tmp = root;
        splay(t);
        ch[root][1] = ch[tmp][1];
        f[ch[tmp][1]] = root;
        clean(tmp);
        update(root);
    }
}
ll sum[MAX];
int main(void){
    int N;
    ll a,t;
    scanf("%d%lld",&N,&t);
    for(int i=1;i<=N;++i){
        scanf("%lld",&a);
        sum[i] = sum[i-1] + a;
    }
    ll res = 0;
    Insert(t);
    for(int i=1;i<=N;++i){
        Insert(sum[i]);
        res += Size[ch[root][1]];
        del(sum[i]);
        Insert(sum[i]+t);

    }
    printf("%lld\n",res);
    return 0;
}