关于取模前缀和的一些问题
查看原帖
关于取模前缀和的一些问题
1368189
znzryb楼主2024/9/17 21:46

想问问大佬们这样用取模前缀和建树可以吗?

#include <iostream>
#define ll long long
using namespace std;
const ll maxn=1e5+10,maxn4=4*maxn;
ll n,q,m,a[maxn],sumA[maxn];
struct rangeSES {
    ll s;ll e;ll sumR;
}tree[maxn4];
void buildTree(ll fa) {
    if(tree[fa].e==tree[fa].s) return;
    ll lson=fa<<1,rson=lson+1;
    tree[lson].s=tree[fa].s,tree[lson].e=(tree[fa].s+tree[fa].e)/2;
    tree[lson].sumR=(sumA[tree[lson].e]-sumA[tree[lson].s-1])%m;
    tree[rson].s=tree[lson].e+1,tree[rson].e=tree[fa].e;
    tree[rson].sumR=(sumA[tree[rson].e]-sumA[tree[rson].s-1])%m;
    buildTree(lson);
    buildTree(rson);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>q>>m;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        a[i]%=m;
    }
    for(int i=1;i<=n;i++) {
        sumA[i]=(a[i]+sumA[i-1])%m;
    }
    tree[1].s=1;tree[1].e=n;tree[1].sumR=sumA[n];
    buildTree(1);


    // debug
    for(int i=1;i<=4*n;i++) {
        cout<<tree[i].s<<" "<<tree[i].e<<" "<<tree[i].sumR<<endl;
    }
    return 0;
}
2024/9/17 21:46
加载中...