实在不知道哪里错了,一直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;
}
救救孩子吧