洛谷云剪贴板

作者: EndSaH 发表时间: 2019-01-24 22:11 https://www.luogu.org/paste/4kxm4tgf 公开
/**********************************************************
 * Author        : EndSaH
 * Email         : hjxhb1@gmail.com
 * Created Time  : 2019-01-24 17:02
 * FileName      : you.cpp
 * Website       : https://endsah.cf
 * *******************************************************/

#include <cstdio>
#include <cctype>

typedef long long LL;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug(s) debug("The massage in line %d, Function %s: %s\n", __LINE__, __FUNCTION__, s)
#define getchar() (ipos == iend and (iend = (ipos = _ibuf) + fread(_ibuf, 1, __bufsize, stdin), ipos == iend) ? EOF : *ipos++)
#define putchar(ch) (opos == oend ? fwrite(_obuf, 1, __bufsize, stdout), opos = _obuf : 0, *opos++ = (ch))
#define lson(x) ((x) << 1)
#define rson(x) ((x) << 1 | 1)
#define __bufsize (1 << 20)

char _ibuf[__bufsize], _obuf[__bufsize], _stk[20];
char *ipos = _ibuf, *iend = _ibuf, *opos = _obuf, *oend = _obuf + __bufsize, *stkpos = _stk;

struct END
{ ~END() { fwrite(_obuf, 1, opos - _obuf, stdout); } }
__;

inline int read()
{
    register int x = 0;
    register char ch;
    while (!isdigit(ch = getchar()));
    while (x = (x << 3) + (x << 1) + (ch & 15), isdigit(ch = getchar()));
    return x;
}

template <typename _INT>
inline void write(_INT x)
{
    while (*++stkpos = x % 10 ^ 48, x /= 10, x);
    while (stkpos != _stk)
        putchar(*stkpos--);
}

template <typename _Tp>
inline bool Chkmax(_Tp& x, const _Tp& y)
{ return x < y ? x = y, true : false; }

template <typename _Tp>
inline bool Chkmin(_Tp& x, const _Tp& y)
{ return x > y ? x = y, true : false; }

const int maxN = 3e5 + 2;
const int mod = 1e9 + 9;

inline int Mod(int x)
{ return x >= mod ? x - mod : x; }

int n, m, opt, L, R;
int fib[maxN];
int sum[maxN << 2], tag[2][maxN << 2], l[maxN << 2], r[maxN << 2];

inline void Add(int x, int a, int b)
{
    tag[0][x] = Mod(tag[0][x] + a), tag[1][x] = Mod(tag[1][x] + b);
    sum[x] = (sum[x] + (LL)b * fib[r[x] - l[x] + 2] + (LL)a * fib[r[x] - l[x] + 1] - b) % mod;
}

inline void Pushup(int x)
{ sum[x] = Mod(sum[lson(x)] + sum[rson(x)]); }

inline void Pushdown(int x)
{
    if (tag[0][x])
    {
        int mid = (l[x] + r[x]) >> 1, _a, _b;
        _a = ((LL)tag[0][x] * fib[mid - l[x]] + (LL)tag[1][x] * fib[mid - l[x] + 1]) % mod;
        _b = ((LL)tag[0][x] * fib[mid - l[x] + 1] + (LL)tag[1][x] * fib[mid - l[x] + 2]) % mod;
        Add(lson(x), tag[0][x], tag[1][x]), Add(rson(x), _a, _b);
        tag[0][x] = tag[1][x] = 0;
    }
}

void Build(int l, int r, int curr)
{
    ::l[curr] = l, ::r[curr] = r;
    if (l == r)
        sum[curr] = Mod(Mod(read()));
    else
    {
        register int mid = (l + r) >> 1;
        Build(l, mid, lson(curr)), Build(mid + 1, r, rson(curr));
        Pushup(curr);
    }
}

void Change(int curr)
{
    if (L <= l[curr] and R >= r[curr])
    {
        Add(curr, fib[l[curr] - L + 1], fib[l[curr] - L + 2]);
        return;
    }
    register int mid = (l[curr] + r[curr]) >> 1;
    Pushdown(curr);
    if (L <= mid)
        Change(lson(curr));
    if (R > mid)
        Change(rson(curr));
    Pushup(curr);
}

int Ask(int curr)
{
    if (L > r[curr] or R < l[curr])
        return 0;
    if (L <= l[curr] and R >= r[curr])
        return sum[curr];
    Pushdown(curr);
    return Mod(Ask(lson(curr)) + Ask(rson(curr)));
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("3.in", "r", stdin);
    freopen("you.out", "w", stdout);
#endif
    n = read(), m = read();
    Build(1, n, 1);
    fib[1] = fib[2] = 1;
    for (register int i = 3; i <= n; ++i)
        fib[i] = Mod(fib[i - 1] + fib[i - 2]);
    fib[n + 1] = Mod(fib[n] + fib[n - 1]);
    while (m--)
    {
        opt = read(), L = read(), R = read();
        if (opt == 1)
            Change(1);
        else
            write(Ask(1)), putchar('\n');
    }
    return 0;
}

