01Trie!!
查看原帖
01Trie!!
750943
Timmylyx楼主2024/1/26 18:21
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mid (l+r)/2
#define ls id*2
#define rs id*2+1
#define N 10000010
#define M 2e14
struct node{
	int tree[N][2],cnt[N],tot=1;
	void insert(int x){
		int now=1;
		for (int i=50; i>=0; i--){
			int c=(x>>i)&1;
			if (tree[now][c]==0){
				tree[now][c]=++tot;
			}now=tree[now][c]; cnt[now]++;
		}
	}int ask(int x){
		int now=1,ans=0;
		for (int i=50; i>=0; i--){
			int c=(x>>i)&1;
			if (c==0) ans+=cnt[tree[now][1]];
			now=tree[now][c];
		}return ans;
	}
}t;
int sum=0,ans=0;
signed main(){
	int n,k; cin>>n>>k;
	for (int i=1; i<=n; i++){
		t.insert(sum+M);
		int x; cin>>x; sum+=x;
		ans+=t.ask(sum-k+M); 
	}cout<<ans;
}
2024/1/26 18:21
加载中...