간단 한 정수 문제 2 (트 리 배열 구현 구간 수정 + 구간 조회)

제목.
제목 전송 문 은 N 의 수열 A 와 M 개의 명령 을 지정 합 니 다. 각 명령 은 다음 과 같은 두 가지 중 하나 일 수 있 습 니 다. 1. "C l r d" 는 A [l], A [l + 1],..., A [r] 를 모두 d 로 표시 합 니 다.2. "Q l r" 는 수열 의 l ~ r 개수 의 합 을 묻 는 것 을 나타 낸다.모든 질문 에 정 수 를 출력 하여 답 을 표시 합 니 다.형식 첫 줄 두 개의 정수 N, M 을 입력 하 십시오.두 번 째 줄 N 개의 정수 A [i].다음 M 줄 은 M 개의 명령 을 표시 하고 모든 명령 의 형식 은 제목 설명 과 같다.출력 형식 은 모든 질문 에 정 수 를 출력 하여 답 을 표시 합 니 다.각 답안 이 한 줄 을 차지 하 다.
샘플 입력
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

샘플 출력
4
55
9
15

해제
∑ i = 1 x b [ i ] \sum\limits_{i = 1} ^ {x} b {[i]} i = 1 ∑ x b [i] 가 a [i] a [i] a [i] 가 증가 하 는 값 이면 a [1 ∼ x] a [1 \ \ sim x] a [1 ∼ x] 가 전체적으로 증가 하 는 값 은 ∑ i = 1 x ∑ j = 1 i b [j] \ sum \ \ limits{i=1}^{x}\sum\limits_{j = 1} ^ {i} b [j] i = 1 ∑ x j = 1 ∑ i b [j] 상식 은 ∑ i = 1 x ∑ j = 1 i b [j] = ∑ i = 1 x (x − i + 1) ∗ b [i] = (x + 1) ∑ i = 1 x b [i] - ∑ i x i ∗ b [i] \ \ sum \ \ limits{i=1}^{x}\sum\limits_{j=1}^{i}b[j] =\sum\limits_{i=1}^{x}(x-i+1)*b[i]=(x+1)\sum\limits_{i=1}^{x}b[i]-\sum\limits_{i}^{x}i*b[i] i=1∑x​j=1∑i​b[j]=i=1∑x​(x−i+1)∗b[i]=(x+1)i=1∑x​b[i]−i∑x​i∗b[i]
각 명령 어 "C l r d" 에 대해 네 가지 동작 을 수행 합 니 다.
  • c 0 c0 c0 에서 l l l 의 위치 에 있 는 숫자 에 d d
  • 를 더 합 니 다.
  • c 0 c0 c0 에서 r + 1 r + 1 r + 1 의 위치 에 있 는 숫자 를 - d - d - d - d
  • c 1 c 에서1 c1 에서 l l l 의 위치 에 있 는 숫자 에 l * 8727 ° d l * d l * 8727 ° d
  • 를 더 합 니 다.
  • c 1 c 에서1 c1 에서 r + 1 r + 1 r + 1 의 위치 에 있 는 숫자 를 - (r + 1) ∗ d - (r + 1) * d − (r + 1) ∗ d
  • 각 지령 'Q l r' 에 대한 답 은 (s u m [r] + (r + 1) ∗ a s k (c 0, r) − a s k (c 1, r) − s u m ([l - 1] + (l - 1] + l ∗ a s k (c 0, l - 1) − a s k (c 1, l - 1, l - 1, l - 1) (sum [r] + (r + 1) * ask (c + 1) * ask (c 1) * ask (c 0, r) - ask (c 0, r) - ask (c 1, r) - ask (c 1) - ask (c 1, c 1) - ask (c 1) - ask (c 1) - ask ( 1, l - 1) (sum [r] + (r + 1) ∗ ask (c0, r) − ask (c1, r) − sum ([l − 1] + l ∗ ask(c0​,l−1)−ask(c1​,l−1))
    code
    #include 
    using namespace std; 
    const int maxn = 1e5 + 100; 
    typedef long long LL; 
    
    template <typename T>
    inline void read(T &s) {
        s = 0; 
        T w = 1, ch = getchar(); 
        while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
        while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
        s *= w; 
    }
    
    int n, m; 
    int a[maxn];
    LL c[2][maxn], sum[maxn]; 
    
    inline int lowbit(int x) { return x & (-x); }
    
    inline void add(int k, int x, int y) {
        for (; x <= n; x += lowbit(x)) 
            c[k][x] += y; 
    }
    
    inline LL ask(int k, int x) {
        LL ans = 0ll; 
        for (; x; x -= lowbit(x)) 
            ans += c[k][x]; 
        
        return ans; 
    }
    
    int main() {
        read(n), read(m); 
        for (int i = 1; i <= n; ++i) {
            read(a[i]); 
            sum[i] = sum[i - 1] + a[i]; 
        }
        
        while (m--) {
            char ch; cin >> ch;  
            
            if (ch == 'C') {
                int l, r, d; 
                read(l), read(r), read(d); 
                
                add(0, l, d); 
                add(0, r + 1, -d); 
                add(1, l, l * d); 
                add(1, r + 1, -(r + 1) * d); 
            }
            else if (ch == 'Q') {
                int l, r; 
                read(l), read(r); 
                
                LL ans = sum[r] + (r + 1) * ask(0, r) - ask(1, r); 
                // check; 
                ans -= sum[l - 1] + l * ask(0, l - 1) - ask(1, l - 1);  
                
                printf("%lld
    "
    , ans); } } return 0; }

    좋은 웹페이지 즐겨찾기