题干：
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.
京公网安备 11010502036488号