CSUSTOJ 你真的会！（线段树）

本文主要是介绍CSUSTOJ 你真的会！（线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：
对于$f(L,R)$，可以发现$L=R$时，$f(L,R)=a[L]+1$。
否则等于$f(L,K)\ast f(K,R)，L\le K\le R$。
所以直接用线段树维护就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;
const int mod = 1e9 + 9;struct Tree {int l,r;ll sum;ll lazy;
}t[maxn << 2];ll qpow(ll x,ll n) {ll res = 1;while(n) {if(n & 1) res = res * x % mod;x = x * x % mod;n >>= 1;}return res;
}void pushup(int i) {t[i].sum = t[i * 2].sum * t[i * 2 + 1].sum % mod;
}void pushdown(int i) {if(t[i].lazy != -1) {t[i * 2].sum = qpow(t[i].lazy,t[i * 2].r - t[i * 2].l + 1);t[i * 2 + 1].sum = qpow(t[i].lazy,t[i * 2 + 1].r - t[i * 2 + 1].l + 1);t[i * 2].lazy = t[i * 2 + 1].lazy = t[i].lazy;t[i].lazy = -1;}
}void build(int i,int l,int r) {t[i].l = l;t[i].r = r;t[i].lazy = -1;if(l == r) {scanf("%lld",&t[i].sum);t[i].sum++;return;}int m = (l + r) >> 1;build(i * 2,l,m);build(i * 2 + 1,m + 1,r);pushup(i);
}void update(int i,int x,int y,ll v) {if(x <= t[i].l && t[i].r <= y) {t[i].lazy = v + 1;t[i].sum = qpow(v + 1,t[i].r - t[i].l + 1);return;}pushdown(i);int m = (t[i].l + t[i].r) >> 1;if(x <= m) update(i * 2,x,y,v);if(y > m) update(i * 2 + 1,x,y,v);pushup(i);
}ll query(int i,int x,int y) {if(x <= t[i].l && t[i].r <= y) {return t[i].sum;}pushdown(i);int m = (t[i].l + t[i].r) >> 1;ll res1 = 0,res2 = 0;if(x <= m) res1 += query(i * 2,x,y);if(y > m) res2 += query(i * 2 + 1,x,y);if(res1 && res2) return res1 * res2 % mod;return (res1 + res2) % mod;
}int main() {int n,m;scanf("%d%d",&n,&m);build(1,1,n);for(int i = 1;i <= m;i++) {int op;scanf("%d",&op);if(op == 1) {int l,r,v;scanf("%d%d%d",&l,&r,&v);update(1,l,r,v);} else if(op == 2) {int l,v;scanf("%d%d",&l,&v);update(1,l,l,v);} else if(op == 3) {int l,r;scanf("%d%d",&l,&r);printf("%lld\n",query(1,l,r));}}return 0;
}

这篇关于CSUSTOJ 你真的会！（线段树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---