#include "towers.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <utility>
#include <tuple>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG
const int INF = (int)1e9 + 7;
using namespace std;
int N, M;
vector<int> H;
vector<int> P;
vector<int> ind;
vector<pii> indm;
vector<pii> LD, RD;
vector<int> GD;
vector<int> DS;
vector<int> DH;
vector<int> Lroot, Rroot, LDroot, RDroot;
int qry(int l, int r)
{
int ret = 0;
for(int x = l + N, y = r + N; x != y; x >>= 1, y >>= 1)
{
if(x & 1) ret = max(ret, ind[x++]);
if(y & 1) ret = max(ret, ind[--y]);
}
return ret;
}
int qrym(int l, int r)
{
pii ret = {INF, INF};
for(int x = l + N, y = r + N; x != y; x >>= 1, y >>= 1)
{
if(x & 1) ret = min(ret, indm[x++]);
if(y & 1) ret = min(ret, indm[--y]);
}
return ret.ss;
}
struct SEG
{
struct Node
{
int x;
int l, r;
Node(void) : x(0), l(-1), r(-1) {}
}nd[40404040];
int cnt = 0;
int init(int s, int e, const vector<int> &V)
{
int ret = cnt++;
if(s + 1 == e)
{
nd[ret].x = V[s];
return ret;
}
int mid = s + e >> 1;
nd[ret].l = init(s, mid, V);
nd[ret].r = init(mid, e, V);
nd[ret].x = nd[nd[ret].l].x + nd[nd[ret].r].x;
return ret;
}
int upd(int ind, int s, int e, int x, int v)
{
int ret = cnt++;
nd[ret] = nd[ind];
if(s + 1 == e)
{
nd[ret].x += v;
return ret;
}
int mid = s + e >> 1;
if(x < mid) nd[ret].l = upd(nd[ret].l, s, mid, x, v);
else nd[ret].r = upd(nd[ret].r, mid, e, x, v);
nd[ret].x = nd[nd[ret].l].x + nd[nd[ret].r].x;
return ret;
}
int qry(int ind, int s, int e, int l, int r)
{
if(e <= l || r <= s) return 0;
if(l <= s && e <= r) return nd[ind].x;
int mid = s + e >> 1;
return qry(nd[ind].l, s, mid, l, r) + qry(nd[ind].r, mid, e, l, r);
}
}seg;
void init(int _N, vector<int> _H)
{
N = _N;
H = _H;
for(int i = 0; i < N; ++i) P.push_back(i);
sort(P.begin(), P.end(), [](int x, int y){return H[x] < H[y];});
ind.resize(2 * N);
for(int i = 0; i < N; ++i) ind[i + N] = H[i];
for(int i = N - 1; i >= 1; --i) ind[i] = max(ind[i << 1], ind[i << 1 | 1]);
indm.resize(2 * N);
for(int i = 0; i < N; ++i) indm[i + N] = { H[i], i };
for(int i = N - 1; i >= 1; --i) indm[i] = min(indm[i << 1], indm[i << 1 | 1]);
set<int> S;
LD.resize(N);
RD.resize(N);
GD.resize(N);
for(int i : P)
{
auto it = S.lower_bound(i);
int l = (it == S.begin() ? -1 : *prev(it));
int r = (it == S.end() ? N : *it);
LD[i] = { l, qry(l + 1, i + 1) - H[i] };
RD[i] = { r, qry(i, r) - H[i] };
GD[i] = min(LD[i].ss, RD[i].ss);
DH.push_back(LD[i].ss);
DH.push_back(RD[i].ss);
S.insert(i);
}
sort(DH.begin(), DH.end());
DH.resize(unique(DH.begin(), DH.end()) - DH.begin());
M = DH.size();
for(int i = 0; i < N; ++i)
{
LD[i].ss = lower_bound(DH.begin(), DH.end(), LD[i].ss) - DH.begin();
RD[i].ss = lower_bound(DH.begin(), DH.end(), RD[i].ss) - DH.begin();
GD[i] = lower_bound(DH.begin(), DH.end(), GD[i]) - DH.begin();
DS.push_back(GD[i]);
}
sort(DS.begin(), DS.end());
Lroot.resize(N + 1);
Rroot.resize(N + 1);
vector<int> tmp(M);
vector<int> ls[N + 1];
for(int i = 0; i < N; ++i) ++tmp[GD[i]], ls[LD[i].ff + 1].push_back(i);
Lroot[0] = Rroot[N] = seg.init(0, M, tmp);
for(int i = 0; i <= N; ++i)
{
if(i) Lroot[i] = Lroot[i - 1];
for(auto x : ls[i])
{
Lroot[i] = seg.upd(Lroot[i], 0, M, GD[x], -1);
Lroot[i] = seg.upd(Lroot[i], 0, M, RD[x].ss, 1);
}
}
for(auto &v : ls) v.clear();
for(int i = 0; i < N; ++i) ls[RD[i].ff].push_back(i);
for(int i = N - 1; i >= 0; --i)
{
Rroot[i] = Rroot[i + 1];
for(auto x : ls[i + 1])
{
Rroot[i] = seg.upd(Rroot[i], 0, M, GD[x], -1);
Rroot[i] = seg.upd(Rroot[i], 0, M, LD[x].ss, 1);
}
}
LDroot.resize(N);
LDroot[0] = seg.init(0, M, vector<int>(M));
for(int i = 1; i < N; ++i) LDroot[i] = seg.upd(LDroot[i - 1], 0, M, RD[i - 1].ss, 1);
RDroot.resize(N);
RDroot[N - 1] = LDroot[0];
for(int i = N - 2; i >= 0; --i) RDroot[i] = seg.upd(RDroot[i + 1], 0, M, LD[i + 1].ss, 1);
// for(int i = 0; i < N; ++i)
// {
// cout << LD[i].ff << ' ' << LD[i].ss << ' ' << RD[i].ff << ' ' << RD[i].ss << endl;
// }
if(cnt > 40404000) exit(0);
}
int max_towers(int L, int R, int D)
{
D = lower_bound(DH.begin(), DH.end(), D) - DH.begin();
int m = qrym(L, R + 1);
// cout << seg.qry(Lroot[L], 0, M, D, M) << endl;
// cout << seg.qry(Rroot[R], 0, M, D, M) << endl;
// cout << (DS.end() - lower_bound(DS.begin(), DS.end(), D)) << endl;
// cout << (GD[m] >= D ? 1 : 0) << endl;
// cout << (LD[m].ss >= D ? 1 : 0) << endl;
// cout << (RD[m].ss >= D ? 1 : 0) << endl;
// cout << seg.qry(LDroot[L], 0, M, D, M) << endl;
// cout << seg.qry(RDroot[R], 0, M, D, M) << endl;
return seg.qry(Lroot[L], 0, M, D, M) + seg.qry(Rroot[R], 0, M, D, M)
- (DS.end() - lower_bound(DS.begin(), DS.end(), D))
+ (GD[m] >= D ? 1 : 0) - (LD[m].ss >= D ? 1 : 0) - (RD[m].ss >= D ? 1 : 0)
- seg.qry(LDroot[L], 0, M, D, M) - seg.qry(RDroot[R], 0, M, D, M) + 1;
}
Compilation message
towers.cpp: In member function 'int SEG::init(int, int, const std::vector<int>&)':
towers.cpp:76:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
76 | int mid = s + e >> 1;
| ~~^~~
towers.cpp: In member function 'int SEG::upd(int, int, int, int, int)':
towers.cpp:94:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
94 | int mid = s + e >> 1;
| ~~^~~
towers.cpp: In member function 'int SEG::qry(int, int, int, int, int)':
towers.cpp:106:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
106 | int mid = s + e >> 1;
| ~~^~~
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:189:8: error: 'cnt' was not declared in this scope; did you mean 'int'?
189 | if(cnt > 40404000) exit(0);
| ^~~
| int
