U469302题解

zhujianheng · 2025-08-06 14:09:30 · 个人记录

很明显，这题就是一个 rsq，只不过是两个数组的 rsq 而已，而且还是静态的，很明显可以用前缀和，时间复杂度 O(n)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll r[N],d[N],s1[N],s2[N],n,m;
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m>>k;
    for(ll i=1;i<=n;i++){
        cin>>r[i]>>d[i];
        s1[i]=(s1[i-1]+r[i])%k;
        s2[i]=(s2[i-1]+d[i])%k;
    }
    for(ll i=1;i<=m;i++){
        ll op,l,r;
        cin>>op>>l>>r;
        if(op==1) cout<<((s1[r]-s1[l-1])%k+k)%k<<endl;
        else cout<<((s2[r]-s2[l-1])%k+k)%k<<endl;
    }
    return 0;
}