F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Rikka with Bubble Sort

Time Limit: 30000/20000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 197    Accepted Submission(s): 15


Problem Description
Bubble sort is a simple but beautiful algorithm. And this problem is a simple data structure task which is relative to bubble sort.

Rikka has an integer array $A$ of length $n$, and then she makes $m$ operations on it.

There are two types of operations:
1. 1 L R, Rikka runs the following C program on $A$.
for (int i=L;i<R;i++) if (A[i]>A[i+1]) swap(A[i], A[i+1]);
2. 2 L R, Rikka wants to know the interval sum of $[L,R]$, i.e., $\sum_{i=L}^R A_i$.
 

Input
The first line contains two integers $n,m(1 \leq n \leq 10^6, 1 \leq m \leq 3 \times 10^4)$, and the second line contains $n$ integers $A_i(1 \leq A_i \leq 10^9)$.

And then $m$ lines follow, each line contains three integers $t,L,R(t \in \{1,2\}, 1 \leq L \leq R \leq n)$.
 

Output
For each query, output a single line with a single integer, the answer.
 

Sample Input
5 6 1 5 4 5 1 1 3 5 2 2 4 1 2 4 2 1 3 1 1 5 2 3 4
 

Sample Output
10 6 9
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-28 20:59:07, Gzip enabled