C++14(g++5.4) 解法, 执行用时: 139ms, 内存消耗: 7708K, 提交时间: 2019-06-08 16:02:54

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll A[N];
ll F(ll x){
    ll ans=0;
    while(x)ans+=x%10,x/=10;
    return ans;
}
struct SegmentTree{
    int l,r,flag;ll sum;
    #define l(x) Tree[x].l
    #define r(x) Tree[x].r
    #define sum(x) Tree[x].sum
    #define flag(x) Tree[x].flag
}Tree[N*4];
void build(int p,int l,int r){
    l(p)=l;r(p)=r;
    if(l==r){sum(p)=A[l];return;}
    int mid=(l(p)+r(p))/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    sum(p)=sum(p*2)+sum(p*2+1);
}
void change(int p,int l,int r){
    if(flag(p))return;
    if(l(p)==r(p)){
        sum(p)=F(sum(p));
        if(sum(p)<10)flag(p)=1;
        return;
    }
    int mid=(l(p)+r(p))/2;
    if(l<=mid)change(p*2,l,r);
    if(r>mid)change(p*2+1,l,r);
    sum(p)=sum(p*2)+sum(p*2+1);
    flag(p)=(flag(p*2)&&flag(p*2+1));
}
ll ask(int p,int l,int r){
    if(l<=l(p)&&r>=r(p))return sum(p);
    int mid=(l(p)+r(p))/2;ll val=0;
    if(l<=mid)val+=ask(p*2,l,r);
    if(r>mid)val+=ask(p*2+1,l,r);
    return val;
}
int main(){
    int n,m,x,l,r;cin>>n>>m;
    for(int i=1;i<=n;++i)scanf("%lld",&A[i]);
    while(m--){scanf("%d%d",&x,&x);};
    build(1,1,n);
    int Q;cin>>Q;while(Q--){
        scanf("%d%d%d",&x,&l,&r);
        if(x==1)change(1,l,r);
        else printf("%lld\n",ask(1,l,r));
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 234ms, 内存消耗: 12704K, 提交时间: 2019-06-09 12:50:30

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,m,a,u,v,q;
struct node
{
	int l,r,data,flag;
}t[N<<2];
int f(int x)
{
	int res=0;
	while(x)	res+=x%10,x/=10;
	return res;
}
void push_up(int p)
{
	t[p].data=t[p<<1].data+t[p<<1|1].data;
	t[p].flag=t[p<<1].flag+t[p<<1|1].flag;
}
void build(int p,int l,int r)
{
	t[p].l=l,t[p].r=r,t[p].flag=0;
	if(l==r)
	{
		cin>>t[p].data;return ;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	push_up(p);
}
void change(int p,int l,int r)
{
	if(t[p].r-t[p].l+1==t[p].flag)	return ;
	if(t[p].l==t[p].r)
	{
		t[p].data=f(t[p].data);
		if(t[p].data<10)	t[p].flag=1;
		return ;
	}
	int mid=t[p].l+t[p].r>>1;
	if(r<=mid)	change(p<<1,l,r);
	else if(l>mid)	change(p<<1|1,l,r);
	else	change(p<<1,l,mid),change(p<<1|1,mid+1,r);
	push_up(p);
}
int ask(int p,int l,int r)
{
	if(t[p].l==l&&t[p].r==r)	return t[p].data;
	int mid=t[p].l+t[p].r>>1;
	if(r<=mid)	return ask(p<<1,l,r);
	else if(l>mid)	return ask(p<<1|1,l,r);
	else	return ask(p<<1,l,mid)+ask(p<<1|1,mid+1,r);
}
signed main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m;
	build(1,1,n);
	for(int i=1;i<=m;i++)	cin>>u>>v;
	cin>>q;
	while(q--)
	{
		int op;
		cin>>op>>u>>v;
		if(op)	change(1,u,v);
		else	cout<<ask(1,u,v)<<endl;
	}
	return 0;
}