©2020-2024 ioDraw All rights reserved,
Privacy Policy
又到了万物复苏的季节，家乡的苹果树结果了。像往常一样小龙同学被叫回家摘苹果。
假设需要采摘的一棵树上当前有a颗苹果，那么小龙会采摘⌈a/3⌉颗苹果，其中⌈x⌉表示不小于x的最小整数。
但是，为了可持续发展，若a小于10，那么小龙不会采摘这棵树的任何一颗苹果。
此外，小龙时不时会有一些疑问，想知道一些树上当前总共有多少颗苹果。
又或者想知道一些树中有多少棵苹果树上的苹果小于100颗。
那么就请你来帮助小龙同学吧。
输入描述:
第1行2个正整数 n和 m。表示小龙同学家有n棵苹果树，m次采摘（或疑问）。 第2行 n 个整数，第 i 个整数 ai 表示第 i棵苹果树上原本结有
ai 颗苹果 。 接下来 m 行，每行共3个正整数op,l,r。
若op=1，表示小龙会采摘 [l,r] 区间内的苹果树。
若op=2，表示小龙想知道 [l,r]区间内的有多少棵苹果树上的苹果小于100颗。
若op=3，表示小龙想知道 [l,r] 区间内的共有多少颗苹果。
输出描述:
对于每个 op=2或者op=3的操作，输出1行1个整数表示答案。
示例1
输入
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; }