1 条题解
-
0Guest LV 0 MOD
-
1
#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