给您一个整数数组a1，a2，…，an。该数组不增加。
让我们考虑一条有n个商店的生产线。商店用从1到n的整数从左到右编号。在第i家商店中，一顿饭的费用等于ai。
您应该处理两种类型的q查询：
1 x y：对于每个车间1≤i≤x，设置ai = max（ai，y）。
2 x y：让我们考虑一个拥有y钱的饥饿的人。他参观了从第x家到第n家的商店，如果他能在当前的商店买一顿饭，他就购买其中一件。查找他将购买多少餐。如果他有至少ai钱，该人可以在商店i中买一顿饭，之后他的钱减少ai。
输入项
第一行包含两个整数n，q（1≤n，q≤2⋅105）。
第二行包含n个整数a1，a2，…，an（1≤ai≤109）-用餐费用。保证a1≥a2≥…≥an。
接下来的每行q包含三个整数t，x，y（1≤t≤2，1≤x≤n，1≤y≤109），每个整数描述下一个查询。
确保至少存在一个类型2查询。
输出量
对于类型2的每个查询，在新行上输出答案。
//对于第二种操作，在线段树上有技巧的递归，具体看代码 //对于第一种操作 //二分出第一个小于等于y的位置p //如果大于x continue //否则 up(p,x,y) #include<bits/stdc++.h> using namespace std; const int maxn=2e5+100; typedef long long ll; int n,q; int a[maxn]; struct node { int l,r; ll sum; ll lazy; ll Min; }segTree[maxn<<2]; void build (int i,int l,int r) { segTree[i].l=l; segTree[i].r=r; if (l==r) { segTree[i].sum=a[l]; segTree[i].Min=a[l]; return; } int mid=(l+r)>>1; build(i<<1,l,mid); build(i<<1|1,mid+1,r); segTree[i].sum=segTree[i<<1].sum+segTree[i<<1|1].sum; segTree[i].Min=min(segTree[i<<1].Min,segTree[i<<1|1].Min); } void spread (int i) { if (segTree[i].lazy) { segTree[i<<1].sum=segTree[i].lazy*(segTree[i<<1].r-segTree[i<<1].l+1); segTree[i<<1].Min=segTree[i].lazy; segTree[i<<1].lazy=segTree[i].lazy; segTree[i<<1|1].sum=segTree[i].lazy*(segTree[i<<1|1].r-segTree[i<<1|1].l+1); segTree[i<<1|1].Min=segTree[i].lazy; segTree[i<<1|1].lazy=segTree[i].lazy; segTree[i].lazy=0; } } void up (int i,int l,int r,ll v) { if (segTree[i].l>=l&&segTree[i].r<=r) { segTree[i].sum=v*(segTree[i].r-segTree[i].l+1); segTree[i].Min=v; segTree[i].lazy=v; return; } spread(i); int mid=(segTree[i].l+segTree[i].r)>>1; if (l<=mid) up(i<<1,l,r,v); if (r>mid) up(i<<1|1,l,r,v); segTree[i].sum=segTree[i<<1].sum+segTree[i<<1|1].sum; segTree[i].Min=min(segTree[i<<1].Min,segTree[i<<1|1].Min); } ll query (int i,int l,int r) { if (segTree[i].l>=l&&segTree[i].r<=r) { return segTree[i].sum; } spread(i); int mid=(segTree[i].l+segTree[i].r)>>1; ll ans=0; if (l<=mid) ans+=query(i<<1,l,r); if (r>mid) ans+=query(i<<1|1,l,r); return ans; } int q1 (int i,int l,int r,int &tt) { if (segTree[i].Min>tt) return 0; if (segTree[i].l>=l&&segTree[i].r<=r&&segTree[i].sum<=tt) { tt-=segTree[i].sum; return segTree[i].r-segTree[i].l+1; } spread(i); int mid=(segTree[i].l+segTree[i].r)>>1; int ans=0; if (l<=mid) ans+=q1(i<<1,l,r,tt); if (r>mid) ans+=q1(i<<1|1,l,r,tt); return ans; } int main () { scanf("%d%d",&n,&q); for (int i=1;i<=n;i++) scanf("%d",a+i); build(1,1,n); for (int i=1;i<=q;i++) { int t,x,y; scanf("%d%d%d",&t,&x,&y); if (t==1) { int l=1,r=n,p=n+1; while (l<=r) { int mid=(l+r)>>1; if (query(1,mid,mid)<=y) { p=mid; r=mid-1; } else { l=mid+1; } } if (p>x) continue; else up(1,p,x,y); } else { int ans=q1(1,x,n,y); printf("%d ",ans); } } }