ai​ 颗苹果 。 接下来 m 行，每行共3个正整数op,l,r。

5 5 1 10 100 1000 10000 2 1 5 3 1 5 1 1 5 2 1 5 3 1 5

2 11111 3 7405

1e5范围

#include <iostream> #include <algorithm> using namespace std; const int N =
1e5 + 10; typedef long long ll; typedef pair<int,int> pii; int n,m; int a[N];
struct node{ int l,r; int max,num100; ll sum; }tr[N*4]; void pushup(int u){
tr[u].max= max(tr[u<<1].max,tr[u<<1|1].max);
tr[u].num100=tr[u<<1].num100+tr[u<<1|1].num100;
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum; } void build(int u,int l,int r){
tr[u]={l,r,0,0,0}; if(l==r){ tr[u].max=a[r]; tr[u].sum=a[r]; if(a[r]<100)
tr[u].num100=1; return; } int mid=(l+r)>>1; build(u<<1,l,mid);
build(u<<1|1,mid+1,r); pushup(u); } void modify(int u,int l,int r){
if(tr[u].max<10) return; if(tr[u].l==tr[u].r){ int p=tr[u].sum/3;
if(tr[u].sum%3) p++; tr[u].sum-=p; tr[u].max=(int)tr[u].sum;
if(tr[u].sum<100)tr[u].num100=1; return; } int mid=tr[u].r+tr[u].l>>1;
if(l<=mid) modify(u<<1,l,r); if (r>mid) modify(u<<1|1,l,r); pushup(u); } ll
querynum100(int u,int l,int r){ if(l<=tr[u].l&&r>=tr[u].r) return tr[u].num100;
ll res=0; int mid = tr[u].l + tr[u].r >> 1; if (l <= mid) res += querynum100(u
<< 1, l, r); if (r > mid) res += querynum100(u << 1 | 1, l, r); return res; }
ll querysum(int u,int l,int r){ if(l<=tr[u].l&&r>=tr[u].r) return tr[u].sum; ll
res=0; int mid = tr[u].l + tr[u].r >> 1; if (l <= mid) res += querysum(u << 1,
l, r); if (r > mid) res += querysum(u << 1 | 1, l, r); return res; } int main()
{ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,1,n);
while(m--){ int op,l,r; scanf("%d%d%d",&op,&l,&r); if(op==1) modify(1,l,r);
if(op==2) printf("%lld\n",querynum100(1,l,r)); if(op==3)
printf("%lld\n",querysum(1,l,r)); } return 0; }

GitHub

Gitee