Greg and Array

Greg'in N elemanlı bir dizisi ve M tane işlemi var.
Her işlem l, r, d sayılarıyla gösteriliyor.
İşlem ise dizinin l(1 değil, harf olan l). indisinden r. indise kadar olan elemanları d kadar arttırmak.
Greg M tane işlemi bir listeye sırasıyla yazıyor ve ikinci bir işlem biçimi tanımlıyor.
İkinci işlemden de K tane yapacak.
Bu işlem x, y şeklinde gösteriliyor, M işlemlik listedeki x'den y'ye kadar olan işlemleri uygulamamızı sağlıyor.
Greg'in sizden istediği, dizinin K işlemden sonraki hâli.

Girdi Biçimi:

N M K( Hepsinin sınırı 100.000 )
Dizinin N elemanı( Sınır yine 100.000 )
l r d şeklinde M tane işlem( d'nin sınırı 100.000)
x y şeklinde K tane işlem

Çıktı Biçimi:

Tek satırda dizinin son hâli.

Örnek Girdi:

3 3 3
1 2 3
1 2 1
1 3 2
2 3 4
1 2
1 3
2 3

Örnek Çıktı:

9 18 17

________________________________________________________

Link: http://codeforces.com/contest/295/problem/A

________________________________________________________

Çözüm:

Online sorgu içermeyen problemlerde dizide l,r arasını d kadar arttırma işlemini şu şekilde yapabiliriz:
ar[r]+=d;
ar[l-1]-=d;

ar[x] şu demek: x ve solundaki bütün elemanların değerini ar[x] kadar arttırdık.
Diziyi bu şekilde tutarsak en sondan başa doğru her elemanı toplayarak gelince dizinin son halini elde ederiz.

İlk M işlemi bu tarz bir dizi olarak düşünürsek ikinci K işlemi bu M elemanlı dizi üzerinde uygulayabiliriz.
M elemanlı dizinin asıl hâlini bulunca İlk dizimizi de aynı şekilde son hâline getirebiliriz.

Eğer dizideki aralık arttırma işlemleri için Segment Tree kullansaydı problemi online olarak çözmüş olacaktık, fakat zaman karmaşıklığı artacaktı.

________________________________________________________

Çözüm Kodu:

#include <cstdio>
#include <iostream>

#define fi first
#define se second

using namespace std;

typedef pair<int,int> ii;
typedef unsigned long long int ULint;

const int MAXN=100100;

ULint N,M,K;
ULint l[MAXN];
ULint r[MAXN];
ULint t[MAXN];
ULint ar[MAXN];
ULint wr[MAXN];
ULint inc[MAXN];

int main(){

ios_base::sync_with_stdio(false);
cin >> N >> M >> K;

for( int a,i=1 ; i<=N ; i++ ){
cin >> a;
ar[i]+=a;
ar[i-1]-=a;
}

for( int i=1 ; i<=M ; i++ )
cin >> l[i] >> r[i] >> t[i];

for( int a,b,i=1 ; i<=K ; i++ ){
cin >> a >> b;
inc[b]++;
inc[a-1]--;
}

ULint cur=0;

for( int i=M ; i ; i-- ){
cur+=inc[i];
ar[r[i]]+=t[i]*cur;
ar[l[i]-1]-=t[i]*cur;
}

cur=0;

for( int i=N ; i ; i-- ){
cur+=ar[i];
wr[i]=cur;
}

for( int i=1 ; i<=N ; i++ )
cout << wr[i] << ' ';

cout << '\n';
return 0;
}