- 技术
- 华华开始学信息学（树状数组+分块）
思路：吧数组分成sqrt（n）块 当给出更新的长度大于sqrt（n）时我们去树状数组暴力更新每个点，小于时，我们让lazy[x]+=y表示下标x的倍数的位置每个都+=y，询问时先算树状数组的区间，然后再看lazy是否有过标记，ans+=（10/2-3/2）*lazy【2】意思是【3——10】这个区间2的倍数的个数所给出的贡献。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include<iostream>
#include<vector>
#include<bits/stdc++.h>
using namespace std
;
typedef long long ll
;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair
<int,int> PII
;
const int mod
=1e4+7;
const int N
=2e5+10;
const int inf
=0x7f7f7f7f;
ll
gcd(ll a
,ll b
)
{
return b
==0?a
:gcd(b
,a
%b
);
}
ll
lcm(ll a
,ll b
)
{
return a
*(b
/gcd(a
,b
));
}
template <class T>
void read(T
&x
)
{
char c
;
bool op
= 0;
while(c
= getchar(), c
< '0' || c
> '9')
if(c
== '-')
op
= 1;
x
= c
- '0';
while(c
= getchar(), c
>= '0' && c
<= '9')
x
= x
* 10 + c
- '0';
if(op
)
x
= -x
;
}
template <class T>
void write(T x
)
{
if(x
< 0)
x
= -x
, putchar('-');
if(x
>= 10)
write(x
/ 10);
putchar('0' + x
% 10);
}
int block
;
ll a
[N
],lazy
[N
];
int n
,m
;
int lowbit(int x
)
{
return x
&-x
;
}
void update(int x
,int k
)
{
while(x
<=n
)
{
a
[x
]+=k
;
x
+=lowbit(x
);
}
}
ll
query(int x
)
{
ll ans
=0;
while(x
>0)
{
ans
+=a
[x
];
x
-=lowbit(x
);
}
return ans
;
}
int main()
{
SIS
;
cin
>>n
>>m
;
block
=sqrt(n
);
while(m
--)
{
int op
,x
,y
;
cin
>>op
>>x
>>y
;
if(op
==1)
{
if(x
<=block
){
lazy
[x
]+=y
;
}else{
for(int i
=x
;i
<=n
;i
+=x
)
update(i
,y
);
}
}
else
{
ll ans
=query(y
)-query(x
-1);
for(int i
=1;i
<=block
;i
++)
ans
+=(y
/i
-(x
-1)/i
)*lazy
[i
];
cout
<<ans
<<endl
;
}
}
return 0;
}
Processed:
0.009, SQL:
9
