想问问大佬们这样用取模前缀和建树可以吗?
#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;
}