#include "meetings.h"
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=750005;
const int mxM=2200005;
const int mxK=61;
const int MOD=1e9+7;
const ll INF=1e18;
int N, Q;
ll H[mxN];
pii qry[mxN];
ll l[mxN], r[mxN];
ll ldp[mxN], rdp[mxN]; // ldp[i] : [l[i]+1, i]에서 시작점을 선택해서 [l[i]+1, i-1]에 대한 최소 비용
ll rval[mxN], lval[mxN];
int ldep[mxN], rdep[mxN];
int dl[mxN], dr[mxN], mh[mxN];
pii lrng[mxN], rrng[mxN];
pll rline[mxN], lline[mxN];
ll ans[mxN];
void init(vector <int> h, vector <int> L, vector <int> R){
N=h.size();
for(int i=0;i<N;i++) H[i]=h[i];
Q=L.size();
for(int i=0;i<Q;i++) qry[i]=pii(L[i], R[i]);
}
void input(){
cin >> N >> Q;
for(int i=0;i<N;i++) cin >> H[i];
for(int i=0;i<Q;i++) cin >> qry[i].fi >> qry[i].se;
}
void make_cartesian_tree(){ // 두 산의 높이가 같으면 오른쪽에 있는 산의 높이가 더 높다
stack <int> stk;
for(int i=0;i<N;i++){
while(stk.size() && H[stk.top()]<=H[i]) stk.pop();
if(stk.size()) l[i]=stk.top();
else l[i]=-1;
stk.push(i);
}
while(stk.size()) stk.pop();
for(int i=N-1;i>=0;i--){
while(stk.size() && H[stk.top()]<H[i]) stk.pop();
if(stk.size()) r[i]=stk.top();
else r[i]=-1;
stk.push(i);
}
//dep
for(int i=0;i<N;i++){
if(l[i]==-1) ldep[i]=1;
else ldep[i]=ldep[l[i]]+1;
}
for(int i=N-1;i>=0;i--){
if(r[i]==-1) rdep[i]=1;
else rdep[i]=rdep[r[i]]+1;
}
//rng
for(int i=0;i<N;i++){
if(l[i]==-1) rrng[i]=pii(0, i);
else rrng[i]=pii(l[i]+1, i);
if(r[i]==-1) lrng[i]=pii(i, N-1);
else lrng[i]=pii(i, r[i]-1);
}
}
void make_dp(){
//길이 2짜리 segment의 비용은 0이다
vector <pii> v;
for(int i=0;i<N;i++){
if(l[i]!=-1 && r[i]!=-1) v.emplace_back(max(i-l[i], r[i]-i), i);
}
sort(all(v));
for(auto [d, i] : v){
if(H[l[i]]<=H[r[i]]){
int now=l[i];
rdp[now]=min(rdp[i]+(i-l[i])*H[i], ldp[i]+(r[i]-i)*H[i]);
}
else{
int now=r[i];
ldp[now]=min(rdp[i]+(i-l[i])*H[i], ldp[i]+(r[i]-i)*H[i]);
}
}
}
void make_lrval(){
for(int i=N-1;i>=0;i--){
if(r[i]==-1) rval[i]=(N-i)*H[i];
else rval[i]=(r[i]-i)*H[i]+rval[r[i]];
}
for(int i=0;i<N;i++){
if(l[i]==-1) lval[i]=(i+1)*H[i];
else lval[i]=(i-l[i])*H[i]+lval[l[i]];
}
}
void make_sps(){
vector <vector <int>> spsl(N, vector<int>(20)), spsr(N, vector<int>(20));
for(int j=0;j<N;j++){
spsl[j][0]=l[j];
spsr[j][0]=r[j];
}
for(int i=1;i<20;i++){
for(int j=0;j<N;j++){
if(spsl[j][i-1]==-1 || spsl[spsl[j][i-1]][i-1]==-1) spsl[j][i]=-1;
else spsl[j][i]=spsl[spsl[j][i-1]][i-1];
if(spsr[j][i-1]==-1 || spsr[spsr[j][i-1]][i-1]==-1) spsr[j][i]=-1;
else spsr[j][i]=spsr[spsr[j][i-1]][i-1];
}
}
for(int i=0;i<Q;i++){
auto [s, e]=qry[i];
int now=s;
for(int j=19;j>=0;j--){
if(spsr[now][j]!=-1 && spsr[now][j]<=e) dr[i]+=(1<<j), now=spsr[now][j];
}
now=e;
for(int j=19;j>=0;j--){
if(spsl[now][j]!=-1 && spsl[now][j]>=s) dl[i]+=(1<<j), now=spsl[now][j];
}
mh[i]=now;
}
spsl.clear(); spsr.clear();
spsl.shrink_to_fit(); spsr.shrink_to_fit();
}
void make_line(){
//rdp[now]+(now-s+1)*H[now]+rval[r[now]]-rval[hmax]+(e-hmax+1)*H[hmax] : y = -H[now]*x + rdp[now]+(now+1)*H[now]+rval[r[now]]에 -rval[hmax]+(e-hmax+1)*H[hmax]를 더한다
//ldp[now]+(e-now+1)*H[now]+lval[l[now]]-lval[hmax]+(hmax-s+1)*H[hmax] : y = H[now]*x + ldp[now]+(-now+1)*H[now]+lval[l[now]]에 -lval[hmax]+(hmax-s+1)*H[hmax]를 더한다
for(int i=0;i<N;i++){
if(l[i]!=-1) lline[i]=pll(H[i], ldp[i]+(-i+1)*H[i]+lval[l[i]]);
else lline[i]=pll();
if(r[i]!=-1) rline[i]=pll(-H[i], rdp[i]+(i+1)*H[i]+rval[r[i]]);
else rline[i]=pll();
}
}
struct Node{
int val;
int llink, rlink;
Node() : val(), llink(), rlink() {}
Node(int val, int llink, int rlink) : val(val), llink(llink), rlink(rlink) {}
};
struct event{
int idx;
int e1, e2;
event() : idx(), e1(), e2() {}
event(int idx, int e1, int e2) : idx(idx), e1(e1), e2(e2) {}
};
char swp_typ;
vector <Node> seg[4*mxN];
pii sgrng[4*mxN];
vector <event> swp[mxN], imswp; // imswp means immediate swap, where intersection <= x
int now_x;
void seg_init(int idx, int s, int e){
sgrng[idx]=pii(s, e);
seg[idx].resize(e-s+3);
seg[idx][0].rlink=e-s+2;
for(int i=1;i<=e-s+1;i++) seg[idx][i].llink=seg[idx][i].rlink=-1;
seg[idx][e-s+2].llink=0;
if(s==e) return;
int mid=(s+e)/2;
seg_init(2*idx, s, mid);
seg_init(2*idx+1, mid+1, e);
}
ll intersection(int e1, int e2){
pll c1, c2;
if(swp_typ=='r') c1=rline[e1], c2=rline[e2];
else c1=lline[e1], c2=lline[e2];
if(swp_typ=='r') assert(c1.fi<=c2.fi);
else assert(c1.fi>=c2.fi);
if(c1.fi==c2.fi){
if(c1.se<=c2.se) return (swp_typ=='r' ? 0 : N);
else return (swp_typ=='r' ? N+1 : -1);
}
if(swp_typ=='r'){
pll c3=pll(c1.fi-c2.fi, c1.se-c2.se);
return (c3.se%(-c3.fi)==0 ? c3.se/(-c3.fi) : c3.se/(-c3.fi)+1);
}
else{
pll c3=pll(c2.fi-c1.fi, c2.se-c1.se);
return (c3.se%(-c3.fi)==0 ? c3.se/(-c3.fi) : c3.se/(-c3.fi)-1);
}
} // e1이 e2보다 작아지는 순간을 리턴
void add_swp(int idx, int ln, int rn){
ll itx=intersection(seg[idx][ln].val, seg[idx][rn].val);
if(swp_typ=='r'){
if(itx<=now_x) imswp.emplace_back(idx, ln, rn);
else if(itx<=N-1) swp[itx].emplace_back(idx, ln, rn);
}
else{
if(itx>=now_x) imswp.emplace_back(idx, ln, rn);
else if(itx>=0) swp[itx].emplace_back(idx, ln, rn);
}
}
void add_node(int idx, int ln, int now, int rn, int x){
seg[idx][now].rlink=rn;
seg[idx][now].llink=ln;
seg[idx][ln].rlink=now;
seg[idx][rn].llink=now;
seg[idx][now].val=x;
if(ln!=0) add_swp(idx, ln, x);
if(rn!=seg[idx].size()-1) add_swp(idx, x, rn);
}
void del_node(int idx, int now){
int ln=seg[idx][now].llink, rn=seg[idx][now].rlink;
seg[idx][ln].rlink=rn;
seg[idx][rn].llink=ln;
seg[idx][now].llink=seg[idx][now].rlink=seg[idx][now].val=-1;
if(ln!=0 && rn!=seg[idx].size()-1) add_swp(idx, ln, rn);
}
void add(int idx, int s, int e, int pos, int x){
int rn=seg[idx].size()-1, ln=seg[idx][rn].llink;
add_node(idx, ln, pos-s+1, rn, x);
if(s==e) return;
int mid=(s+e)/2;
if(pos<=mid) add(2*idx, s, mid, pos, x);
else add(2*idx+1, mid+1, e, pos, x);
}
void swap_f(event t){
auto [idx, e1, e2]=t;
int s=sgrng[idx].fi;
int idx1=(swp_typ=='r' ? rdep[e1] : ldep[e1])-s+1, idx2=(swp_typ=='r' ? rdep[e2] : ldep[e2])-s+1;
if(seg[idx][idx1].rlink==idx2 && seg[idx][idx2].llink==idx1 && seg[idx][idx1].val==e1 && seg[idx][idx2].val==e2){
del_node(idx, idx1);
}
}
ll seg_solv(int idx, int s1, int e1, int s2, int e2, ll x){
if(s2>e1 || s1>e2) return INF;
if(s2<=s1 && e1<=e2){
int bk=seg[idx].back().llink;
if(bk==0) return INF;
pll ln=(swp_typ=='r' ? rline[seg[idx][bk].val] : lline[seg[idx][bk].val]);
return ln.fi*x+ln.se;
}
int mid=(s1+e1)/2;
return min(seg_solv(2*idx, s1, mid, s2, e2, x), seg_solv(2*idx+1, mid+1, e1, s2, e2, x));
}
void del(int idx, int s, int e, int pos, int x){
int bk=seg[idx].back().llink;
if(seg[idx][bk].val==x){
del_node(idx, bk);
}
if(s==e) return;
int mid=(s+e)/2;
if(pos<=mid) del(2*idx, s, mid, pos, x);
else del(2*idx+1, mid+1, e, pos, x);
}
vector <int> ppct[mxN]; // i번 직선을 push하면 i, pop하면 -i-1
vector <int> qct[mxN];
void init_sweep(){
for(int i=0;i<4*mxN;i++) seg[i].clear(), sgrng[i]=pii();
for(int i=0;i<mxN;i++) swp[i].clear();
imswp.clear();
now_x=0;
for(int i=0;i<mxN;i++) ppct[i].clear(), qct[i].clear();
seg_init(1, 1, N);
}
void solv_query(){
for(int i=0;i<Q;i++) ans[i]=INF;
seg_init(1, 1, N);
//가장 높은 곳에서 시작
for(int i=0;i<Q;i++) ans[i]=min(ans[i], (qry[i].se-qry[i].fi+1)*H[mh[i]]);
swp_typ='r';
//dpr에 대해서 segment tree sweeping
for(int i=N-1;i>=0;i--){ // 깊이가 낮은 것부터 push -> i--
if(r[i]==-1) continue;
ppct[rrng[i].fi].push_back(i);
}
// i에 대해서 push -> 쿼리 시행 -> i가 끝나면 i를 pop
for(int i=0;i<Q;i++) qct[qry[i].fi].push_back(i);
for(int i=0;i<N;i++){
now_x=i;
//add element
for(int x : ppct[i]){ // add element
add(1, 1, N, rdep[x], x);
}
//maintain list
while(swp[i].size() || imswp.size()){
if(swp[i].size()){
event t=swp[i].back();
swp[i].pop_back();
swap_f(t);
}
else{
event t=imswp.back();
imswp.pop_back();
swap_f(t);
}
}
//solve queries
for(int x : qct[i]){
int e=qry[x].se;
int hmax=mh[x];
if(dr[x]>=1) ans[x]=min(ans[x], seg_solv(1, 1, N, rdep[i], rdep[i]+dr[x]-1, i)-rval[hmax]+(e-hmax+1)*H[hmax]);
}
//pop
del(1, 1, N, rdep[i], i);
}
init_sweep();
swp_typ='l';
//dpl에 대해서 segment tree sweeping
for(int i=0;i<N;i++){ // 깊이가 낮은 것부터 push -> i++
if(l[i]==-1) continue;
ppct[lrng[i].se].push_back(i);
}
// i에 대해서 push -> 쿼리 시행 -> i가 끝나면 i를 pop
for(int i=0;i<Q;i++) qct[qry[i].se].push_back(i);
for(int i=N-1;i>=0;i--){
now_x=i;
//add element
for(int x : ppct[i]){ // add element
add(1, 1, N, ldep[x], x);
}
//maintain list
while(swp[i].size() || imswp.size()){
if(swp[i].size()){
event t=swp[i].back();
swp[i].pop_back();
swap_f(t);
}
else{
event t=imswp.back();
imswp.pop_back();
swap_f(t);
}
}
//solve queries
for(int x : qct[i]){
int s=qry[x].fi;
int hmax=mh[x];
if(dl[x]>=1) ans[x]=min(ans[x], seg_solv(1, 1, N, ldep[i], ldep[i]+dl[x]-1, i)-lval[hmax]+(hmax-s+1)*H[hmax]);
}
//pop
del(1, 1, N, ldep[i], i);
}
//rdp[now]+(now-s+1)*H[now]+rval[r[now]]-rval[hmax]+(e-hmax+1)*H[hmax] : y = -H[now]*x + rdp[now]+(now+1)*H[now]+rval[r[now]]에 -rval[hmax]+(e-hmax+1)*H[hmax]를 더한다
//ldp[now]+(e-now+1)*H[now]+lval[l[now]]-lval[hmax]+(hmax-s+1)*H[hmax] : y = H[now]*x + ldp[now]+(-now+1)*H[now]+lval[l[now]]에 -lval[hmax]+(hmax-s+1)*H[hmax]를 더한다
/*
for(int i=0;i<Q;i++){
auto [s, e]=qry[i];
int now=s;
int hmax=mh[i];
while(r[now]!=-1 && r[now]<=e){
ans[i]=min(ans[i], rdp[now]+(now-s+1)*H[now]+rval[r[now]]-rval[hmax]+(e-hmax+1)*H[hmax]);
now=r[now];
}
ans[i]=min(ans[i], H[now]*(e-s+1));
now=e;
while(l[now]!=-1 && l[now]>=s){
ans[i]=min(ans[i], ldp[now]+(e-now+1)*H[now]+lval[l[now]]-lval[hmax]+(hmax-s+1)*H[hmax]);
now=l[now];
}
}
*/
//for(int i=0;i<Q;i++) cout << ans[i] << '\n';
}
void solv(){
make_cartesian_tree();
make_dp();
make_lrval();
make_sps();
make_line();
solv_query();
}
vector<ll> minimum_costs(vector<int> h, vector<int> L, vector<int> R) {
init(h, L, R);
solv();
vector <ll> C(Q);
for(int j=0;j<Q;j++) C[j]=ans[j];
return C;
}
/*
int main()
{
gibon
input();
solv();
}
*/
Compilation message
meetings.cpp: In function 'void add_node(int, int, int, int, int)':
meetings.cpp:208:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
208 | if(rn!=seg[idx].size()-1) add_swp(idx, x, rn);
| ~~^~~~~~~~~~~~~~~~~~~
meetings.cpp: In function 'void del_node(int, int)':
meetings.cpp:215:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
215 | if(ln!=0 && rn!=seg[idx].size()-1) add_swp(idx, ln, rn);
| ~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
147284 KB |
Output is correct |
| 2 |
Runtime error |
134 ms |
253536 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
147284 KB |
Output is correct |
| 2 |
Runtime error |
134 ms |
253536 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
147284 KB |
Output is correct |
| 2 |
Runtime error |
153 ms |
264040 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
147284 KB |
Output is correct |
| 2 |
Runtime error |
153 ms |
264040 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
147284 KB |
Output is correct |
| 2 |
Runtime error |
134 ms |
253536 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
