/*    ∫ ∫ ∫    ノヽ   (_  )  (_    ) (______ )  ヽ(´・ω・)ノ     |  /    UU */ #pragma region macro #include typedef long long int64; using namespace std; using P = pair; typedef vector vi; const int MOD = (int)1e9 + 7; const int64 INF = 1LL << 62; const int inf = 1<<30; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b ostream& operator<<(ostream& os, vector &V){ int N = V.size(); REP(i,N){ os << V[i]; if (i!=N-1) os << " "; } os << "\n"; return os; } template ostream& operator<<(ostream& os, pair const&P){ os << "("; os << P.first; os << " , "; os << P.second; os << ")"; return os; } template ostream& operator<<(ostream& os, set &S){ auto it=S.begin(); while(it!=S.end()){ os << *it; os << " "; it++; } os << "\n"; return os; } template ostream& operator<<(ostream& os, deque &q){ for(auto it=q.begin();it> dxdy = {mp(0,1),mp(1,0),mp(-1,0),mp(0,-1)}; #pragma endregion //fixed< struct SegmentTree{ /* ~~~~1-indexで実装~~~~ 1 2 3 4 5 6 7 ~~~~親・兄弟・子へのアクセスの仕方~~~~ i<<1 i i^1 i<<1|0 i<<1|1 */ using F = function; int N; F func; //関数(minとか) T identity; //単位元 vector data; //上から添字 2*Nくらいのノード SegmentTree(){} SegmentTree(F f,T identity):func(f),identity(identity){} void init(int n_){ N=1; while(N& v){ int n_ = v.size(); init(n_); for(int i=0; i>=1){ //右シフトして0にならない間 data[k] = func(data[k<<1], data[(k<<1)+1] ); } } //https://hcpc-hokudai.github.io/archive/structure_segtree_001.pdf //閉開区間[left,right)で T query(int left,int right){ T left_val=identity, right_val=identity; for(int l=left+N,r=right+N; l>=1,r>>=1){ if(l&1) left_val = func(left_val, data[l++] ); if(r&1) right_val = func(data[--r], right_val); } return func(left_val, right_val); } //葉の値を取得する T get_val(int idx){ return data[idx+N]; } }; template ostream& operator<<(ostream& os, SegmentTree &S){ int N = S.data.size(); int cnt = 0; int up = 1; for(int i=1;i> N >> Q; vector A(N); REP(i,N) cin>>A[i]; vector> queries; SegmentTree S( [](int64 a,int64 b)->int64{ return a+b; }, 0 ); S.init(N+1); REP(i,Q){ char A; int64 x,y; cin >> A >> x >> y; vector tmp = {0,--x,y}; if(A=='A') tmp[0]=1; queries.push_back(tmp); } reverse(ALL(queries)); vector ans(N,0); REP(i,Q){ int64 A,x,y; A=queries[i][0]; x=queries[i][1]; y=queries[i][2]; if(A){ int64 add_cnt = S.query(0,x+1); ans[x] += add_cnt*y; }else{ S.set_val(x,S.get_val(x) + 1); S.set_val(y,S.get_val(y) - 1); } } REP(i,N){ int64 add_cnt = S.query(0,i+1); ans[i] += add_cnt*A[i]; } cout << ans; }