1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
| #include <bits/stdc++.h>
using namespace std;
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define VI vector<int>
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
template<class T>inline void read(T &x) {
x=0; char ch=getchar(); bool f=0;
for(;ch<'0'||ch>'9';ch=getchar()) f|=(ch=='-');
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+(ch^48);
if(f) x=-x;
}
template<class T,class... V>
inline void read(T &a,V&... b){read(a); read(b...);}
#define CASES int ___;for(read(___);___--;)
mt19937 rnd(random_device{}());
const int N = 5e5+5;
ull ans[N];
#define lc (u<<1)
#define rc (lc|1)
#define ls lc,l,mid
#define rs rc,mid+1,r
ull s1[N<<2],s2[N<<2];
ull t1[N<<2],t2[N<<2];
inline void pushup(int u) {
s1[u] = s1[lc] + s1[rc];
s2[u] = s2[lc] + s2[rc];
}
inline void pushtag1(int u,int len,ull x) {
t1[u] += x;
s1[u] += x * len;
}
inline void pushtag2(int u,int len,ull x) {
t2[u] += x;
s2[u] += x * len;
}
inline void pushdown(int u,int l,int r) {
int mid = (l+r)>>1;
if(t1[u]) {
pushtag1(lc,mid-l+1,t1[u]);
pushtag1(rc,r-mid,t1[u]);
t1[u] = 0;
}
if(t2[u]) {
pushtag2(lc,mid-l+1,t2[u]);
pushtag2(rc,r-mid,t2[u]);
t2[u] = 0;
}
}
ull ask(int u,int l,int r,int L,int R,ull x) {
if(L<=l&&r<=R)
return s1[u] * x - s2[u];
pushdown(u,l,r);
int mid = (l+r)>>1;
ull ans = 0;
if(L<=mid)
ans += ask(ls,L,R,x);
if(mid<R)
ans += ask(rs,L,R,x);
return ans;
}
void add(int u,int l,int r,int L,int R,ull w,int p) {
if(L<=l&&r<=R) {
pushtag1(u,r-l+1,w);
pushtag2(u,r-l+1,1ull * w * p);
return;
}
pushdown(u,l,r);
int mid = (l+r)>>1;
if(L <= mid)
add(ls,L,R,w,p);
if(mid<R)
add(rs,L,R,w,p);
pushup(u);
}
struct node{
int l,r,c;
node() {}
node(int _l,int _r,int _c) {
l = _l; r = _r; c = _c;
}
friend inline bool operator<(const node &A,const node &B) {
if(A.l != B.l)
return A.l<B.l;
return A.r<B.r;
}
};
set<node> s;
int n,q;
int main() {
read(n,q);
fo(i,1,n) {
int x;
read(x);
s.insert({i,i,x});
}
s.insert({n+1,n+1,0});
fo(i,1,q) {
int opt,l,r; ull w;
read(opt,l,r,w);
if(opt == 1) {
auto it = s.upper_bound({l,n+1,0});
it --;
auto now = *it;
s.erase(it);
if(now.l != l)
s.insert({now.l,l-1,now.c});
s.insert({l,now.r,now.c});
it = s.upper_bound({r,n+1,0});
it --;
now = *it;
s.erase(it);
if(now.r != r)
s.insert({r+1,now.r,now.c});
s.insert({now.l,r,now.c});
auto it2 = it;
for(it = it2 = s.lower_bound({l,0,0});it != s.end() && it -> r <= r; it2++,s.erase(it),it = it2) {
now = *it;
ans[now.c] += ask(1,1,n,now.l,now.r,i-1);
}
s.insert({l,r,w});
ans[w] -= ask(1,1,n,l,r,i-1);
}
else
add(1,1,n,l,r,w,i-1);
}
for(auto [l,r,c]:s)
ans[c] += ask(1,1,n,l,r,q);
fo(i,1,n) {
printf("%llu ",ans[i]);
}
return 0;
}
|