hdu 6609 区间条件前缀和 + 二分

题目传送门//res tp hdu

目的

在尾部逐步插入n个元素，求插入第i个元素时,[1,i)内删去多少个元素，可使前缀和[1,i]不大于m

多测Q [1,15]

n [1,2e5]

m [1,1e9]

每个元素W [1,m] (i∈[1,n]);

数据结构

树状数组

分析

维护两个树状数组，分别储存前缀和前缀中元素数量。先将元素全部读入，之后进行排列，同时记录好每个元素排列之后的下标。按下标向树状数组插入元素。之后二分枚举即可

时间复杂度O(Qnlognlogn)

#include<iostream>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long ll;

const int L = 200010;

ll val[L],sor[L];

struct E{

	ll v;

	int pos;

}sorted[L];

int Q,POS[L];

ll n,m;

ll BIT[L],bit[L];

int Len;

int lowbit(int x){return x&-x;}

bool cmp(E a,E b){return a.v<b.v;}

void change(int x,int y){

	sor[x] = y;

    for(int i = x;i<=L;i+=lowbit(i)){

    	BIT[i] += y;bit[i]++;

	}

}

ll query(int k){//对前缀和的询问

    ll ans = 0;

    for(int i = k;i > 0; i -= lowbit(i))

        ans += BIT[i];

    return ans;

}

int query1(int k){//对前缀内元素个数的询问

	int ans = 0;

	for(int i = k;i>0;i-=lowbit(i))

		ans += bit[i];

	return ans;

}

int getans(int x,int M){ //前x个元素的小序前缀之和不超过M

	int lo = 1,hi = n+1;

	int mi;

	ll sum;

	while(lo < hi){

		mi = (lo + hi)>>1;

		sum = query(mi);

		if(M <sum)	hi = mi;

		else lo = mi + 1;

	}

	--lo;

	return x-query1(lo);

}

int main(){

	scanf(" %d",&Q);

	while(Q--){

		scanf(" %lld %lld",&n,&m);

		for(int i = 1;i<=n;++i)	BIT[i] = bit[i] = 0;

		for(int i = 1;i<=n;++i) sor[i] = 0;

		for(int i = 1;i<=n;++i) {

			scanf(" %lld",&val[i]);

			sorted[i].v = val[i];

			sorted[i].pos = i;

		}

		sort(sorted+1,sorted+1+n,cmp);

		for(int i = 1;i<=n;++i)	POS[sorted[i].pos] = i;

		int ans;

		for(int i = 1;i<=n;++i){

			ans = getans(i-1,m-val[i]);

			change(POS[i],val[i]);

			printf("%d ",ans);

		}

		printf("\n");

	}

}