W - Doom HDU - 5239 线段树 找取模的规律+求一个很大的数的平方对一个数取模的写法 特别的模数==2^63-2^31

时间：2021-03-09 12:42:26

这个题目一开始感觉还是有点难的，这个模数这么大，根本就不知道怎么写，然后去搜了题解，知道了怎么去求当x很大的时候x的平方对一个数取模怎么样不会爆掉。

然后还顺便发现了一个规律就是当一个数更新一定次数之后就不会变化了。

然后这个题目就很好写了，就是一个区间求和和一个区间修改。现在还不确定如果不加一个找到的规律是不是会超时。

现在写完了，写的过程你会发现，这个每次必须更新到叶节点才可以，不然这个是有问题的，因为我们要求和，

所以如果不更新到叶节点，那就无法求和，然后我们再计算一下复杂度，如果直接是m*n*logn 那么复杂度就太高了

但是有了这个规律之后你会发现每个数最大平方30次就不变了，所以就是说复杂度就是30*n*logn 这个就可以接受了。

所以这个规律很重要，知道这个之后就很好写了。

这个模数有点特别可以记一下 2^63-2^31

#include <cstring>

#include <queue>

#include <cstdlib>

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <map>

#include <vector>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

const int maxn = 1e5 + ;

typedef unsigned long long ull;

typedef long long ll;

const ull mod = ;

ll q_mul(ll a, ll b) {

    ll ans = ;

    while (b) {

        if (b & ) {

            ans = (ans + a) % mod;

        }

        a = (a + a) % mod;

        b >>= ;

    }

    return ans;

}

ull a[maxn], sum[maxn * ], flag[maxn * ];

void push_up(int id) {

    sum[id] = (sum[id << ] + sum[id <<  | ]) % mod;

    if (flag[id << ] && flag[id <<  | ]) flag[id] = ;

}

void build(int id, int l, int r) {

    flag[id] = ;

    if (l == r) {

        sum[id] = a[l];

        return;

    }

    int mid = (l + r) >> ;

    build(id << , l, mid);

    build(id <<  | , mid + , r);

    push_up(id);

}

ull query(int id, int l, int r, int x, int y) {

    if (x <= l && y >= r) return sum[id];

    int mid = (l + r) >> ;

    ull ans = ;

    if (x <= mid) ans += query(id << , l, mid, x, y) % mod, ans%mod;

    if (y > mid) ans += query(id <<  | , mid + , r, x, y) % mod, ans %= mod;

    return ans % mod;

}

void update(int id, int l, int r, int x, int y) {

    if (flag[id]) return;

    if (l == r) {

        ull ans = q_mul(sum[id], sum[id]);

        if (ans == sum[id]) flag[id] = ;

        sum[id] = ans;

        return;

    }

    int mid = (l + r) >> ;

    if (x <= mid) update(id << , l, mid, x, y);

    if (y > mid) update(id <<  | , mid + , r, x, y);

    push_up(id);

}

int main() {

    int t;

    scanf("%d", &t);

    for (int cas = ; cas <= t; cas++) {

        int n, m;

        scanf("%d%d", &n, &m);

        for (int i = ; i <= n; i++) scanf("%llu", &a[i]);

        build(, , n);

        ull ans = ;

        printf("Case #%d:\n", cas);

        while (m--) {

            int l, r;

            scanf("%d%d", &l, &r);

            ans += query(, , n, l, r);

            ans %= mod;

            printf("%llu\n", ans);

            update(, , n, l, r);

        }

    }

    return ;

}

线段树+找规律

相关文章