BZOJ 1798:[Ahoi 2009]Seqメンテナンスシーケンスseq(セグメントツリー乗算の混合動作)
2942 ワード
テーマ:クリックしてリンクを開く
1つの配列、3つの操作、1つ目は区間[a,b]の各数を乗算し、2つ目は区間[a,b]の各数にcを加え、3つ目は[a,b]の区間の和を照会し、pをタッチする.
2つの操作では、簡単にマークを下に伝えることはできません.乗算タグを渡すたびに、加算タグを同時に乗算タグに乗算します.例えば、ある区間に加算タグaddが入ってきて、その後、乗算タグmulが入ってきます.
結果は(x+add)*mul=x*mul+add*mulである.このように下にマークを渡すと相対的に独立します.再帰境界は加算タグを更新する前にそのノードのmulに乗り,左右の息子がdownするときはまず息子のaddを本ノードのmulに乗じる.
最後にsumについて述べると,例えば,本ノードの存在する加算タグxと乗算タグyであり,xを先に加えてyを乗じると,左息子のsumが(sum+x)*yに更新される.乗算タグが本ノードに伝達されると加算タグが更新されるので,sum[o<<1]=(左区間の長さ*x)+sum[o<<1]*yとなる.
テーマ:クリックしてリンクを開く
1つの配列、3つの操作、1つ目は区間[a,b]の各数を乗算し、2つ目は区間[a,b]の各数にcを加え、3つ目は[a,b]の区間の和を照会し、pをタッチする.
2つの操作では、簡単にマークを下に伝えることはできません.乗算タグを渡すたびに、加算タグを同時に乗算タグに乗算します.例えば、ある区間に加算タグaddが入ってきて、その後、乗算タグmulが入ってきます.
結果は(x+add)*mul=x*mul+add*mulである.このように下にマークを渡すと相対的に独立します.再帰境界は加算タグを更新する前にそのノードのmulに乗り,左右の息子がdownするときはまず息子のaddを本ノードのmulに乗じる.
最後にsumについて述べると,例えば,本ノードの存在する加算タグxと乗算タグyであり,xを先に加えてyを乗じると,左息子のsumが(sum+x)*yに更新される.乗算タグが本ノードに伝達されると加算タグが更新されるので,sum[o<<1]=(左区間の長さ*x)+sum[o<<1]*yとなる.
/**************************************************************
Problem: 1798
User: __ElemenT
Language: C++
Result: Accepted
Time:4676 ms
Memory:10184 kb
****************************************************************/
#include
#define lson o<<1, l, m
#define rson o<<1|1, m+1, r
typedef long long LL;
const int maxn = 100005;
int n, a, b, c, k, q;
LL sum[maxn<<2], add[maxn<<2], mul[maxn<<2], p;
void up(int o) {
sum[o] = (sum[o<<1]+sum[o<<1|1]) %p;
}
void build(int o, int l, int r) {
add[o] = 0, mul[o] = 1;
if(l == r) {
scanf("%lld", &sum[o]);
return;
}
int m = (l+r) >> 1;
build(lson);
build(rson);
up(o);
}
void down(int o, int len) {
// if(add[o] != 0 && mul[o] != 1) {
add[o<<1] = (add[o<<1] * mul[o] + add[o]) %p;
add[o<<1|1] = (add[o<<1|1] * mul[o] + add[o]) %p;
mul[o<<1] = mul[o<<1] * mul[o] %p;
mul[o<<1|1] = mul[o<<1|1] * mul[o] %p;
sum[o<<1] = (sum[o<<1] * mul[o] + add[o] * (len-(len>>1))) %p;
sum[o<<1|1] = (sum[o<<1|1] * mul[o] + add[o] * (len>>1)) %p;
add[o] = 0, mul[o] = 1;
// }
}
void update(int o, int l, int r, int op) {
if(a <= l && r <= b) {
if(op == 1) {
add[o] = add[o]*c %p;
mul[o] = mul[o]*c %p;
sum[o] = sum[o]*c %p;
} else {
add[o] = (add[o] + c) %p;
sum[o] = (sum[o] + (LL)c*(r-l+1)) %p;
}
return;
}
down(o, r-l+1);
int m = (l+r) >> 1;
if(a <= m) update(lson, op);
if(m < b ) update(rson, op);
up(o);
}
LL query(int o, int l, int r) {
if(a <= l && r <= b) return sum[o] %p;
down(o, r-l+1);
int m = (l+r) >> 1;
LL ans = 0;
if(a <= m) ans = query(lson);
if(m < b ) ans += query(rson);
return ans %p;
}
int main()
{
scanf("%d%lld", &n, &p);
build(1, 1, n);
scanf("%d", &q);
while(q--) {
scanf("%d%d%d", &k, &a, &b);
if(k != 3) {
scanf("%d", &c);
update(1, 1, n, k);
} else printf("%lld
", query(1, 1, n));
}
return 0;
}