题干：

https://buaacoding.cn/contest-ng/index.html#/334/problems

K wjj 的自动售货机

时间限制：1000ms   内存限制：131072kb

通过率：14/26 (53.85%)    正确率：14/119 (11.76%)

wjj 最近很看好线下实体销售的行业， 他觉得可以先投资自动售货机来试试水。

于是他在北航的新主楼中安装了一台可以售卖 nn 种物品的售货机， 第 ii 种物品共有 aiai 个。

为了方便用户，用户每次购买时， 可以选定某个区间 [l,r][l,r] 内的种类， 然后自动售货机根据选定的区间进行出货。

记 al,al+1,⋯,ar−1,aral,al+1,⋯,ar−1,ar 非零值中的最小值为 xx， 每种物品会以 xx 个为一组、尽可能多地出货； 即出货后，物品数量 ai←(aimodx),∀i∈[l,r]ai←(aimodx),∀i∈[l,r]。

wjj 最终按顺序记录了 qq 个这样的区间信息。 他希望你能帮他计算，每次出货前和出货后，选定区间内的剩余物品数量的总和； 即分别以每次出货前和出货后的 aiai，计算 ∑ri=lai∑i=lrai。

输入

第一行包含一个正整数 TT（1≤T≤101≤T≤10），表示有 TT 组测试数据。

接下来依次给出每组测试数据。对于每组测试数据：

第一行，包含两个整数 nn 和 qq，含义见题目描述。

第二行，nn 个空格分隔的整数，依次表示序列的每一项。0≤ai≤10130≤ai≤1013（1≤i≤n1≤i≤n）。

接下来 qq 行，每行表示一组询问，格式如下：

• L R

1≤L≤R≤n1≤L≤R≤n。

对于所有的测试数据，满足 ∑n,∑q≤2×105∑n,∑q≤2×105。

输出

对于每组数据，对于每个询问，输出空格分隔的两个整数表示答案。

输入样例

1 5 2 5 4 2 2 10 1 5 1 5

输出样例

23 1 1 0

题目大意：

   n个数，q次询问，每次询问给出一段区间，找到区间内非零的最小的数x，对该区间的每个数都更新为a[i]取模x，对于每次操作，输出更新前和更新后的区间和。

解题报告：

   由于取模运算可以使得改数字最少减小一半(证明很简单)，所以对于每个数字最多logn次就降为0，所以对于更新操作可以直接暴力。对于查询最小值，注意一下排除为0的情况就可以了。

