F题解 | #Witcher Genshin Impact#

Witcher Genshin Impact

https://ac.nowcoder.com/acm/contest/81068/F

F题解 | Witcher Genshin Impact

既然大家都是线段树我就来个分块吧

#include <bits/stdc++.h>
 
using LL = long long;
using PII = std::pair<LL, LL>;

const int N = 1e5 + 10;
const int M = 330;
const int MOD = 1145141;

LL n, m, total, length, v[N], belong[N], sum[M], l[M], r[M], rnum[M]; 

void build() {
    length = sqrt(n);
    total = (n - 1)/length + 1;
    for(int i = 1; i <= total; i++) {
        l[i] = r[i - 1] + 1, r[i] = i*length;
    }
    r[total] = n;

    for(int i = 1; i <= n; i++) belong[i] = (i - 1)/length + 1;
    
    //处理每个块的和
    for(int i = 1; i <= total; i++) {
        LL all = 1;
        for(int j = l[i]; j <= r[i]; j++) {
            sum[i] = (sum[i] + v[j]*all)%MOD;
            all = (all*v[j])%MOD;
            if(j == r[i]) rnum[i] = all;
        }
    }
}

void modify(int pos, int val) {
    v[pos] = val;
    int now = belong[pos];
    sum[now] = 0;

    LL all = 1;
    for(int i = l[now]; i <= r[now]; i++) {
        sum[now] = (sum[now] + v[i]*all)%MOD;
        all = (all*v[i])%MOD;
    }
    rnum[now] = all;
}

LL query(int L, int R) {
    if(belong[L] == belong[R]) {
        LL res = 0, all = 1;
        for(int i = L; i <= R; i++) {
            res = (res + all*v[i])%MOD;
            all = (all*v[i])%MOD;
        }
        return res;
    }
    
    LL res = 0, tempr = 1;
    for(int i = L; i <= r[belong[L]]; i++) {
        res = (res + tempr*v[i])%MOD;
        tempr = (tempr*v[i])%MOD;
    }
    
    for(int i = belong[L] + 1; i <= belong[R] - 1; i++) {
        res = (res + tempr*sum[i])%MOD;
        tempr = (tempr*rnum[i])%MOD;
    }

    for(int i = l[belong[R]]; i <= R; i++) {
        res = (res + tempr*v[i])%MOD;
        tempr = (tempr*v[i])%MOD;
    }
    
    return res;
}

void solve() {
    std::cin >> n >> m;
    for(int i = 1; i <= n; i++) std::cin >> v[i];
    build();

    while(m--) {
        int op, a, b;
        std::cin >> op >> a >> b;
        if(op == 1) std::cout << query(a, b) << '\n';
        else modify(a, b);
    }
}
  
int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
     
    int T = 1;;
    //std::cin >> T;
    while (T--) solve();
    return 0;
}

全部评论

相关推荐

评论
1
收藏
分享

创作者周榜

更多
正在热议
更多
# 你的mentor是什么样的人? #
4219次浏览 30人参与
# 你觉得mentor喜欢什么样的实习生 #
10469次浏览 293人参与
# 智慧芽求职进展汇总 #
18043次浏览 107人参与
# 帮我看看,领导说这话什么意思? #
6386次浏览 26人参与
# 没有家庭托举的我是怎么找工作的 #
12454次浏览 160人参与
# 怎么给家人解释你的工作? #
1460次浏览 16人参与
# 未岚大陆求职进展汇总 #
23856次浏览 114人参与
# 求职低谷期你是怎么度过的 #
5300次浏览 93人参与
# 26届秋招公司红黑榜 #
12533次浏览 43人参与
# 从哪些方向判断这个offer值不值得去? #
6627次浏览 95人参与
# 同bg的你秋招战况如何? #
158834次浏览 927人参与
# 度小满求职进展汇总 #
10130次浏览 53人参与
# 实习必须要去大厂吗? #
146706次浏览 1541人参与
# 校招泡的最久的公司是哪家? #
4626次浏览 22人参与
# 你有哪些缓解焦虑的方法? #
37188次浏览 835人参与
# 面试紧张时你会有什么表现? #
1740次浏览 21人参与
# 你喜欢工作还是上学 #
77599次浏览 860人参与
# 入职第一天,你准备什么时候下班 #
85497次浏览 467人参与
# 秋招想进国企该如何准备 #
97728次浏览 487人参与
# 简历无回复,你会继续海投还是优化再投? #
103595次浏览 819人参与
# 机械人的工作环境真的很差吗 #
25049次浏览 119人参与
# 独居后,你的生活是更好了还是更差了? #
28136次浏览 263人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务