[CCF] 201709-5 除法
树状数组水题…(不过要剪枝)
题面：
我的代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+100;
long long a[maxn];
int b[maxn],n;
inline int lowbit(int x)
{
return x&(-x);
}
void update(int x,int add)
{
while(x<=n) a[x]+=add,x+=lowbit(x);
}
long long getSum(int x)
{
long long ans = 0;
while(x>0) ans+=a[x],x-=lowbit(x);
return ans;
}
long long query(int left,int right)
{
return getSum(right) - getSum(left-1);
}
int main()
{
int m,op,left,right,v;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%d",b+i);
update(i,b[i]);
}
while(m--)
{
scanf("%d%d%d",&op,&left,&right);
if(op==2)
printf("%lld\n",query(left,right));
else
{
scanf("%d",&v);
if(v==1) continue; //除以1就没必要更新了
for(int i=left;i<=right;++i)
{
if(b[i]>=v&&b[i]%v==0) //这里也剪枝
{
update(i,b[i]/v-b[i]);
b[i]/=v;
}
}
}
}
return 0;
}
我的代码
#incl
