/** - dwuy -
／＞ フ
| _ _|
／`ミ _x ノ
/ |
/ ヽ ?
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
**/
#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "test"
using namespace std;
typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;
const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 100005;
int n;
int a[MX];
struct Dwuy{
int n;
vector<ll> tree;
Dwuy(int n = 0) : n(n), tree(n + 5, 0) {}
void update(int idx, ll val){
for(; idx<=n; idx+=-idx&idx) tree[idx] += val;
}
ll gsum(int idx){
ll res = 0;
for(; idx; idx-=-idx&idx) res += tree[idx];
return res;
}
int gsum(int l, int r){
return min(1LL*INF, gsum(r) - gsum(l - 1));
}
} dwuy;
struct Taiki{
int n;
vector<int> tree;
Taiki(int n = 0) : n(n), tree(n<<2|3, 0) {}
void update(int pos, int val){
int id = 1;
for(int lo=1, hi=n; lo<hi;){
int mid = (lo + hi)>>1;
if(pos <= mid) hi = mid, id = id<<1;
else lo = mid + 1, id = id<<1|1;
}
tree[id] = val;
for(id>>=1; id; id>>=1) tree[id] = max(tree[id<<1], tree[id<<1|1]);
}
int lmx(int l, int r, int id, const int &lim, const int &pos, const int &val){
if(l > pos || tree[id] <= val) return l - 1;
if(r < lim) return lim - 1;
if(l == r) return l;
int mid = (l + r)>>1;
int p = lmx(mid + 1, r, id<<1|1, lim, pos, val);
return p != mid? p : lmx(l, mid, id<<1, lim, pos, val);
}
int lmx(int lim, int pos, int val){
return lmx(1, n, 1, lim, pos, val);
}
int rmx(int l, int r, int id, const int &lim, const int &pos, const int &val){
if(r < pos || tree[id] <= val) return r + 1;
if(l > lim) return lim + 1;
if(l == r) return l;
int mid = (l + r)>>1;
int p = rmx(l, mid, id<<1, lim, pos, val);
return p != mid + 1? p : rmx(mid + 1, r, id<<1|1, lim, pos, val);
}
int rmx(int lim, int pos, int val){
return rmx(1, n, 1, lim, pos, val);
}
} taiki;
struct Cnode{
vector<pii> pl, pr;
int l, r;
/// pl: {pl[i], ...} -> pr[i] = R;
/// pr: {pr[i], ...} -> pl[i] = L;
Cnode() : pl({}), pr({}), l(0), r(0) {}
};
struct Chii{
int n;
vector<Cnode> tree;
Chii(int n = 0) : n(n), tree(n<<2|3, Cnode()) {}
void build(int l, int r, int id){
tree[id].l = l;
tree[id].r = r;
if(l == r) return;
int mid = (l + r)>>1;
build(l, mid, id<<1);
build(mid + 1, r, id<<1|1);
}
void build(){
build(1, n, 1);
}
Cnode combine(Cnode a, Cnode b){
Cnode res;
res.l = a.l;
res.r = b.r;
if(a.pl.size() == 0 || b.pl.size() == 0) return res;
res.pr = a.pr;
res.pr.pop_back();
res.pl = b.pl;
res.pl.pop_back();
pii extrLeft = {-1, -1};
pii extrRight = {-1, -1};
int bsum = dwuy.gsum(b.l, b.pr[0].fi);
for(int i=0, j=b.l - 1; i<len(b.pr);){
while(j >= a.l){
int p = taiki.lmx(a.l, j, bsum);
p = max(p, a.l - 1);
if(p != j){
bsum += dwuy.gsum(p + 1, j);
j = p;
while(i + 1 < len(b.pr) && bsum >= ::a[b.pr[i].fi + 1]){
b.pr[i + 1].se += b.pr[i].se;
bsum += dwuy.gsum(b.pr[i].fi + 1, b.pr[i + 1].fi);
i++;
}
}
else break;
}
if(j < a.l) res.pr.push_back(b.pr[i]);
i++;
if(i == len(b.pr)) extrLeft = {j + 1, b.pr.back().se};
else bsum += dwuy.gsum(b.pr[i - 1].fi + 1, b.pr[i].fi);
while(i + 1 < len(b.pr) && bsum >= ::a[b.pr[i].fi + 1]){
b.pr[i + 1].se += b.pr[i].se;
bsum += dwuy.gsum(b.pr[i].fi + 1, b.pr[i + 1].fi);
i++;
}
}
bsum = dwuy.gsum(a.pl[0].fi, a.r);
for(int i=0, j=a.r + 1; i<len(a.pl); ){
while(j <= b.r){
int p = taiki.rmx(b.r, j, bsum);
p = min(p, b.r + 1);
if(p != j){
bsum += dwuy.gsum(j, p - 1);
j = p;
while(i + 1 <len(a.pl) && bsum >= ::a[a.pl[i].fi - 1]){
a.pl[i + 1].se += a.pl[i].se;
bsum += dwuy.gsum(a.pl[i + 1].fi, a.pl[i].fi - 1);
i++;
}
}
else break;
}
if(j > b.r) res.pl.push_back(a.pl[i]);
i++;
if(i == len(a.pl)) extrRight = {j - 1, a.pl.back().se};
else bsum += dwuy.gsum(a.pl[i].fi, a.pl[i - 1].fi - 1);
while(i + 1 <len(a.pl) && bsum >= ::a[a.pl[i].fi - 1]){
a.pl[i + 1].se += a.pl[i].se;
bsum += dwuy.gsum(a.pl[i + 1].fi, a.pl[i].fi - 1);
i++;
}
}
bool flag = 1;
for(pii &p: res.pr) if(p.fi == extrRight.fi){
p.se += extrRight.se;
flag = 0;
}
if(flag){
res.pr.push_back(extrRight);
int i = len(res.pr) - 1;
while(i > 0 && res.pr[i].fi < res.pr[i - 1].fi){
swap(res.pr[i], res.pr[i - 1]);
i--;
}
}
flag = 1;
for(pii &p: res.pl) if(p.fi == extrLeft.fi){
p.se += extrLeft.se;
flag = 0;
}
if(flag){
res.pl.push_back(extrLeft);
int i = len(res.pl) - 1;
while(i > 0 && res.pl[i].fi > res.pl[i - 1].fi){
swap(res.pl[i], res.pl[i - 1]);
i--;
}
}
return res;
}
void update(int pos){
int id = 1;
for(int lo=1, hi=n; lo<hi;){
int mid = (lo + hi)>>1;
if(pos <= mid) hi = mid, id = id<<1;
else lo = mid + 1, id = id<<1|1;
}
tree[id].pl = {{pos, 1}};
tree[id].pr = {{pos, 1}};
for(id>>=1; id; id>>=1) tree[id] = combine(tree[id<<1], tree[id<<1|1]);
}
Cnode get(int l, int r, int id, const int &u, const int &v){
if(l >= u && r <= v) return tree[id];
int mid = (l + r)>>1;
if(mid >= v) return get(l, mid, id<<1, u, v);
if(mid < u) return get(mid + 1, r, id<<1|1, u, v);
return combine(get(l, mid, id<<1, u, v), get(mid + 1, r, id<<1|1, u, v));
}
int get(int l, int r){
Cnode res = get(1, n, 1, l, r);
return res.pl.back().se;
}
void show(int l, int r, int id){
cout << " === " << l << ' ' << r << " = " << id << endl;
cout << "pl: "; for(pii p: tree[id].pl) cout << "{" << p.fi << ", " << p.se << "} ";
cout << endl;
cout << "pr: "; for(pii p: tree[id].pr) cout << "{" << p.fi << ", " << p.se << "} ";
cout << endl << endl;
if(l == r) return;
int mid = (l + r)>>1;
show(l, mid, id<<1);
show(mid + 1, r, id<<1|1);
}
void show(){
show(1, n, 1);
}
} chii;
int32_t main(){
fastIO;
//file(TASK);
cin >> n;
for(int i=1; i<=n; i++) cin >> a[i];
dwuy = Dwuy(n);
taiki = Taiki(n);
chii = Chii(n);
chii.build();
for(int i=1; i<=n; i++) dwuy.update(i, a[i]);
for(int i=1; i<=n; i++) taiki.update(i, a[i]);
for(int i=1; i<=n; i++) chii.update(i);
// chii.show();
int q; cin >> q;
while(q--){
int oper, u, v;
cin >> oper >> u >> v;
if(oper == 1){
dwuy.update(u, -a[u] + v);
a[u] = v;
taiki.update(u, a[u]);
chii.update(u);
}
else{
cout << chii.get(u, v) << endl;
}
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Incorrect |
5 ms |
592 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
165 ms |
39972 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Incorrect |
5 ms |
592 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
165 ms |
39972 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
165 ms |
39972 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Incorrect |
5 ms |
592 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
