修改的是区间加，求的是区间和。
因为这里有取模，但还有一个就是输出的时候会满足在int范围，但是没说过程中会不会超过int，所以还是需要开long long，不然就真的会WA在30分，然后一脸懵逼。
#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <limits> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #include <unordered_map> #include <unordered_set> #define lowbit(x) ( x&(-x) ) #define pi 3.141592653589793 #define e 2.718281828459045 #define INF 0x3f3f3f3f #define eps 1e-6 #define HalF (l + r)>>1 #define lsn rt<<1 #define rsn rt<<1|1 #define Lson lsn, l, mid #define Rson rsn, mid+1, r #define QL Lson, ql, qr #define QR Rson, ql, qr #define myself rt, l, r using namespace std; typedef unsigned long long ull; typedef unsigned int uit; typedef long long ll; const int maxN = 5e4 + 7; int N, Q, len, s; ll a[maxN]; struct K { int l, r; ll sum, lazy; K(int a=0, int b=0, ll c=0, ll d=0):l(a), r(b), sum(c), lazy(d) {} inline int len() { return r - l + 1; } }t[240]; inline void update(int ql, int qr, ll w) { int st = (ql - 1) / len + 1, ed = (qr - 1) / len + 1; if(st == ed) { for(int i=ql; i<=qr; i++) { a[i] += w; t[st].sum += w; } return; } for(int i=ql; i<=t[st].r; i++) { a[i] += w; t[st].sum += w; } for(int i=t[ed].l; i<=qr; i++) { a[i] += w; t[ed].sum += w; } for(int i=st + 1; i<=ed - 1; i++) t[i].lazy += w; } inline ll query(int ql, int qr, ll mod) { ll ans = 0; int st = (ql - 1) / len + 1, ed = (qr - 1) / len + 1; if(st == ed) { for(int i=ql; i<=qr; i++) { ans += a[i] + t[st].lazy; if(ans >= mod) ans %= mod; } return ans; } for(int i=ql; i<=t[st].r; i++) { ans += a[i] + t[st].lazy; if(ans >= mod) ans %= mod; } for(int i=t[ed].l; i<=qr; i++) { ans += a[i] + t[ed].lazy; if(ans >= mod) ans %= mod; } for(int i=st + 1; i <= ed - 1; i++) { ans += t[i].sum + t[i].lazy * t[i].len() % mod; if(ans >= mod) ans %= mod; } return ans; } int main() { scanf("%d", &N); Q = N; for(int i=1; i<=N; i++) scanf("%lld", &a[i]); len = sqrt(N); s = N / len + (N % len == 0 ? 0 : 1); for(int i=1; i<=s; i++) { t[i].l = (i - 1) * len + 1; t[i].r = i * len; } t[s].r = N; for(int i=1; i<=s; i++) for(int j=t[i].l; j<=t[i].r; j++) t[i].sum += a[j]; int op, l, r, c; while(Q--) { scanf("%d%d%d%d", &op, &l, &r, &c); if(op) { printf("%lld\n", query(l, r, c + 1)); } else { update(l, r, c); } } return 0; }
