Hướng dẫn bài GOODARR

Trùm CUỐI 2020-10-16 16:07:47 2021-12-13 8:34:22

Link đến bài GOODARR

Tổng cộng 1 trả lời

Trùm CUỐI

Liên kết tới các thảo luận về Cập nhật lười trên cây IT với việc tăng một đoạn các phần tử mà cách tăng là một cấp số cộng

  • Mã nguồn C++ minh họa
#include <bits/stdc++.h>
#define f(i,a,b) for (int i = a; i <= b; i++)

using namespace std;

const int RIGHT = 131072;
const int SIZE = 255005;
int N, Q, K[SIZE], D[SIZE], LK[SIZE], LD[SIZE], S[SIZE];

int query(int l, int r, int n = 1, int a = 1, int b = RIGHT)
{
    if(a > r || b < l) return 0;
    if(a >= l && b <= r) return S[n];

    if(LK[n] != 0 || LD[n] != 0)
    {
        int sz = (b-a+1) / 2;
        K[2*n] += LK[n], K[2*n+1] += LK[n] + LD[n]*sz;
        D[2*n] += LD[n], D[2*n+1] += LD[n];
        S[2*n] += LK[n]*sz + LD[n]*sz*(sz-1) / 2;
        S[2*n+1] += (LK[n] + LD[n]*sz)*sz + LD[n]*sz*(sz-1) / 2;
        LK[2*n] += LK[n], LK[2*n+1] += LK[n] + LD[n]*sz;
        LD[2*n] += LD[n], LD[2*n+1] += LD[n];
        LK[n] = LD[n] = 0;
    }

    int mid = (a+b) / 2;
    return query(l,r,2*n,a,mid) + query(l,r,2*n+1,mid+1,b);
}

void update(int l, int r, int k, int d, int n = 1, int a = 1, int b = RIGHT)
{
    if(a >= l && b <= r)
    {
        K[n] += k, D[n] += d;
        LK[n] += k, LD[n] += d;
        int sz = (b-a+1);
        S[n] += k*sz + d*sz*(sz-1) / 2;
        return;
    }

    if(LK[n] != 0 || LD[n] != 0)
    {
        int sz = (b-a+1) / 2;
        K[2*n] += LK[n], K[2*n+1] += LK[n] + LD[n]*sz;
        D[2*n] += LD[n], D[2*n+1] += LD[n];
        S[2*n] += LK[n]*sz + LD[n]*sz*(sz-1) / 2;
        S[2*n+1] += (LK[n] + LD[n]*sz)*sz + LD[n]*sz*(sz-1) / 2;
        LK[2*n] += LK[n], LK[2*n+1] += LK[n] + LD[n]*sz;
        LD[2*n] += LD[n], LD[2*n+1] += LD[n];
        LK[n] = LD[n] = 0;
    }

    int mid = (a+b) / 2;
    if(l <= mid) update(l,min(mid,r),k,d,2*n,a,mid);
    if(r > mid) update(max(mid+1,l),r,k + d*max(mid-l+1,0),d,2*n+1,mid+1,b);

    S[n] = S[2*n] + S[2*n+1];
}

int main()
{
    scanf("%d %d", &N, &Q);
    while(Q--)
    {
        int t;
        scanf("%d", &t);
        if(t == 1)
        {
            int l,r,k,d;
            scanf("%d %d %d %d", &l, &r, &k, &d);
            update(l,r,k,d);
        }
        else
        {
            int l,r;
            scanf("%d %d", &l, &r);
            printf("%d\n", query(l,r));
        }
    }
}