#include "bits/stdc++.h" #include #define rep(i,n) for(int i = 0; i < n; i++) typedef long long ll; typedef unsigned long long ull; using namespace std; #define vll vector> #define vl vector #define vi vector #define vii vector> #define pb push_back #define pf push_front #define ld long double #define Sort(a) sort(a.begin(),a.end()) #define cSort(a,cmp) sort(a.begin(),a.end(),cmp) #define reSort(a) sort(a.rbegin(), a.rend()) static const ll llMAX = numeric_limits::max(); static const int intMAX = numeric_limits::max(); static const ll llMIN = numeric_limits::min(); static const int intMIN = numeric_limits::min(); static const ll d_5 = 100000; static const ll d9_7 = 1000000007; static const ll d_9 = 1000000000; static const double PI=3.14159265358979323846; template T gcd(T a,T b){ if(a==0){ return b; }else if(b==0){ return a; } while(1) { if(a < b) swap(a, b); if(!b) break; a %= b; } return a; } ll digitpower(ll a,ll b){//aのb乗を計算 if(b==1){ return a; }else if(b==0){ return 1; } int mode=0; if(mode==0){ if(b%2==1){ ll tmp = digitpower(a,(b-1)/2); tmp%=d9_7; tmp*=tmp; tmp%=d9_7; tmp*=a; return (tmp)%d9_7; }else{ ll tmp = digitpower(a,(b)/2); tmp%=d9_7; tmp*=tmp; tmp%=d9_7; return (tmp)%d9_7; } }else{ if(b%2==1){ ll tmp = digitpower(a,(b-1)/2); tmp*=tmp; tmp*=a; return (tmp); }else{ ll tmp = digitpower(a,(b)/2); tmp*=tmp; return (tmp); } } return 0; } template void Printvector(std::vector &a){ int size = a.size(); rep(i,size){ cout< void Printvector(std::vector> &a){ int size = a.size(); rep(i,size){ int size2=a[i].size(); rep(j,size2){ cout< primes(ll n){ unordered_set ret; for(ll i=2;i*i<=n;i++){ if(n%i==0){ ret.insert(i); ret.insert(n/i); } } return ret; } long long modinv(long long a, long long m) {//modの逆元 long long b = m, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u; } vl facs(1000008,-1); ll Factrial(ll num){ if(facs[num]!=-1){ return facs[num]; } if(num==1||num<=0){ return 1; }else if(num<0){ printf("ERROR_minus\n"); return 0; }else{ facs[num]=(num*Factrial(num-1))%d9_7; return facs[num]; } } struct c{ ll a; ll b; }; template class delaySegmentTree{ public: int n; vector nodes; vector delaynodes; //constructor delaySegmentTree(int size,T init){ initialize(size,init); } //関数を定義(minなのかmaxなのかとか) T thisoperator(T a, T b){ return a+b; } void update(int x,T a){//xがindex x+=n-1; nodes[x]+=a; while(x>0){ x=(x-1)/2; nodes[x]=thisoperator(nodes[2*x+1],nodes[2*x+2]); } } void initialize(int inputn,T init){ int k=0; while(inputn>(1< ((1< ((1< 1) { delaynodes[2*k+1] += delaynodes[k] / 2; delaynodes[2*k+2] += delaynodes[k] / 2; } // 伝播が終わったので、自ノードの遅延配列を空にする delaynodes[k] = 0; } } void add(int a, int b, T x, int k=0, int l=0, int r=-1) { if(r < 0) r = n; // k 番目のノードに対して遅延評価を行う eval(k, l, r); // 範囲外なら何もしない if(b <= l || r <= a) return; // 完全に被覆しているならば、遅延配列に値を入れた後に評価 if(a <= l && r <= b) { delaynodes[k] += (r - l) * x; eval(k, l, r); } // そうでないならば、子ノードの値を再帰的に計算して、 // 計算済みの値をもらってくる else { add(a, b, x, 2*k+1, l, (l+r)/2); add(a, b, x, 2*k+2, (l+r)/2, r); nodes[k] = nodes[2*k+1] + nodes[2*k+2]; } } T sec_get(int reql,int reqr,int nowindex=0,int nowl=0,int nowr=-1){ // 最初に呼び出されたときの対象区間は [0, n) //開区間であることに注意 if(nowr < 0) nowr = n; // 要求区間と対象区間が交わらない -> 適当に返す if(nowr <= reql || reqr <= nowl) return 0; //関数が呼び出されるので評価 eval(nowindex,nowl,nowr); // 要求区間が対象区間を完全に被覆 -> 対象区間を答えの計算に使う if(reql <= nowl && nowr <= reqr) return nodes[nowindex]; // 要求区間が対象区間の一部を被覆 -> 子について探索を行う // 左側の子を vl ・ 右側の子を vr としている // 新しい対象区間は、現在の対象区間を半分に割ったもの T val1 = sec_get(reql, reqr, 2*nowindex+1, nowl, (nowl+nowr)/2); T val2 = sec_get(reql, reqr, 2*nowindex+2, (nowl+nowr)/2, nowr); return thisoperator(val1, val2); } void Printn(){ cout<<"Printvector"<right.b; } int main(void){ ll n,q; cin>>n>>q; vl a(n); vl x(q),y(q); vector c(q); rep(i,n)cin>>a[i]; rep(i,n){ cin>>c[i]>>x[i]>>y[i]; if(c[i]=='B'){ y[i]--; } x[i]--; } delaySegmentTree seg1(n,0); delaySegmentTree seg2(n,0); rep(i,q){ seg1.add(x[i],y[i],1); } vl ans(n,0); rep(i,q){ if(c[i]=='B'){ ans[x[i]]+=y[i]*(seg1.sec_get(x[i],x[i]+1)-seg2.sec_get(x[i],x[i]+1)); }else{ seg2.add(x[i],y[i],1); } } rep(i,n){ cout<