思路1：

线段树（982 ms）

每个点最多更新6次

代码：

#include
     
      using namespace std;#define ll long long#define pb push_back#define ls rt<<1,l,m#define rs rt<<1|1,m+1,r#define mem(a,b) memset(a,b,sizeof(a))const int N=1e6+5;const int INF=0x3f3f3f3f;int a[N];int d[N];ll tree[N<<2];int mx[N<<2];void init(){    for(int i=1;i
      
       >1;    build(ls);    build(rs);    push_up(rt);}void update(int L,int R,int rt,int l,int r){    if(mx[rt]<=2)return ;    if(l==r){        tree[rt]=mx[rt]=d[tree[rt]];        return ;    }    int m=(l+r)>>1;    if(L<=m)update(L,R,ls);    if(R>m)update(L,R,rs);    push_up(rt);}ll query(int L,int R,int rt,int l,int r){    if(L<=l&&r<=R)return tree[rt];    int m=(l+r)>>1;    ll ans=0;    if(L<=m)ans+=query(L,R,ls);    if(R>m)ans+=query(L,R,rs);    return ans;}int main(){    ios::sync_with_stdio(false);    cin.tie(0);    int n,m,t,l,r;    init();    cin>>n>>m;    for(int i=1;i<=n;i++)cin>>a[i];    build(1,1,n);    while(m--){        cin>>t>>l>>r;        if(t==1)update(l,r,1,1,n);        else cout<
       
        <
       
      
     

思路2：

分块（1326 ms）

每个块最多更新6次

代码：

#include
     
      using namespace std;#define ll long long #define pb push_back#define mem(a,b) memset(a,b,sizeof(a))const int N=1e6+5;int d[N];int a[N],belong[N],blo,flag[1000];ll sum[1000];void init(){    for(int i=1;i
      
       2)flag[x]=0;    } } void update(int l,int r){    if(belong[l]==belong[r]){        for(int i=l;i<=r;i++){            sum[belong[i]]-=a[i];            a[i]=d[a[i]];            sum[belong[i]]+=a[i];        }        return ;    }     for(int i=l;i<=belong[l]*blo;i++){        sum[belong[i]]-=a[i];        a[i]=d[a[i]];        sum[belong[i]]+=a[i];    }    for(int i=belong[l]+1;i<=belong[r]-1;i++)solve(i);    for(int i=(belong[r]-1)*blo+1;i<=r;i++){        sum[belong[i]]-=a[i];        a[i]=d[a[i]];        sum[belong[i]]+=a[i];    }}ll query(int l,int r){    ll ans=0;    if(belong[l]==belong[r]){        for(int i=l;i<=r;i++)ans+=a[i];        return ans;    }     for(int i=l;i<=belong[l]*blo;i++)ans+=a[i];    for(int i=belong[l]+1;i<=belong[r]-1;i++)ans+=sum[i];    for(int i=(belong[r]-1)*blo+1;i<=r;i++)ans+=a[i];    return ans;} int main(){    ios::sync_with_stdio(false);    cin.tie(0);    init();    int n,m,t,l,r;    cin>>n>>m;    blo=sqrt(n);    for(int i=1;i<=n;i++)cin>>a[i];    for(int i=1;i<=n;i++){        belong[i]=(i-1)/blo+1;        sum[belong[i]]+=a[i];    }    while(m--){        cin>>t>>l>>r;        if(t==1)update(l,r);        else cout<
       
        <