re求调
查看原帖
re求调
550775
rsy_楼主2023/11/7 22:24
#include <bits/stdc++.h>
#define rep(i,j,k) for(register int i=(j);i<=(k);i=-~i)
#define per(i,j,k) for(register int i=(j);i>=(k);--i)
#define int long long

using namespace std;

namespace rsy{
	const int N = 2e5 + 10, mod = 998244353, hh = 1e15;
	typedef pair<int,int> pii;
	typedef long long ll;
	typedef unsigned long long ull;
	
	int n,k;
	struct segtree{
		int sum[N<<2],lson[N<<2],root,rson[N<<2],tot;
		void pushup(int u){
			sum[u]=sum[lson[u]]+sum[rson[u]];
		}
		void modify(int &u,int id,int w,int L=-1e18,int R=1e18){
			if(!u)u=++tot;
			if(L==R){sum[u]+=w;return;}
			int mid=L+(R-L)/2;
			if(id<=mid)modify(lson[u],id,w,L,mid);
			if(id>mid)modify(rson[u],id,w,mid+1,R);
			pushup(u);
		}
		int query(int u,int ql,int qr,int l=-1e18,int r=1e18){
			if(!u)return 0;
			if(ql<=l&&qr>=r)return sum[u];
			int res=0,mid=l+(r-l)/2;
			if(ql<=mid)res=query(lson[u],ql,qr,l,mid);
			if(qr>mid)res+=query(rson[u],ql,qr,mid+1,r);
			return res;
		}
	}tr;
	int a[N],res;
	
	void solve()
	{
		cin>>n>>k;
		for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1];
		for(int i=n;i>=1;i--)
			tr.modify(tr.root,a[i]+hh,1),res+=tr.query(tr.root,1,a[i-1]+k+hh-1);
		cout<<res<<'\n';
	}

	signed main()
	{
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		int T = 1;
		while (T -- ) solve();
		return 0;
	}
}

signed main()
{

    return rsy::main();
}
2023/11/7 22:24
加载中...