题解 CF1042D Petya and Array

PanH · 2020-06-10 21:12:42 · 题解

emm...虽然已经有权值线段树做法了，但这种做法其实是不用离散化的，因为权值线段树可以动态开点。对于线段树的操作也只要 insert 和 query 就可以了。

或许我的代码会更简洁一点？（雾）。

• 由于存在负数，线段树处理不了，于是可以加上一个很大的数 (1e15) 。

具体操作看代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
template<class T>inline void read(T &x)
{
    x=0;int f=0;char ch=getchar();
    while(!isdigit(ch)) f=ch=='-',ch=getchar();
    while(isdigit(ch))  x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=f?-x:x;
}
const int MAXN=1e7+5,N=2e5+5,G=1e15;
int tree[MAXN],lson[MAXN],rson[MAXN],tot,n,t,a[N],rt,ans;
#define mid (l+r>>1)
inline void make(int &k){if(!k) k=++tot;}
void insert(int l,int r,int &k,int x)
{
    make(k);
    if(l==r)    return tree[k]++,void();
    if(x<=mid)  insert(l,mid,lson[k],x);
    else    insert(mid+1,r,rson[k],x);
    tree[k]=tree[lson[k]]+tree[rson[k]];
}
int query(int l,int r,int k,int x,int y)
{
    if(l>=x&&r<=y)  return tree[k];
    int res=0;
    if(x<=mid)  res+=query(l,mid,lson[k],x,y);
    if(y>mid)   res+=query(mid+1,r,rson[k],x,y);
    return res;
}
#undef mid
signed main()
{
    read(n),read(t);
    for(int i=1;i<=n;i++)   read(a[i]),a[i]+=a[i-1];
    for(int i=n;i;i--)  insert(1,G<<1,rt,a[i]+G),ans+=query(1,G<<1,rt,1,a[i-1]+t+G-1);//插入以i为右端点的前缀和，求出以i为左端点有多少区间。
    printf("%lld",ans);
    return 0;
}