Codeforces 920F. SUM and REPLACE / bzoj 3211 花神游历各国

题目大意：

一个数列支持两种操作

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));

     }

 }

巴特西

Codeforces 920F. SUM and REPLACE / bzoj 3211 花神游历各国

最新文章

热门文章