CDQ 求调
查看原帖
CDQ 求调
754856
_zexal_楼主2023/7/4 23:18

rt,样例过了,代码0分.

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int Maxn=2e5+5;
int n,k,a[Maxn],sum1[Maxn],sum2[Maxn],Tree[Maxn];
inline bool cmp(int x,int y){
	return x>y; 
}
inline int CDQ(int l,int r){
	if(l==r) return a[l]>0;
	int mid=l+r>>1;
	int ans=0;
	ans+=CDQ(l,mid)+CDQ(mid+1,r);
	for(int i=mid;i>=l;i--)
		sum1[i]=sum1[i+1]+a[i];
	for(int j=mid+1;j<=r;j++) 
		sum2[j]=sum2[j-1]+a[j];
	sort(sum1+l+1,sum1+mid+1);
	sort(sum2+mid+2,sum2+r+1,cmp);
	for(int i=mid+1;i>=l;i--) sum1[i]=0;
	for(int j=mid;j<=r;j++) sum2[j]=0;	  
	int head=1;
	for(int i=l;i<=mid;i++){
		while(sum1[i]+sum2[mid+head]>0&&head<=r-mid){
			head++;
		}
		ans+=head;
	}
	return ans;
}
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]-=k;
	}
	cout<<CDQ(1,n);
	return 0;
}
2023/7/4 23:18
加载中...