网友投稿 722 2022-09-02
BZOJ 1798 维护序列 （多校连萌，对线段树进行加乘混合操作）
题目地址：#include #include #include #include #include #include #include #include #include #include const int inf = 0x3f3f3f3f;//1061109567typedef long long LL;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;const int maxn = 100010;LL add[maxn<<2],mul[maxn<<2],sum[maxn<<2];LL p;void pushup(int rt){ sum[rt] = (sum[rt<<1] + sum[rt<<1|1]) % p;}void pushdown(int rt,int m){ if(add[rt] == 0 && mul[rt] == 1) return; add[rt<<1] = (add[rt<<1]*mul[rt] + add[rt]) % p;//前面包括的是乘，后面包括的是加和先加后乘的 //假设sum[rt]为一段和，(sum[rt]+x)*p,最后的结果只是这一段的和乘以p加上x*p add[rt<<1|1] = (add[rt<<1|1]*mul[rt] + add[rt]) % p; mul[rt<<1] = (mul[rt<<1] * mul[rt]) % p; mul[rt<<1|1] = (mul[rt<<1|1]*mul[rt]) % p; sum[rt<<1] = (sum[rt<<1] * mul[rt] + (m - (m>>1)) * add[rt]) % p;//注意里面的参数 sum[rt<<1|1] = (sum[rt<<1|1] * mul[rt] + (m>>1) * add[rt]) % p; add[rt] = 0,mul[rt] = 1;}void updata(int L,int R,int value,int l,int r,int rt,int op){ if(l >= L && r <= R) { if(op == 1) { add[rt] = add[rt] * value % p; mul[rt] = mul[rt] * value % p; sum[rt] = sum[rt] * value % p; } else { add[rt] = (add[rt] + value) % p; sum[rt] = (sum[rt] + (r - l + 1) * (LL)value) % p; } return; } pushdown(rt,r-l+1); int m = (l + r)>>1; if(L <= m) updata(L,R,value,lson,op); if(R > m) updata(L,R,value,rson,op); pushup(rt);}void build(int l,int r,int rt){ add[rt] = 0,mul[rt] = 1; if(l == r) { scanf("%lld",&sum[rt]); return; } int m = (l + r) >> 1; build(lson); build(rson); pushup(rt);}LL query(int L,int R,int l,int r,int rt){ if(l >= L && r <= R) return sum[rt]; pushdown(rt,r-l+1); int m = (l + r)>>1; LL ans = 0; if(L <= m) ans += query(L,R,lson); if(R > m) ans += query(L,R,rson); return ans % p;}int main(){ int n; while(scanf("%d%lld",&n,&p) != EOF) { build(1,n,1); int m; scanf("%d",&m); for(int i=0; i 版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论，来抢沙发吧~
暂时没有评论，来抢沙发吧~