AcWing 243. JAVA
原题链接
困难
作者:
季之秋
,
2021-05-25 21:43:35
,
所有人可见
,
阅读 419
import java.util.*;
public class Main{
static int N = 100010;
static long tr1[] = new long[N], tr2[] = new long[N];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int last = 0;
for(int i = 1; i <= n; i ++){
int a = sc.nextInt();
modify(i, a - last); // 懒得开数组
last = a;
}
while(m -- != 0){
String s = sc.next();
int l = sc.nextInt();
int r = sc.nextInt();
if(s.charAt(0) == 'C'){
int c = sc.nextInt();
modify(l, c);
modify(r+1, -c); // 差分
}else{
System.out.println(query(r) - query(l - 1)); // 前缀和
}
}
}
static int lowbit(int x){
return x & -x;
}
static void modify(int x, int c){
for(int i = x; i < N; i += lowbit(i)){
tr1[i] += c;
tr2[i] += x * 1L * c; // x是下标,c是差分的值
}
}
static long query(int x){
long sum1 = 0, sum2 = 0;
for(int i = x; i >= 1; i -= lowbit(i)){
sum1 += tr1[i]; // 虚构矩形
sum2 += tr2[i]; // 被减去部分
}
return sum1 * (x+1) - sum2; // 正方形减去一部分
}
}