CF1439C Greedy Shopping

题解

尝试做一下，感觉是每次取一段前缀和，这样就相当于让我们证明在 \(a_i\le 10^{12}\) 时，不可能构造出隔一个取一个的情况（\(n=10^5\)）。

a[i]:  1, 2, 3, 5, 6,11,12,23,24...

s[i]:  1, 1, 4, 4,10,10,22,22,46...

可以发现他是成指数级增长的，所以必定不能构造出这样的数据，呕吼，好像可以做了。

我们就动态维护一下区间和，每次在这个东西上二分，按照我们上面的策略就可以了吧。

好像还需要吉老师线段树，骚啊~

好像不需要吉老师线段树了，各种线段树上二分才能保证复杂度不超过两只 \(\log_2\) 。。。感觉对于二分和线段树的理解更上一层楼了。

#include<bits/stdc++.h>

using namespace std;

#define Lint long long

const int N=2e5+5;

int n,m;Lint a[N];

struct Seg_Tree

{

	struct Node{Lint data,tag,L,R;}tr[N<<2];

	void up(int u)

	{

		tr[u].data=tr[u<<1].data+tr[u<<1|1].data;

		tr[u].L=tr[u<<1|1].L,tr[u].R=tr[u<<1].R;

	}

	void update(int u,int l,int r,Lint z)

	{

		tr[u].data=(r-l+1)*z;

		tr[u].L=tr[u].R=tr[u].tag=z;

	}

	void down(int u,int l,int r)

	{

		if(!tr[u].tag) return ;

		int mid=(l+r)>>1;

		update(u<<1,l,mid,tr[u].tag);

		update(u<<1|1,mid+1,r,tr[u].tag);

		tr[u].tag=0;

	}

	void build(int u,int l,int r,Lint a[])

	{

		if(l==r) return (void)(tr[u].data=tr[u].L=tr[u].R=a[l]);

		int mid=(l+r)>>1;

		build(u<<1,l,mid,a);

		build(u<<1|1,mid+1,r,a);

		up(u);

	}

	void chg(int u,int l,int r,int x,int y,Lint z)

	{

		if(x>y) return ;

		if(x<=l&&r<=y) return update(u,l,r,z);

		down(u,l,r);

		int mid=(l+r)>>1;

		if(x<=mid) chg(u<<1,l,mid,x,y,z);

		if(y>mid) chg(u<<1|1,mid+1,r,x,y,z);

		up(u);

	}

	int find(int u,int l,int r,int x)

	{

		if(tr[u].L>x) return n+1;

		if(l==r) return l;

		down(u,l,r);

		int mid=(l+r)>>1;

		if(tr[u<<1].L<=x) return find(u<<1,l,mid,x);

		else return find(u<<1|1,mid+1,r,x);

	}

	Lint sum(int u,int l,int r,int x,int y)

	{

		if(x>y) return 0;

		if(x<=l&&r<=y) return tr[u].data;

		down(u,l,r);

		int mid=(l+r)>>1;Lint res=0;

		if(x<=mid) res+=sum(u<<1,l,mid,x,y);

		if(y>mid) res+=sum(u<<1|1,mid+1,r,x,y);

		return res;

	}

	int query(int u,int l,int r,Lint k)

	{

		if(l==r) return l;

		down(u,l,r);

		int mid=(l+r)>>1;Lint tmp=tr[u<<1].data;

		if(k<=tmp) return query(u<<1,l,mid,k);

		else return query(u<<1|1,mid+1,r,k-tmp);

	}

}t;

int main()

{

	cin>>n>>m;

	for(int i=1;i<=n;++i) scanf("%lld",&a[i]);

	t.build(1,1,n,a);

	while(m--)

	{

		int opt,x,y;

		scanf("%d%d%d",&opt,&x,&y);

		if(opt==1) t.chg(1,1,n,t.find(1,1,n,y),x,y);

		else

		{

			int cnt=0;

			while(x<=n)

			{

				int tmp=t.query(1,1,n,t.sum(1,1,n,1,x-1)+y);

				if(t.sum(1,1,n,x,tmp)>y) tmp--;

//				printf("%d %d %d\n",x,y,tmp);

				cnt+=tmp-x+1,y-=t.sum(1,1,n,x,tmp),x=t.find(1,1,n,y);

				if(x<=tmp) x=tmp+1;

			}

			printf("%d\n",cnt);

		}

	}

	return 0;

}

巴特西

CF1439C Greedy Shopping

题解

最新文章

热门文章