沧州专业网站建设公司,网站制作加我,深圳网站建设方维,国内重大新闻事件摘抄又到了万物复苏的季节#xff0c;家乡的苹果树结果了。像往常一样小龙同学被叫回家摘苹果。 假设需要采摘的一棵树上当前有a颗苹果#xff0c;那么小龙会采摘⌈a/3⌉颗苹果#xff0c;其中⌈x⌉表示不小于x的最小整数。 但是#xff0c;为了可持续发展#xff0c;若a小于1… 又到了万物复苏的季节家乡的苹果树结果了。像往常一样小龙同学被叫回家摘苹果。 假设需要采摘的一棵树上当前有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。 若op1表示小龙会采摘 [l,r] 区间内的苹果树。 若op2表示小龙想知道 [l,r]区间内的有多少棵苹果树上的苹果小于100颗。 若op3表示小龙想知道 [l,r] 区间内的共有多少颗苹果。 输出描述: 对于每个 op2或者op3的操作输出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 pairint,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[u1].max,tr[u1|1].max);tr[u].num100tr[u1].num100tr[u1|1].num100;tr[u].sumtr[u1].sumtr[u1|1].sum;
}
void build(int u,int l,int r){tr[u]{l,r,0,0,0};if(lr){tr[u].maxa[r];tr[u].suma[r];if(a[r]100) tr[u].num1001;return;}int mid(lr)1;build(u1,l,mid);build(u1|1,mid1,r);pushup(u);
}
void modify(int u,int l,int r){if(tr[u].max10) return;if(tr[u].ltr[u].r){int ptr[u].sum/3;if(tr[u].sum%3) p;tr[u].sum-p;tr[u].max(int)tr[u].sum;if(tr[u].sum100)tr[u].num1001;return;}int midtr[u].rtr[u].l1;if(lmid) modify(u1,l,r);if (rmid) modify(u1|1,l,r);pushup(u);
}
ll querynum100(int u,int l,int r){if(ltr[u].lrtr[u].r) return tr[u].num100;ll res0;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(ltr[u].lrtr[u].r) return tr[u].sum;ll res0;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 i1;in;i) scanf(%d,a[i]);build(1,1,n);while(m--){int op,l,r;scanf(%d%d%d,op,l,r);if(op1) modify(1,l,r);if(op2) printf(%lld\n,querynum100(1,l,r));if(op3) printf(%lld\n,querysum(1,l,r));}return 0;
}