AC代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; const ll INF = 9223372036854775807; int n,q; ll a[MAX]; struct TREE {int l,r;ll val;//区间和 ll minn; } tree[MAX<<2]; void pushup(int cur) {ll t1=tree[cur*2].minn;ll t2=tree[cur*2+1].minn;if(t1 == 0) tree[cur].minn = t2;else if(t2 == 0) tree[cur].minn = t1;else tree[cur].minn = min(t1,t2);tree[cur].val = tree[cur*2].val + tree[cur*2+1].val; } void build(int l,int r,int cur) {tree[cur].l = l,tree[cur].r = r;if(l == r) {tree[cur].minn = tree[cur].val = a[r];return;}int m = (l+r)>>1;build(l,m,cur*2);build(m+1,r,cur*2+1);pushup(cur); } ll qMin(int pl,int pr,int cur) {//查询区间最小值 if(pl <= tree[cur].l && pr >= tree[cur].r) {return tree[cur].minn;}ll tmp1 = INF,tmp2 = INF;if(pl <= tree[cur*2].r) tmp1 = qMin(pl,pr,cur*2);if(pr >= tree[cur*2+1].l) tmp2 = qMin(pl,pr,cur*2+1);if(tmp1 == 0) {if(tmp2 == INF) tmp2=0;return tmp2;}if(tmp2 == 0) {if(tmp1 == INF) tmp1=0;return tmp1;}return min(tmp1,tmp2); }ll qSum(int pl,int pr,int cur) {//查询区间和if(pl <= tree[cur].l && pr >= tree[cur].r) {return tree[cur].val;}ll tmp1 = 0,tmp2 = 0;if(pl <= tree[cur*2].r) tmp1 = qSum(pl,pr,cur*2);if(pr >= tree[cur*2+1].l) tmp2 = qSum(pl,pr,cur*2+1);return tmp1+tmp2; } void update(int pl,int pr,ll val,int cur) {if(tree[cur].minn == 0) return ;if(tree[cur].l == tree[cur].r) {tree[cur].val%=val;tree[cur].minn%=val;return;}if(pl <= tree[cur*2].r) update(pl,pr,val,cur*2);if(pr >= tree[cur*2+1].l) update(pl,pr,val,cur*2+1);pushup(cur); } int main() {int t;cin>>t;while(t--) {scanf("%d%d",&n,&q);for(int i = 1; i<=n; i++) {scanf("%lld",a+i);}build(1,n,1);while(q--) {int l,r;scanf("%d%d",&l,&r);ll tmp = qMin(l,r,1);ll ans1 = qSum(l,r,1);ll ans2;if(tmp == 0) ans2 = ans1;else {update(l,r,tmp,1);ans2 = qSum(l,r,1);}printf("%lld %lld\n",ans1,ans2);}}return 0 ; }

WA代码1：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; const ll INF = 9223372036854775807; int n,q; ll a[MAX]; struct TREE {int l,r;ll val;//区间和 ll minn; } tree[MAX<<2]; void pushup(int cur) {ll t1=tree[cur*2].minn;ll t2=tree[cur*2+1].minn;if(t1 == 0) tree[cur].minn = t2;else if(t2 == 0) tree[cur].minn = t1;else tree[cur].minn = min(t1,t2);tree[cur].val = tree[cur*2].val + tree[cur*2+1].val; } void build(int l,int r,int cur) {tree[cur].l = l,tree[cur].r = r;if(l == r) {tree[cur].minn = tree[cur].val = a[r];return;}int m = (l+r)>>1;build(l,m,cur*2);build(m+1,r,cur*2+1);pushup(cur); } ll qMin(int pl,int pr,int cur) {//查询区间最小值 if(pl <= tree[cur].l && pr >= tree[cur].r) {return tree[cur].minn;}ll tmp1 = INF,tmp2 = INF;if(pl <= tree[cur*2].r) tmp1 = qMin(pl,pr,cur*2);if(pr >= tree[cur*2+1].l) tmp2 = qMin(pl,pr,cur*2+1);return min(tmp1,tmp2); }ll qSum(int pl,int pr,int cur) {//查询区间和if(pl <= tree[cur].l && pr >= tree[cur].r) {return tree[cur].val;}ll tmp1 = 0,tmp2 = 0;if(pl <= tree[cur*2].r) tmp1 = qMin(pl,pr,cur*2);if(pr >= tree[cur*2+1].l) tmp2 = qMin(pl,pr,cur*2+1);return tmp1+tmp2; } void update(int pl,int pr,ll val,int cur) {if(tree[cur].minn == 0) return ;if(tree[cur].l == tree[cur].r) {tree[cur].val%=val;tree[cur].minn%=val;return;}if(pl <= tree[cur*2].r) update(pl,pr,val,cur*2);if(pr >= tree[cur*2+1].l) update(pl,pr,val,cur*2+1);pushup(cur); } int main() {int t;cin>>t;while(t--) {scanf("%d%d",&n,&q);for(int i = 1; i<=n; i++) {scanf("%lld",a+i);}build(1,n,1);while(q--) {int l,r;scanf("%d%d",&l,&r);ll tmp = qMin(l,r,1);ll ans1 = qSum(l,r,1);ll ans2;if(tmp == 0) ans2 = ans1;else {update(l,r,tmp,1);ans2 = qSum(l,r,1);} printf("%lld %lld\n",ans1,ans2);}}return 0 ; }

WA代码2：：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; const ll INF = 9223372036854775807; int n,q; ll a[MAX]; struct TREE {int l,r;ll val;//区间和 ll minn; } tree[MAX<<2]; void pushup(int cur) {ll t1=tree[cur*2].minn;ll t2=tree[cur*2+1].minn;if(t1 == 0) tree[cur].minn = t2;else if(t2 == 0) tree[cur].minn = t1;else tree[cur].minn = min(t1,t2);tree[cur].val = tree[cur*2].val + tree[cur*2+1].val; } void build(int l,int r,int cur) {tree[cur].l = l,tree[cur].r = r;if(l == r) {tree[cur].minn = tree[cur].val = a[r];return;}int m = (l+r)>>1;build(l,m,cur*2);build(m+1,r,cur*2+1);pushup(cur); } ll qMin(int pl,int pr,int cur) {//查询区间最小值 if(pl <= tree[cur].l && pr >= tree[cur].r) {return tree[cur].minn;}ll tmp1 = INF,tmp2 = INF;if(pl <= tree[cur*2].r) tmp1 = qMin(pl,pr,cur*2);if(pr >= tree[cur*2+1].l) tmp2 = qMin(pl,pr,cur*2+1);if(tmp1 == 0) return tmp2;if(tmp2 == 0) return tmp1;return min(tmp1,tmp2); }ll qSum(int pl,int pr,int cur) {//查询区间和if(pl <= tree[cur].l && pr >= tree[cur].r) {return tree[cur].val;}ll tmp1 = 0,tmp2 = 0;if(pl <= tree[cur*2].r) tmp1 = qMin(pl,pr,cur*2);if(pr >= tree[cur*2+1].l) tmp2 = qMin(pl,pr,cur*2+1);return tmp1+tmp2; } void update(int pl,int pr,ll val,int cur) {if(tree[cur].minn == 0) return ;if(tree[cur].l == tree[cur].r) {tree[cur].val%=val;tree[cur].minn%=val;return;}if(pl <= tree[cur*2].r) update(pl,pr,val,cur*2);if(pr >= tree[cur*2+1].l) update(pl,pr,val,cur*2+1);pushup(cur); } int main() {int t;cin>>t;while(t--) {scanf("%d%d",&n,&q);for(int i = 1; i<=n; i++) {scanf("%lld",a+i);}build(1,n,1);while(q--) {int l,r;scanf("%d%d",&l,&r);ll tmp = qMin(l,r,1);ll ans1 = qSum(l,r,1);ll ans2;if(tmp == 0) ans2 = ans1;else {update(l,r,tmp,1);ans2 = qSum(l,r,1);} printf("%lld %lld\n",ans1,ans2);}}return 0 ; }

总结：

WA了好几发，，

首先RE因为没有开四倍。

1WA首先是没有所有的变量都开longlong，后来一个一个变量检查的。

2WA是INF设置的不够大，因为单个数据是1e13,而总共2e5个数，所以最大可能值是2e18，所以保险起见就设置INF为9e18好了。

3WA在求最小值的时候不太对，（也就是WA代码1那样写的）这样会导致只要有一个儿子节点的minn是0，就直接返回0了。

4WA在求最小值的时候不太对，因为这样有可能返回INF，比如左子树的minn是0，右子树的minn是2，那么应该返回 2，但是这样的话就返回INF了。。。

5WA在qSum的时候，，，里面递归竟然写成了qMin。。。我再也不复制粘贴了55555.

总结

以上是生活随笔为你收集整理的【北航oj】（线段树取模运算）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。