源码  复制

```cpp
/**********************************************************
 * Author        : EndSaH
 * Email         : hjxhb1@gmail.com
 * Created Time  : 2019-01-24 17:02
 * FileName      : you.cpp
 * Website       : https://endsah.cf
 * *******************************************************/
 
#include <cstdio>
#include <cctype>

typedef long long LL;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug(s) debug("The massage in line %d, Function %s: %s\n", __LINE__, __FUNCTION__, s)
#define getchar() (ipos == iend and (iend = (ipos = _ibuf) + fread(_ibuf, 1, __bufsize, stdin), ipos == iend) ? EOF : *ipos++)
#define putchar(ch) (opos == oend ? fwrite(_obuf, 1, __bufsize, stdout), opos = _obuf : 0, *opos++ = (ch))
#define lson(x) ((x) << 1)
#define rson(x) ((x) << 1 | 1)
#define __bufsize (1 << 20)

char _ibuf[__bufsize], _obuf[__bufsize], _stk[20];
char *ipos = _ibuf, *iend = _ibuf, *opos = _obuf, *oend = _obuf + __bufsize, *stkpos = _stk;

struct END
{ ~END() { fwrite(_obuf, 1, opos - _obuf, stdout); } }
__;

inline int read()
{
    register int x = 0;
    register char ch;
    while (!isdigit(ch = getchar()));
    while (x = (x << 3) + (x << 1) + (ch & 15), isdigit(ch = getchar()));
    return x;
}

template <typename _INT>
inline void write(_INT x)
{
    while (*++stkpos = x % 10 ^ 48, x /= 10, x);
    while (stkpos != _stk)
        putchar(*stkpos--);
}

template <typename _Tp>
inline bool Chkmax(_Tp& x, const _Tp& y)
{ return x < y ? x = y, true : false; }

template <typename _Tp>
inline bool Chkmin(_Tp& x, const _Tp& y)
{ return x > y ? x = y, true : false; }

const int maxN = 3e5 + 2;
const int mod = 1e9 + 9;

inline int Mod(int x)
{ return x >= mod ? x - mod : x; }

int n, m, opt, L, R;
int fib[maxN];
int sum[maxN << 2], tag[2][maxN << 2], l[maxN << 2], r[maxN << 2];

inline void Add(int x, int a, int b)
{
    tag[0][x] = Mod(tag[0][x] + a), tag[1][x] = Mod(tag[1][x] + b);
    sum[x] = (sum[x] + (LL)b * fib[r[x] - l[x] + 2] + (LL)a * fib[r[x] - l[x] + 1] - b) % mod;
}

inline void Pushup(int x)
{ sum[x] = Mod(sum[lson(x)] + sum[rson(x)]); }

inline void Pushdown(int x)
{
    if (tag[0][x])
    {
        int mid = (l[x] + r[x]) >> 1, _a, _b;
        _a = ((LL)tag[0][x] * fib[mid - l[x]] + (LL)tag[1][x] * fib[mid - l[x] + 1]) % mod;
        _b = ((LL)tag[0][x] * fib[mid - l[x] + 1] + (LL)tag[1][x] * fib[mid - l[x] + 2]) % mod;
        Add(lson(x), tag[0][x], tag[1][x]), Add(rson(x), _a, _b);
        tag[0][x] = tag[1][x] = 0;
    }
}

void Build(int l, int r, int curr)
{
    ::l[curr] = l, ::r[curr] = r;
    if (l == r)
        sum[curr] = Mod(Mod(read()));
    else
    {
        register int mid = (l + r) >> 1;
        Build(l, mid, lson(curr)), Build(mid + 1, r, rson(curr));
        Pushup(curr);
    }
}

void Change(int curr)
{
    if (L <= l[curr] and R >= r[curr])
    {
        Add(curr, fib[l[curr] - L + 1], fib[l[curr] - L + 2]);
        return;
    }
    register int mid = (l[curr] + r[curr]) >> 1;
    Pushdown(curr);
    if (L <= mid)
        Change(lson(curr));
    if (R > mid)
        Change(rson(curr));
    Pushup(curr);
}

int Ask(int curr)
{
    if (L > r[curr] or R < l[curr])
        return 0;
    if (L <= l[curr] and R >= r[curr])
        return sum[curr];
    Pushdown(curr);
    return Mod(Ask(lson(curr)) + Ask(rson(curr)));
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("3.in", "r", stdin);
    freopen("you.out", "w", stdout);
#endif
    n = read(), m = read();
    Build(1, n, 1);
    fib[1] = fib[2] = 1;
    for (register int i = 3; i <= n; ++i)
        fib[i] = Mod(fib[i - 1] + fib[i - 2]);
    fib[n + 1] = Mod(fib[n] + fib[n - 1]);
    while (m--)
    {
        opt = read(), L = read(), R = read();
        if (opt == 1)
            Change(1);
        else
            write(Ask(1)), putchar('\n');
    }
    return 0;
}
```