BZOJ 1798 Ahoi 2009 维护序列seq

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 100010 #define MO p #define LEFT (pos << 1) #define RIGHT (pos << 1|1) #define CNT (r - l + 1) using namespace std; long long p; struct Mark{ long long p_mark,m_mark; Mark() { m_mark = 1; p_mark = 0; } void operator +=(long long c) { p_mark = (p_mark + c) % MO; } void operator *=(long long c) { p_mark = (p_mark * c) % MO; m_mark = (m_mark * c) % MO; } void operator +=(const Mark &a) { m_mark = (m_mark * a.m_mark) % MO; p_mark = (p_mark * a.m_mark + a.p_mark) % MO; } }; struct Complex{ long long sum; Mark mark; }tree[MAX << 2]; int cnt,asks; long long src[MAX]; void BuildTree(int l,int r,int pos); void Mulitiply(int l,int r,int x,int y,int pos,long long c); void Plus(int l,int r,int x,int y,int pos,long long c); int Ask(int l,int r,int x,int y,int pos); inline void PushDown(int pos,int cnt); int main() { cin >> cnt >> p; for(int i = 1;i <= cnt; ++i) scanf("%lld",&src[i]); BuildTree(1,cnt,1); cin >> asks; for(int flag,i = 1;i <= asks; ++i) { scanf("%d",&flag); int x,y,z; switch(flag) { case 1: scanf("%d%d%d",&x,&y,&z); Mulitiply(1,cnt,x,y,1,z); break; case 2: scanf("%d%d%d",&x,&y,&z); Plus(1,cnt,x,y,1,z); break; case 3: scanf("%d%d",&x,&y); printf("%d ",(int)Ask(1,cnt,x,y,1)); break; } } return 0; } void BuildTree(int l,int r,int pos) { tree[pos].mark.p_mark = 0; tree[pos].mark.m_mark = 1; if(l == r) { tree[pos].sum = src[l] % MO; return ; } int mid = (l + r) >> 1; BuildTree(l,mid,LEFT); BuildTree(mid + 1,r,RIGHT); tree[pos].sum = (tree[LEFT].sum + tree[RIGHT].sum) % MO; } void Mulitiply(int l,int r,int x,int y,int pos,long long c) { if(l == x && y == r) { tree[pos].sum = (tree[pos].sum * c) % MO; tree[pos].mark *= c; return ; } PushDown(pos,CNT); int mid = (l + r) >> 1; if(y <= mid) Mulitiply(l,mid,x,y,LEFT,c); else if(x > mid) Mulitiply(mid + 1,r,x,y,RIGHT,c); else { Mulitiply(l,mid,x,mid,LEFT,c); Mulitiply(mid + 1,r,mid + 1,y,RIGHT,c); } tree[pos].sum = (tree[LEFT].sum + tree[RIGHT].sum) % MO; } void Plus(int l,int r,int x,int y,int pos,long long c) { if(l == x && y == r) { tree[pos].sum = (tree[pos].sum + (c * CNT) % MO) % MO; tree[pos].mark += c; return ; } PushDown(pos,CNT); int mid = (l + r) >> 1; if(y <= mid) Plus(l,mid,x,y,LEFT,c); else if(x > mid) Plus(mid + 1,r,x,y,RIGHT,c); else { Plus(l,mid,x,mid,LEFT,c); Plus(mid + 1,r,mid + 1,y,RIGHT,c); } tree[pos].sum = (tree[LEFT].sum + tree[RIGHT].sum) % MO; } int Ask(int l,int r,int x,int y,int pos) { if(l == x && y == r) return tree[pos].sum; PushDown(pos,CNT); int mid = (l + r) >> 1; if(y <= mid) return Ask(l,mid,x,y,LEFT); if(x > mid) return Ask(mid + 1,r,x,y,RIGHT); int left = Ask(l,mid,x,mid,LEFT); int right = Ask(mid + 1,r,mid + 1,y,RIGHT); return (left + right) % MO; } inline void PushDown(int pos,int cnt) { if(tree[pos].mark.m_mark == 1 && !tree[pos].mark.p_mark) return ; tree[LEFT].mark += tree[pos].mark; tree[RIGHT].mark += tree[pos].mark; if(tree[pos].mark.m_mark != 1) { tree[LEFT].sum = (tree[LEFT].sum * tree[pos].mark.m_mark) % MO; tree[RIGHT].sum = (tree[RIGHT].sum * tree[pos].mark.m_mark) % MO; tree[pos].mark.m_mark = 1; } if(tree[pos].mark.p_mark) { tree[LEFT].sum = (tree[LEFT].sum + ((cnt - (cnt >> 1)) * tree[pos].mark.p_mark) % MO) % MO; tree[RIGHT].sum = (tree[RIGHT].sum + ((cnt >> 1) * tree[pos].mark.p_mark) % MO) % MO; tree[pos].mark.p_mark = 0; } }