| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 585126 | GioChkhaidze | Progression (NOI20_progression) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
#define lf (h << 1)
#define mf ((l + r) >> 1)
#define rf ((h << 1) | 1)
#define tree int h, int l, int r
#define left lf, l, mf
#define right rf, mf + 1, r
#define ll long long
#define f first
#define s second
using namespace std;
const int N = 3e5 + 5;
ll vl;
int n, m, q, L, R, S, C, id, a[N], b[N];
struct node {
int ans;
int len;
int fr;
int ls;
int pr;
int sf;
int add;
ll sum;
node () {
sum = 0;
ans = 0;
len = 0;
add = 0;
fr = 0;
ls = 0;
pr = 0;
sf = 0;
}
};
node v[4 * N], bs;
node mrg(node a, node b) {
node c;
c.len = a.len + b.len;
c.fr = a.fr, c.ls = b.ls;
c.pr = a.pr, c.sf = b.sf;
c.ans = max(a.ans, b.ans);
c.sum = a.sum + b.sum;
if (a.ls == b.fr) {
if (a.len == c.pr) c.pr += b.pr;
if (b.len == c.sf) c.sf += a.sf;
c.ans = max(c.ans, a.sf + b.pr);
}
return c;
}
void shift(tree) {
if (v[h].flag) {
v[lf].fr = v[h].toggle;
v[lf].ls = v[h].toggle;
v[rf].fr = v[h].toggle;
v[rf].ls = v[h].toggle;
//v[lf].add += v[h].toggle;
//v[rf].add += v[h].toggle;
v[lf].sum = (mf - l + 1) * v[h].toggle;
v[rf].sum = (r - mf) * v[h].toggle;
v[h].toggle = 0;
v[h].flag = 0;
}
if (v[h].add) {
v[lf].fr += v[h].add;
v[lf].ls += v[h].add;
v[rf].fr += v[h].add;
v[rf].ls += v[h].add;
v[lf].add += v[h].add;
v[rf].add += v[h].add;
v[lf].sum += (mf - l + 1) * v[h].add;
v[rf].sum += (r - mf) * v[h].add;
v[h].add = 0;
}
}
void build(tree) {
if (l == r) {
v[h].pr = v[h].sf = v[h].len = v[h].ans = 1;
v[h].fr = v[h].ls = v[h].sum = b[l];
return ;
}
build(left), build(right);
v[h] = mrg(v[lf], v[rf]);
}
void up_range(tree) {
if (R < l || r < L) return ;
if (L <= l && r <= R) {
v[h].fr += C, v[h].ls += C;
v[h].sum += (r - l + 1) * C;
if (v[h].flag) {
v[h].toggle += C;
v[h].add = 0;
}
else {
v[h].add += C;
}
return;
}
shift(h, l, r);
up_range(left);
up_range(right);
v[h] = mrg(v[lf], v[rf]);
}
void up_dot(tree) {
if (l == r) {
v[h].pr = v[h].sf = v[h].len = v[h].ans = 1;
v[h].fr = v[h].ls = v[h].sum = b[l];
return;
}
shift(h, l, r);
if (id <= mf) {
up_dot(left);
}
else {
up_dot(right);
}
v[h] = mrg(v[lf], v[rf]);
}
void up_to_range(tree) {
if (r < L || R < l) return ;
if (L <= l && r <= R) {
v[h].toggle = v[h].fr = v[h].ls = C;
v[h].sum = (r - l + 1) * C;
v[h].flag = true;
v[h].add = 0;
return;
}
shift(h, l, r);
up_to_range(left);
up_to_range(right);
v[h] = mrg(v[lf], v[rf]);
}
ll get_avl(tree) {
if (r < L || R < l) return 0;
if (L <= l && r <= R) return v[h].sum;
return get_avl(left) + get_avl(right);
}
ll get_vl(tree) {
if (l == r) return v[h].fr;
shift(h, l, r);
if (id <= mf)
return get_vl(left);
return get_vl(right);
}
node get(tree) {
if (r < L || R < l) return bs;
if (L <= l && r <= R) return v[h];
shift(h, l, r);
return mrg(get(left), get(right));
}
void change_id(int x, int vl) {
a[x] = vl;
if (1 < x) {
id = x - 1;
b[id] = a[id + 1] - a[id];
up_dot(1, 1, m);
}
if (x < n) {
id = x;
b[id] = a[id + 1] - a[id];
up_dot(1, 1, m);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
if (1 < i) {
b[i - 1] = a[i] - a[i - 1];
}
}
m = n + 1;
build(1, 1, m);
/*cout << "\n";
for (int j = 1; j < n; ++j) {
id = j; cout << get_vl(1, 1, m) << " ";
}
cout << "\n";*/
for (int i = 1; i <= q; ++i) {
int tp;
cin >> tp >> L >> R;
if (tp == 1) {
cin >> S >> C;
if (L == 1) a[1] += S;
--R, up_range(1, 1, m), ++R;
if (1 < L) {
id = L - 1;
vl = get_vl(1, 1, m);
b[id] = vl + S;
up_dot(1, 1, m);
}
if (R < n) {
id = R;
vl = get_vl(1 , 1, m);
b[id] = vl - (S + (R - L) * C);
up_dot(1, 1, m);
}
/*
cout << "\n";
for (int j = 1; j < n; ++j)
id = j, cout << get_vl(1, 1, m) << " ";
cout << "\n";
a[L - 1] += S
b[L - 1] = a[L] - a[L - 1]
b[R] = a[R + 1] - a[R]
*/
}
else
if (tp == 2) {
cin >> S >> C;
if (L == 1) a[1] = S;
up_to_range(1, 1, m);
ll vl = S;
for (int j = L; j <= R; ++j) {
change_id(j, vl);
vl += C;
}
}
else
if (tp == 3) {
--R; cout << get(1 , 1, m).ans + 1 << "\n";
}
}
}
/*
S + (i − L) × C.
S + i * C - L * C
(S - L * C) + i * C
b[i] = a[i + 1] - a[i]
QUERY ADD
QUERY PUT
QUERY
*/