【牛客挑战赛39 C 牛牛的等差数列（线段树）（*）】题目链接
文章图片
文章图片
#include
#define ll long long
using namespace std;
const int maxn = 2e5 + 50;
int val[maxn];
ll a[maxn<<2], d[maxn<<2];
ll sum[maxn<<2];
const int mod = 3*5*7*11*13*17*19*23;
void build(int rt, int l, int r){
if(l == r) {
scanf("%lld",&sum[rt]);
return;
}
int mid = (l+r)>>1;
build(rt<<1, l, mid);
build(rt<<1|1, mid+1, r);
sum[rt] = (sum[rt<<1] + sum[rt<<1|1])%mod;
}
void down(int node, int L, int R){
if(a[node] == 0 && d[node] == 0) return;
int m = (L+R)>>1;
a[node*2]=(a[node*2]+a[node])%mod;
a[node*2+1]=(a[node*2+1]+a[node]+1LL*(m-L+1)*d[node])%mod;
d[node*2]=(d[node*2]+d[node])%mod;
d[node*2+1]=(d[node*2+1]+d[node])%mod;
sum[node*2]=(sum[node*2]+a[node]*(m-L+1)+(1LL*(m-L)*(m-L+1)/2)*d[node])%mod;
sum[node*2+1]=(sum[node*2+1]+a[node]*(R-m)+(1LL*(R-m)*(m+1-L+R-L)/2)*d[node])%mod;
a[node]=0;
d[node]=0;
}
void update(int rt, int L, int R, int x, int y, int k, int dd){
if(L>=x&&R<=y){
sum[rt]=(sum[rt]+1LL*(R-L+1)*k+(1LL*(L+R-x-x)*(R-L+1)/2)*dd)%mod;
d[rt]=(d[rt]+dd)%mod;
a[rt]=(a[rt]+k+1LL*(L-x)*dd)%mod;
return;
}
down(rt, L, R);
int mid = (L+R)>>1;
if(x <= mid) update(rt<<1, L, mid, x, y, k, dd);
if(y > mid) update(rt<<1|1, mid+1, R, x, y, k, dd);
sum[rt] = (sum[rt<<1] + sum[rt<<1|1])%mod;
return;
}
int qry(int rt, int l, int r, int L, int R, int c){
if(L <= l && r <= R) return sum[rt]%c;
int ans = 0;
int mid = (l+r)>>1;
down(rt, l, r);
if(L <= mid) ans += qry(rt<<1, l, mid, L, R, c);
if(R > mid) ans += qry(rt<<1|1, mid+1, r, L, R, c);
return ans%c;
}
int main()
{
int n;
scanf("%d", &n);
build(1,1,n);
int q;
scanf("%d", &q);
while(q--){
int op;
scanf("%d", &op);
if(op == 1){
int l, r, fi, se;
scanf("%d%d%d%d", &l, &r, &fi, &se);
update(1, 1, n, l, r, fi, se);
}else{
int l, r, m;
scanf("%d%d%d", &l, &r, &m);
printf("%d\n", qry(1, 1, n, l, r, m));
}
}
}
推荐阅读
- 线段树|[类欧几里得算法 线段树] BZOJ 1938 [CROATIAN2010] ALADIN
- 牛客 C. 子段乘积（线段树）
- 牛客 数据结构（区间修改+求区间元素平方和）
- 校门外的树 线段树版
- 树链剖分|牛客练习赛51 F-ABCBA（树链剖分，线段树，状态转移）
- 数论|bzoj 1938 - 类欧几里得+线段树
- 线段树|FZU - 2277(树链剖分或dfs序+线段树)
- 并查集|[CF938G] Shortest Path Queries
- 牛客网 练习赛25 B最长区间