#include<bits/stdc++.h>
#include "plants.h"
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
const int N = 200005;
const int MXS = N * 4;
int n, k, A[N], P[2][N], rev[2][N];
int wset;
struct CMP {
inline int operator() (int a, int b) const {
if (!wset)
return a < b;
return rev[0][a] > rev[0][b];
};
};
queue < int > Todo;
vector < int > res;
struct SEGT
{
int MN[MXS], LZ[MXS];
int le, ri, val;
inline void Reset()
{
memset(MN, 0, sizeof(MN));
memset(LZ, 0, sizeof(LZ));
}
inline void Shift(int id)
{
MN[lc] += LZ[id];
MN[rc] += LZ[id];
LZ[lc] += LZ[id];
LZ[rc] += LZ[id];
LZ[id] = 0;
return ;
}
void Adder(int id = 1, int l = 0, int r = n)
{
if (ri <= l || r <= le)
return ;
if (le <= l && r <= ri)
{
MN[id] += val;
LZ[id] += val;
return ;
}
Shift(id);
Adder(lc, l, md);
Adder(rc, md, r);
MN[id] = min(MN[lc], MN[rc]);
}
inline void Add(int l, int r, int vl)
{
val = vl;
if (l < 0)
l += n, r += n;
assert(r - n <= l);
assert(l >= 0);
if (r <= n)
{
le = l; ri = r;
Adder();
}
else
{
le = l; ri = n;
Adder();
le = 0; ri = r - n;
Adder();
}
}
void Extract(int id = 1, int l = 0, int r = n)
{
assert(MN[id] >= 0);
if (MN[id] > 0)
return ;
if (r - l < 2)
return void(res.push_back(l));
Shift(id);
Extract(lc, l, md);
Extract(rc, md, r);
}
};
pair < int , int > F[N];
SEGT SG[2];
/*bitset < N > Ad[N];
int Mark[N];
void DFS(int v)
{
Mark[v] = 1;
for (int u = 0; u < n; u ++)
if (Ad[v][u])
{
if (!Mark[u])
DFS(u);
Ad[v] |= Ad[u];
}
}*/
int MN[N * 4], MX[N * 4];
int segn;
inline void Do(int i, int av, int bv)
{
i += segn;
if (av < 0)
av += n, bv += n;
MN[i] = av;
MX[i] = bv;
for (; i; i >>= 1)
{
MN[i >> 1] = min(MN[i], MN[i ^ 1]);
MX[i >> 1] = max(MX[i], MX[i ^ 1]);
}
}
inline pair < int , int > Get(int l, int r)
{
pair < int , int > ret = {l, r};
for (l += segn, r += segn; l < r; l >>= 1, r >>= 1)
{
if (l & 1)
{
ret.first = min(ret.first, MN[l]);
ret.second = max(ret.second, MX[l]);
l ++;
}
if (r & 1)
{
r --;
ret.first = min(ret.first, MN[r]);
ret.second = max(ret.second, MX[r]);
}
}
if (ret.first < 0)
ret.first += n, ret.second += n;
if (ret.second >= ret.first + n)
ret = {0, n};
return ret;
}
inline pair < int , int > Query(int le, int ri)
{
int mn = le;
int mx = ri;
assert(le >= 0 && ri <= n + n);
assert(le >= 0);
pair < int , int > ret = Get(le, ri);
mn = min(mn, ret.first);
mx = max(mx, ret.second);
ret = Get(max(le - n, 0), max(ri - n, 0));
mn = min(mn, ret.first);
mx = max(mx, ret.second);
ret = Get(min(le + n, segn), min(ri + n, segn));
mn = min(mn, ret.first);
mx = max(mx, ret.second);
if (mn < 0)
mn += n, mx += n;
if (mn >= n)
mn -= n, mx -= n;
mx = min(mx, n + n);
return make_pair(mn, mx);
}
void init(int _k, vector < int > _r)
{
k = _k;
n = (int)_r.size();
for (int i = 0; i < n; i ++)
A[i] = _r[i];
for (int w = 0; w <= 0; w ++)
{
wset = w;
SG[0].Reset();
SG[1].Reset();
for (int i = 0; i < n; i ++)
{
if (A[i])
{
SG[1].Add(i, i + 1, 1);
SG[0].Add(i, i + 1, A[i]);
}
else
{
SG[1].Add(i + 1, i + k, 1);
SG[0].Add(i, i + 1, N);
}
}
Todo.clear();
vector < int > M(n, 0);
for (int __ = 0; __ < n; __ ++)
{
res.clear();
SG[1].Extract();
for (int i : res)
Todo.push(i);
res.clear();
assert((int)Todo.size());
int i = Todo.front();
M[i] = 1;
Todo.pop();
/*for (int j = i - k + 1; j < i + k; j ++)
{
int tt = j;
if (tt < 0) tt += n;
if (tt >= n) tt -= n;
if (M[tt])
continue;
Ad[tt][i] = 1;
}*/
F[i] = {i - k + 1, i + k};
P[w][__] = i;
rev[w][i] = __;
SG[1].Add(i, i + 1, N);
SG[0].Add(i - k + 1, i, -1);
SG[1].Add(i + 1, i + k, -1);
res.clear();
SG[0].Extract();
for (int j : res)
{
SG[1].Add(j, j + 1, -1);
SG[1].Add(j + 1, j + k, 1);
SG[0].Add(j, j + 1, N);
}
res.clear();
}
/*for (int i = 0; i < n; i ++)
printf("%d ", P[w][i]);
printf("\n");*/
}
/*for (int i = 0; i < n; i ++)
if (!Mark[i])
DFS(i);*/
/* segn = n + n;
memset(MN, 63, sizeof(MN));
memset(MX, -63, sizeof(MX));
for (int h = n - 1; h >= 0; h --)
{
int i = P[0][h];
// printf("=== %d :: %d , %d\n", i, F[i].first, F[i].second);
if (F[i].first < 0)
F[i].first += n, F[i].second += n;
if (F[i].first >= n)
F[i].first -= n, F[i].second -= n;
F[i].second = min(F[i].second, segn);
F[i] = Query(F[i].first, F[i].second);
if (F[i].first < 0)
F[i].first += n, F[i].second += n;
if (F[i].first >= n)
F[i].first -= n, F[i].second -= n;
F[i].second = min(F[i].second, segn);
Do(i, F[i].first, F[i].second);
Do(i + n, F[i].first, F[i].second);
// printf("%d :: %d , %d\n", i, F[i].first, F[i].second);
}*/
return ;
/* for (int i = 0; i < n; i ++)
{
printf("%d :: %d\n", F[i].first, F[i].second);
}*/
}
inline bool Check(pair < int , int > ff, int i)
{
int l = ff.first;
int r = ff.second;
if (l < 0)
l += n, r += n;
if (l <= i && i < r)
return 1;
if (l <= i + n && i + n < r)
return 1;
return 0;
}
int compare_plants(int a, int b)
{
if (rev[0][a] < rev[0][b])
return 1;
return -1;
/*if (Ad[a][b])
return -1;
if (Ad[b][a])
return 1;
return 0;*/
if (rev[0][a] < rev[0][b] && Check(F[a], b))
return 1;
if (rev[0][b] < rev[0][a] && Check(F[b], a))
return -1;
return 0;
}
Compilation message
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:190:8: error: 'class std::queue<int>' has no member named 'clear'
190 | Todo.clear();
| ^~~~~
