牛客周赛 Round 28 F_牛客周赛 round 28 题解

F.小红统计区间（hard）

题目链接

为前缀和

• 枚举右端点看有多少个左端点满足条件，即在一个数轴上找的的个数。可以利用树状数组区间查询，查找中满足条件的前缀和。具体操作为先查找，再把自身在数轴上对应的数的个数加一。所以统计时没有统计自身对答案的影响。当前操作为第位时，则数轴上只记录了的前缀和。
• 由于前缀和过大，形成的数轴过长，采用离散化。将所有前缀和由小到大排序并去重，构成新数轴。
• 由于在数轴上可能没有直接映射，所以通过二分找到满足条件的最大的前缀和，转为统计小于等于它的前缀和个数。找不到就不更新
• 最大会到，会爆

 
 
import java.io.*;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;
 
 
 
public class Main{
	static 
	class BIT{
		int size;
		long[] tr;
		public BIT(int n) {
			size=n;
			tr=new long[n+1];
		}
		public int lowbit(int x) {
			return x&(-x);
		}
		public void update(int x) {
			for(int i=x;i<=size;i+=lowbit(i)) {
				tr[i]++;
			}
		}
		public long query(int x) {//区间组合最多1e10，int会爆
			long ans=0;
			for(int i=x;i>0;i-=lowbit(i)) {
				ans+=tr[i];
			}
			return ans;
		}
	}
	public static void main(String[] args) throws IOException{
		Scanner input=new Scanner(System.in);
		int n=input.nextInt();
		long k=input.nextLong();
		long ans=0;
		long[] Sum=new long[n];//用于离散化的前缀和
		long[] pre=new long[n];//保留原本的前缀和
		Sum[0]=input.nextLong();
        if(Sum[0]>=k)ans++;
		pre[0]=Sum[0];
		for(int i=1;i<n;++i) {
			Sum[i]=input.nextLong();
			Sum[i]+=Sum[i-1];
			if(Sum[i]>=k)ans++;
			pre[i]=Sum[i];
		}
		Arrays.sort(Sum);
		HashMap<Long,Integer> hs=new HashMap<Long, Integer>();
		int cnt=0;
		long[] Qu=new long[n+1];//离散后数轴每位对应的前缀和
		for(int i=0;i<n;++i) {
			if(hs.get(Sum[i])==null) {
				cnt++;
				hs.put(Sum[i], cnt);
				Qu[cnt]=Sum[i];
			}
		}
		//排序后位置不同，可能在后面的前缀和被移到前面或在前面的前缀和被移到后面
		
		BIT Tr=new BIT(cnt);
		Tr.update(hs.get(pre[0]));
		for(int i=1;i<n;++i) {
			long y=pre[i]-k;
			int l=1,r=cnt,id=-1;//二分查找
			while(l<=r) {
				int mid=(l+r)>>1;
				if(Qu[mid]<=y) { 
					id=mid;
					l=mid+1;
				}
				else r=mid-1;
			}
			if(id!=-1)ans+=Tr.query(hs.get(Qu[id]));
			Tr.update(hs.get(pre[i]));
		}
		System.out.println(ans);
	}
	
}