线段树（校赛）

线段树（校赛）"/>

线段树（校赛）

                                                             3∑+1?

                                                                  Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

玄黄最近发明了一个神奇的函数：

Xh(x)=3*( ∑(x的每一位) )+1 ，x为自然数。

现在你面前有n个自然数，玄黄现在要求你完成两种操作 。
1、帮玄黄求出这n个数中，区间 [l, r] 的和，并把答案告诉玄黄 。
2、帮玄黄把区间 [l, r] 中的每一个数 x 都变成 Xh(x)。

Input

第一行输入一个正整数n(0 第二行输入n个自然数，下标从 1 至 n，每个自然数大小不超过 100000000003。 
第三行输入一个正整数m(0 之后有m行，每行输入三个数op， l， r（ 0 < op <3， 1 <= l <=r <=n ），op 代表玄黄要求你的操作编号，op 为 1 时执行第一种操作，op 为 2 时执行第二种操作，l 和 r 代表区间范围 。

Output

当 op 为 1 时，输出区间 [l, r] 的和，每次输出占一行。

Sample Input

5 
1 3 5 7 9 
5 
1 1 5 
2 3 5 
1 3 4 
2 1 3 
1 2 5

Sample Output

25 
38 
82

 .php/Home/Contest/contestproblem/cid/2956/pid/4524

#include<stdio.h>
#include<iostream>
#define lson num<<1
#define rson num<<1|1
#define mid ((l+r)>>1)using namespace std;struct node
{long long data,flag;
} a[1200000];long long ans;void build(long long l,long long r,long long num)
{if(l == r){scanf("%lld",&a[num].data);if(a[num].data == 13)a[num].flag = 1;elsea[num].flag = 0;return;}build(l,mid,lson);build(mid+1,r,rson);a[num].data = a[lson].data + a[rson].data;a[num].flag= min(a[lson].flag,a[rson].flag);}void sum(long long x,long long y,long long l,long long r,long long num)
{if(l >= x&&r <= y){ans += a[num].data;return;}if(x <= mid)sum(x,y,l,mid,lson);if(y > mid)sum(x,y,mid+1,r,rson);}void xh(long long x,long long y,long long l,long long r,long long num)//这个函数的特点：所有数进行有限次的函数运算，都会变成13，xh(13) == 13,所以当某个节点所有的叶子节点都为13时，就可以返回了，用flag标记
{if(a[num].flag)return;if(l == r){long long sum = 0;while(a[num].data){sum += a[num].data % 10;a[num].data/=10;}a[num].data = sum*3+1;if(a[num].data == 13)a[num].flag = 1;return ;}if(x <= mid)xh(x,y,l,mid,lson);if(y > mid)xh(x,y,mid+1,r,rson);a[num].data = a[lson].data + a[rson].data;a[num].flag = min(a[lson].flag,a[rson].flag);
}int main()
{long long  m,n,l,r,ope;scanf("%lld",&n);build(1,n,1);scanf("%lld",&m);while(m --){scanf("%lld",&ope);scanf("%lld %lld",&l,&r);if(ope == 1){ans = 0;sum(l,r,1,n,1);printf("%lld\n",ans);}else{xh(l,r,1,n,1);}}return 0;
}