H. 3.魔法传输

ljfyyds / 2023-08-23 / 原文

H. 3.魔法传输

这道题是区间加上等差数列的修改，我们直接去修改会很难想

然后我们可以发现他这个只有单点查询，所以我们就可以这么想，类似于一个差分操作

我们在每一次操作的时候我们就直接将这个区间都加上一，然后再将右端点的后一位减去区间长度

对于每一次单点查询我们就直接对这个点进行前缀和操作即可。

#include <bits/stdc++.h>
#define ls p << 1
#define rs p << 1 | 1
using namespace std;
typedef long long ll;

const int N = 4e5 + 10, mod = 1e9 + 7;
ll sum[N], add[N], n, m;

void pushup(int p)
{
    sum[p] = (sum[ls] + sum[rs]) % mod;
}

void pushdown(int p, int len)
{
    if (add[p])
    {
        add[ls] += add[p];
        add[rs] += add[p];
        sum[ls] += add[p] * (len - (len >> 1));
        sum[ls] %= mod;
        sum[rs] += add[p] * (len >> 1);
        sum[rs] %= mod;
        add[p] = 0;
    }
}

void update(int p, int l, int r, int ql, int qr, ll k)
{
    if (ql <= l && r <= qr)
    {
        add[p] += k;
        sum[p] += k * (r - l + 1);
        sum[p] %= mod;
        return;
    }
    pushdown(p, r - l + 1);
    int mid = (l + r) >> 1;
    if (ql <= mid)
        update(ls, l, mid, ql, qr, k);
    if (qr > mid)
        update(rs, mid + 1, r, ql, qr, k);
    pushup(p);
}

ll query(int p, int l, int r, int ql, int qr)
{
    if (ql <= l && r <= qr)
        return sum[p];
    pushdown(p, r - l + 1);
    ll res = 0;
    int mid = (l + r) >> 1;
    if (ql <= mid)
        res = (res + query(ls, l, mid, ql, qr)) % mod;
    if (qr > mid)
        res = (res + query(rs, mid + 1, r, ql, qr)) % mod;
    return res;
}

char op[2];
int main()
{
    cin >> n >> m;
    while (m--)
    {

        int x, y;
        cin >> op;
        if (op[0] == 'Q')
        {
            cin >> x;
            cout << query(1, 1, n, 1, x) << endl;
        }
        else
        {
            cin >> x >> y;
            update(1, 1, n, x, y, 1);
            update(1, 1, n, y + 1, y + 1, -(y - x + 1));
        }
    }
    return 0;
}