solution
用线段树维护即可。
考虑线段树的懒标记如何维护。我们维护两个懒标记,添加到当前位置的数列在该区间开始位置的首项之和,表示这些添加的数列公差之和。
因为如果往一个位置添加了一个等差数列。其中某个位置可以看作,那么再添加一个等差数列,那么该位置就可以看作,相当于添加了一个首项为公差为的等差数列。
挺简单的思路,就是有点难调233
code
/* * @Author: wxyww * @Date: 2020-04-17 19:25:25 * @Last Modified time: 2020-04-17 20:49:01 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int N = 200010,mod = 223092870; #define int ll ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } int tree[N << 2],lazy1[N << 2],lazy2[N << 2]; int a[N]; void build(int rt,int l,int r) { if(l == r) { tree[rt] = a[l];return; } int mid = (l + r) >> 1; build(rt << 1,l,mid); build(rt << 1 | 1,mid + 1,r); tree[rt] = (tree[rt << 1] + tree[rt << 1 | 1]) % mod; } void upd(int &x,int y) { x = (x + y) % mod; } void pushdown(int rt,int ln,int rn,int l,int r) { if(lazy1[rt] || lazy2[rt]) { upd(lazy1[rt << 1],lazy1[rt]); upd(lazy2[rt << 1],lazy2[rt]); upd(lazy2[rt << 1 | 1],lazy2[rt]); ll f1 = lazy1[rt],f2 = (lazy1[rt] + 1ll * ln * lazy2[rt]) % mod; upd(lazy1[rt << 1 | 1],f2); upd(tree[rt << 1],1ll * (f1 + f1 + (ln - 1) * lazy2[rt]) * ln / 2 % mod); upd(tree[rt << 1 | 1],1ll * (f2 + f2 + 1ll * (rn - 1) * (lazy2[rt])) * rn / 2 % mod); lazy1[rt] = lazy2[rt] = 0; } } ll query(int rt,int l,int r,int L,int R) { if(L <= l && R >= r) return tree[rt]; int mid = (l + r) >> 1; pushdown(rt,mid - l + 1,r - mid,l,r); int ret = 0; if(L <= mid) ret += query(rt << 1,l,mid,L,R); if(R > mid) ret += query(rt << 1 | 1,mid + 1,r,L,R); return ret % mod; } void update(int rt,int l,int r,int L,int R,ll x,ll d) { ll xx = x + (l - L) * d; // printf("%lld %lld %lld %lld\n",l,r,x,xx); if(L <= l && R >= r) { // printf("%lld %lld\n",l,r); tree[rt] += 1ll * (xx + xx + 1ll * d * (r - l)) * (r - l + 1) / 2 % mod; tree[rt] %= mod; // printf("%lld %lld %lld\n",rt,l,r); // printf("%lld %lld %lld\n",l,r,(xx + xx + 1ll * d * (r - l)) * (r - l + 1) / 2); lazy1[rt] += xx;lazy2[rt] += d; lazy1[rt] %= mod;lazy2[rt] %= mod; return; } int mid = (l + r) >> 1; pushdown(rt,mid - l + 1,r - mid,l,r); if(L <= mid) update(rt << 1,l,mid,L,R,x,d); if(R > mid) update(rt << 1 | 1,mid + 1,r,L,R,x,d); tree[rt] = (tree[rt << 1] + tree[rt << 1 | 1]) % mod; } signed main() { // freopen("1.in","r",stdin); int n = read(); for(int i = 1;i <= n;++i) a[i] = read(); build(1,1,n); int Q = read(); while(Q--) { int opt = read(); if(opt == 1) { int l = read(),r = read(),x = read() % mod,d = read() % mod; update(1,1,n,l,r,x,d); } else { int l = read(),r = read(),m = read(); printf("%lld\n",query(1,1,n,l,r) % m); } // puts("!!!"); // printf("!!%lld\n",lazy1[2]); } return 0; }