/ WHOJ / 题库 / 神犇 /

题解

1 条题解

  • 1
    @ 2022-09-04 14:41:30
    #include <iostream>
    #include <cstdio>
    #define sL (s << 1)
    #define sR (s << 1 | 1)
    
    using namespace std;
    typedef long long ll;
    const ll Mod = 1000000007ll;
    const int N = 4e5 + 5;
    
    ll tl[N], tr[N], val[N];
    int n, m; 
    
    inline void AddTag(const int &s, const int &l, const int &r, const ll &vl, const ll &vr, const ll &va)
    {
        tl[s] += vl; tr[s] += vr; val[s] += va;
    }
    
    inline void Down(const int &s, const int &l, const int &r)
    {
        if (!tl[s] && !tr[s]) return ;
        int mid = l + r >> 1;
        AddTag(sL, l, mid, tl[s], tl[s] + (mid - l) * val[s], val[s]); 
        AddTag(sR, mid + 1, r, tr[s] - (r - mid - 1) * val[s], tr[s], val[s]);
        tl[s] = tr[s] = val[s] = 0;
    }
    
    
    inline void Modify(const int &s, const int &l, const int &r, const int &x, const int &y, const ll &vl, const ll &vr)
    {
        if (x == l && y == r) return AddTag(s, l, r, vl, vr, 1);
        Down(s, l, r); int mid = l + r >> 1;
        if (y <= mid) Modify(sL, l, mid, x, y, vl, vr);
         else if (x > mid) Modify(sR, mid + 1, r, x, y, vl, vr);
          else 
          {
            Modify(sL, l, mid, x, mid, vl, vl + mid - x);
            Modify(sR, mid + 1, r, mid + 1, y, vr - (y - mid - 1), vr);
          } 
    }
    
    inline ll Query(const int &s, const int &l, const int &r, const int &x)
    {
        if (l == r) return tl[s];
        Down(s, l, r); int mid = l + r >> 1;
        if (x <= mid) return Query(sL, l, mid, x);
         else return Query(sR, mid + 1, r, x); 
    }
    
    inline void put(ll x)
    {
        if (x > 9) put(x / 10);
        putchar(x % 10 + 48);
    }
    
    int main()
    {
        scanf("%d%d", &n, &m); int u, v;
        while (m--)
        {
            char tp;
            while ((tp = getchar()) != 'C' && tp != 'Q');
            if (tp == 'C')
            {
                scanf("%d%d", &u, &v);
                Modify(1, 1, n, u, v, 1, v - u + 1); 
            }
            else 
            {
                scanf("%d", &u);
                put(Query(1, 1, n, u) % Mod), putchar('\n');
            }
        }
        return 0; 
    } 
    
  • 1

信息

ID
1636
难度
8
分类
线段树数据结构 点击显示
标签
递交数
1
已通过
1
通过率
100%
上传者