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

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

阅读量：4671 次

发布时间：2019-06-09

本文共 2355 字，大约阅读时间需要 7 分钟。

题目大意：

一个数列支持两种操作

1 把区间内的数变成他们自己的约数个数

2 求区间和

思路：

可以想到每个数最终都会变成2或1

然后我们可以线段树

修改的时候记录一下每段有没有全被修改成1或2 是的话就不修改了

不是就暴力修改因为每个数被修改的次数很小

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #define inf 213906214310 #define ll long long11 #define MAXN 100100012 using namespace std;13 inline int read()14 {15 int x=0,f=1;char ch=getchar();16 while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}17 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}18 return x*f;19 }20 int n,g[MAXN],cnt[MAXN],m;21 struct data{ll sum,mx;}tr[MAXN<<2];22 inline void pshp(int k)23 {24 tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum;25 tr[k].mx=max(tr[k<<1].mx,tr[k<<1|1].mx);26 }27 void build(int k,int l,int r)28 {29 if(l==r) {tr[k].sum=tr[k].mx=g[l];return ;}30 int mid=(l+r)>>1;31 build(k<<1,l,mid);build(k<<1|1,mid+1,r);32 pshp(k);33 }34 inline ll query(int k,int a,int b,int l,int r)35 {36 if(l==a&&r==b) return tr[k].sum;37 int mid=(l+r)>>1;38 if(mid>=b) return query(k<<1,a,b,l,mid);39 else if(mid
              
               >1;47 if(mid>=b) upd(k<<1,a,b,l,mid);48 else if(mid

View Code

UPD：

bzoj 3211 区间开根号思路同上

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #define inf 213906214310 #define ll long long11 #define MAXN 10010012 using namespace std;13 inline int read()14 {15 int x=0,f=1;char ch=getchar();16 while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}17 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}18 return x*f;19 }20 int n,g[MAXN],m;21 struct data{ll sum,mx;}tr[MAXN<<2];22 inline void pshp(int k)23 {24 tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum;25 tr[k].mx=max(tr[k<<1].mx,tr[k<<1|1].mx);26 }27 void build(int k,int l,int r)28 {29 if(l==r) {tr[k].sum=tr[k].mx=g[l];return ;}30 int mid=(l+r)>>1;31 build(k<<1,l,mid);build(k<<1|1,mid+1,r);32 pshp(k);33 }34 inline ll query(int k,int a,int b,int l,int r)35 {36 if(l==a&&r==b) return tr[k].sum;37 int mid=(l+r)>>1;38 if(mid>=b) return query(k<<1,a,b,l,mid);39 else if(mid
              
               >1;47 if(mid>=b) upd(k<<1,a,b,l,mid);48 else if(mid