题目大意:
一个数列 支持两种操作
1 把区间内的数变成他们自己的约数个数
2 求区间和
思路:
可以想到每个数最终都会变成2或1
然后我们可以线段树
修改的时候记录一下每段有没有全被修改成1或2 是的话就不修改了
不是就暴力修改 因为每个数被修改的次数很小
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define inf 2139062143
#define ll long long
#define MAXN 1001000
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}
while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,g[MAXN],cnt[MAXN],m;
struct data{ll sum,mx;}tr[MAXN<<];
inline void pshp(int k)
{
tr[k].sum=tr[k<<].sum+tr[k<<|].sum;
tr[k].mx=max(tr[k<<].mx,tr[k<<|].mx);
}
void build(int k,int l,int r)
{
if(l==r) {tr[k].sum=tr[k].mx=g[l];return ;}
int mid=(l+r)>>;
build(k<<,l,mid);build(k<<|,mid+,r);
pshp(k);
}
inline ll query(int k,int a,int b,int l,int r)
{
if(l==a&&r==b) return tr[k].sum;
int mid=(l+r)>>;
if(mid>=b) return query(k<<,a,b,l,mid);
else if(mid<a) return query(k<<|,a,b,mid+,r);
else return query(k<<,a,mid,l,mid)+query(k<<|,mid+,b,mid+,r);
}
inline void upd(int k,int a,int b,int l,int r)
{
if(tr[k].mx<=) return ;
if(l==r) {tr[k].sum=tr[k].mx=cnt[tr[k].mx];return ;}
int mid=(l+r)>>;
if(mid>=b) upd(k<<,a,b,l,mid);
else if(mid<a) upd(k<<|,a,b,mid+,r);
else {upd(k<<,a,mid,l,mid);upd(k<<|,mid+,b,mid+,r);}
pshp(k);
}
int main()
{
int a,b,c;
for(int i=;i<=MAXN;i++)
for(int j=i;j<=MAXN;j+=i) cnt[j]++;
n=read(),m=read();
for(int i=;i<=n;i++) g[i]=read();
build(,,n);
while(m--)
{
a=read(),b=read(),c=read();
if(a==) upd(,b,c,,n);
else printf("%I64d\n",query(,b,c,,n));
}
}
UPD:
bzoj 3211 区间开根号 思路同上
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define inf 2139062143
#define ll long long
#define MAXN 100100
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}
while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,g[MAXN],m;
struct data{ll sum,mx;}tr[MAXN<<];
inline void pshp(int k)
{
tr[k].sum=tr[k<<].sum+tr[k<<|].sum;
tr[k].mx=max(tr[k<<].mx,tr[k<<|].mx);
}
void build(int k,int l,int r)
{
if(l==r) {tr[k].sum=tr[k].mx=g[l];return ;}
int mid=(l+r)>>;
build(k<<,l,mid);build(k<<|,mid+,r);
pshp(k);
}
inline ll query(int k,int a,int b,int l,int r)
{
if(l==a&&r==b) return tr[k].sum;
int mid=(l+r)>>;
if(mid>=b) return query(k<<,a,b,l,mid);
else if(mid<a) return query(k<<|,a,b,mid+,r);
else return query(k<<,a,mid,l,mid)+query(k<<|,mid+,b,mid+,r);
}
inline void upd(int k,int a,int b,int l,int r)
{
if(tr[k].mx<=) return ;
if(l==r) {tr[k].sum=tr[k].mx=sqrt(tr[k].sum);return ;}
int mid=(l+r)>>;
if(mid>=b) upd(k<<,a,b,l,mid);
else if(mid<a) upd(k<<|,a,b,mid+,r);
else {upd(k<<,a,mid,l,mid);upd(k<<|,mid+,b,mid+,r);}
pshp(k);
}
int main()
{
int a,b,c;
n=read();
for(int i=;i<=n;i++) g[i]=read();
m=read();
build(,,n);
while(m--)
{
a=read(),b=read(),c=read();
if(a==) upd(,b,c,,n);
else printf("%lld\n",query(,b,c,,n));
}
}