제출 #1334181

#제출 시각아이디문제언어결과실행 시간메모리
1334181edc원숭이와 사과 나무 (IZhO12_apple)C++20
100 / 100
351 ms137364 KiB
#include <iostream>

using namespace std;

const int RANGE = 1000000000;

class Sparse_Segtree
{
private:
    struct Node
    {
        int freq = 0,
            lazy = 0;
        Node *left = NULL,
              *right = NULL;
    };
    Node *root = new Node;
    const int n;

    void apply(Node *crt, int len, int val)
    {
        if(val == 1)
        {
            crt->lazy = val;
            crt->freq = len;
        }
    }

    void push(Node *crt, int l, int r)
    {
        if(crt->left == NULL)
            crt->left = new Node;
        if(crt->right == NULL)
            crt->right = new Node;
        int m = l + ((r - l) >> 1);
        apply(crt->left, m - l + 1, crt->lazy);
        apply(crt->right, r - (m + 1) + 1, crt->lazy);
    }

    void update(Node *crt, int l, int r, int ql, int qr, int val)
    {
        if(qr < l || r < ql)
            return;
        if(ql <= l && r <= qr)
        {
            apply(crt, r - l + 1, val);
            return;
        }
        push(crt, l, r);
        int m = l + ((r - l) >> 1);
        update(crt->left, l, m, ql, qr, val);
        update(crt->right, m + 1, r, ql, qr, val);
        crt->freq = crt->left->freq + crt->right->freq;
    }

    int query(Node *crt, int l, int r, int ql, int qr)
    {
        if(qr < l || r < ql)
            return 0;
        if(ql <= l && r <= qr)
            return crt->freq;
        push(crt, l, r);
        int m = l + ((r - l) >> 1);
        return query(crt->left, l, m, ql, qr) +
               query(crt->right, m + 1, r, ql, qr);
    }

public:
    Sparse_Segtree(int nn): n(nn) {}

    inline void update(int ql, int qr, int val)
    {
        update(root, 1, n, ql, qr, val);
    }

    inline int query(int ql, int qr)
    {
        return query(root, 1, n, ql, qr);
    }
};

int main()
{
    int Q;
    cin >> Q;
    Sparse_Segtree st(RANGE);
    //
    int C = 0;
    while(Q--)
    {
        int t, x, y;
        cin >> t >> x >> y;
        if(t == 1)
        {
            C = st.query(x + C, y + C);
            cout << C << '\n';
        }
        else // if(t == 2)
            st.update(x + C, y + C, 1);
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...