WA #5 求助
查看原帖
WA #5 求助
968531
Lunar_Whisper楼主2024/4/21 15:27

实在不知道哪里错了,一直WA #5

代码:

# include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e6+10;
int a[N],ans[N*4],tag[N*4],minx[N*4];
inline int ls(int x)
{
	return x << 1;
}
inline int rs(int x)
{
	return x << 1|1;
}
inline void push_up(int p)
{
	minx[p] = min(minx[ls(p)],minx[rs(p)]);
	ans[p] = ans[ls(p)]+ans[rs(p)];
}
inline void build(int p,int l,int r)
{
	if(l == r)
	{
		ans[p] = minx[p] = a[l];
		return ;
	}
	int mid = (l+r) >> 1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	push_up(p);
}
inline void f(int p,int l,int r,int k)
{
	ans[p] += (r-l+1)*k;
//	tag[p] += k;
	tag[p] = k;
	minx[p] = k;
}
inline void push_down(int p,int l,int r)
{
	if(!tag[p]) return ;
	int mid = (l+r) >> 1;
	f(ls(p),l,mid,tag[p]);
	f(rs(p),mid+1,r,tag[p]);
	tag[p] = 0;
}
inline int find(int p,int l,int r,int k)
{
	if(l == r)
	{
		if(k > ans[p])
		{
			return l;
		}
		else
		{
			return l+1;
		}
	}
	push_down(p,l,r);
	int mid = (l+r) >> 1;
	if(minx[ls(p)] >= k)
	{
		return find(rs(p),mid+1,r,k);
	}
	return find(ls(p),l,mid,k);
}
inline void update(int p,int nl,int nr,int l,int r,int k)
{
	if(l <= nl && nr <= r)
	{
		return f(p,nl,nr,k); 
	}
	push_down(p,nl,nr);
	int mid = (nl+nr) >> 1;
	if(l <= mid) update(ls(p),nl,mid,l,r,k);
	if(r > mid) update(rs(p),mid+1,nr,l,r,k);
	push_up(p);
}	
inline int query(int k,int l,int r,int x,int &v)
{
	if(r < x || minx[k] > v) return 0;
	if(l >= x&&v >= ans[k]) 
	{
		v -= ans[k];
		return r-l+1;	
	}
	push_down(k,l,r);
	int ret = 0;
	int mid = (l+r) >> 1;
	ret += query(ls(k),l,mid,x,v);
	ret += query(rs(k),mid+1,r,x,v);
	return ret; 
}
signed main (){
	int n,m;
	scanf("%lld%lld",&n,&m);
	for(int i = 1;i <= n;i++)
	{
		scanf("%lld",&a[i]);
	}
	build(1,1,n);
	while(m--)
	{
		int op;
		scanf("%lld",&op);
		if(op == 1)
		{
			int x,y;
			scanf("%lld%lld",&x,&y);
			int cnt = find(1,1,n,y);
			if(cnt <= x)update(1,1,n,cnt,x,y);
		}
		else
		{
			int x,y;
			scanf("%lld%lld",&x,&y);
			printf("%lld\n",query(1,1,n,x,y));
		}
	}
	return 0;
}

救救孩子吧

2024/4/21 15:27
加载中...