1871: 演唱会

【题目描述】

小林最近迷上了参加演唱会，作为粉丝头子，小林要负责管理整个粉丝团队的应援活动。粉丝团队一共有n名粉丝在演唱会现场坐成一排，第i名粉丝的应援力度为ai。但是并不是每名粉丝的应援都很显眼，只有被聚光灯照射到时，粉丝们的应援才会被传达出来。具体的，聚光灯每次会照射到一个区间[1，r]，传达出的应援力度为区间中所有粉丝的应援力度之和乘以区间中最大的应援力度。同时，为了更好的应援,小林会通知某个粉丝更改他的应援力度，现在请你帮小林计算一下，每次聚光灯照射过来的时候，传达出的应援力度是多少？

【输入格式】

第一行包含两个整数n，m，表示一共有n名粉丝以及m次操作。

第二行包含n个整数，第i个数ai表示第i名粉丝的应援力度接下来m行，每行一个操作符opt。

当opt=1时，输入两个正整数1,r，表示聚光灯当前照射的区间为[1，r]，查询当前区间中传达出的应援力度。

当opt=2时，输入两个正整数x,y，表示将第x名粉丝的应援力度修改为y。

【输出格式】

对于每个查询操作，输出[1，r]区间中传达出的应援力度。

【样例输入1】

5 5

1 2 3 4 5 

1 1 3 

1 3 5

2 1 4 

1 1 3 

1 1 5

【样例输出1】

18 

60 

36 

90

【数据范围与约定】

对于30%的数据。1≤n m≤1000

对于另外20%的数据，保证所有opt=1。

对于100%的数据，1≤n，m≤100000，1≤1,r，x≤n，1≤ai,y≤100000.

第一行包含两个整数n，m，表示一共有n名粉丝以及m次操作。

第二行包含n个整数，第i个数ai表示第i名粉丝的应援力度接下来m行，每行一个操作符opt。

当opt=1时，输入两个正整数1,r，表示聚光灯当前照射的区间为[1，r]，查询当前区间中传达出的应援力度。

当opt=2时，输入两个正整数x,y，表示将第x名粉丝的应援力度修改为y。

5 5
1 2 3 4 5 
1 1 3 
1 3 5
2 1 4 
1 1 3 
1 1 5

18 
60 
36 
90