# LOJ Chen 2461. "2018 training team mutual test Day 1" perfect queue (block maintenance monotony)

subject
See the proposition report of perfect queue by Lin Xuheng

It is converted to find the earliest time when all the added points are completely popped up after each interval is added.
Then it is found that the same insertion time of interval has monotonicity.
Each interval is divided into n\sqrt nn large blocks and n\sqrt nn single points. (one query becomes n\sqrt nn)
For each big block and each single point, two points are used to process the answer of each query.
Then merge the time intervals by color,
Inserting by input time can save sorting,
Time o (n n) O (n \ sqrt n) O (NN)
MLE 85pts Code:

#include <bits/stdc++.h>
#define maxn 100005
#define S 100
#define mS (maxn / S) + 10
#define LL long long
using namespace std;

int n, m, a[maxn], bl[maxn], ed[maxn], L[maxn], R[maxn], X[maxn];
vector<tuple<int, int, int> > op[maxn];
vector<int> opa[mS];
vector<pair<int, int> > G[maxn];
LL ans[maxn];

int main() {
scanf("%d%d", &n, &m);
memset(bl, -1, sizeof bl), bl[0] = 0;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), bl[i] = i / S;
for (int i = 1; i <= m; i++) {
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
L[i] = l, R[i] = r, X[i] = x;
for (int j = bl[l] + 1; j < bl[r]; j++) opa[j].push_back(i);
if (bl[l] != bl[r]) {
for (int j = l; j <= r && bl[j] == bl[l]; j++)
op[j].push_back(make_tuple(opa[bl[j]].size(), x, i));
for (int j = r; j >= l && bl[j] == bl[r]; j--)
op[j].push_back(make_tuple(opa[bl[j]].size(), x, i));
} else {
for (int j = l; j <= r; j++) op[j].push_back(make_tuple(opa[bl[j]].size(), x, i));
}
}

for (int i = 0; i * S <= n; i++) {
for (int j = 0; j < S; j++) Mx = max(Mx, ar[j] = (i * S + j <= n ? a[i * S + j] : 0));
for (int x = 1, y = 2; x <= m;) {
if (L[x] < i * S && (i + 1) * S - 1 < R[x]) {
for (; Mx + addtag > 0 && y <= m; y++) {
if (L[y] < i * S && (i + 1) * S - 1 < R[y])
else if ((i * S <= L[y] && L[y] < (i + 1) * S) || (i * S <= R[y] && R[y] < (i + 1) * S)) {
Mx = -0x3f3f3f3f;
for (int j = 0; j < S; j++) {
if (L[y] - i * S <= j && j <= R[y] - i * S)
ar[j]--;
Mx = max(Mx, ar[j]);
}
}
}
ed[x] = max(ed[x], Mx + addtag > 0 ? m + 1 : y - 1);
}
++x;
if (x <= m) {
if (L[x] < i * S && (i + 1) * S - 1 < R[x])
else if ((i * S <= L[x] && L[x] < (i + 1) * S) || (i * S <= R[x] && R[x] < (i + 1) * S)) {
Mx = -0x3f3f3f3f;
for (int j = 0; j < S; j++) {
if (L[x] - i * S <= j && j <= R[x] - i * S)
ar[j]++;
Mx = max(Mx, ar[j]);
}
}
}
}
}

for (int i = 1; i <= n; i++) {
for (int x = 0, y = 0, sz = op[i].size(); x < sz; x++) {
for (; y < sz && y - x + get<0>(op[i][y]) - get<0>(op[i][x]) < a[i]; y++)
;
if (y == sz && y - 1 - x + opa[bl[i]].size() - get<0>(op[i][x]) >= a[i])
ed[get<2>(op[i][x])] =
max(ed[get<2>(op[i][x])], opa[bl[i]][a[i] + get<0>(op[i][x]) + x + 1 - y - 1]);
else if (y == sz)
ed[get<2>(op[i][x])] = max(ed[get<2>(op[i][x])], m + 1);
else if (y - x + get<0>(op[i][y]) - get<0>(op[i][x]) == a[i])
ed[get<2>(op[i][x])] = max(ed[get<2>(op[i][x])], get<2>(op[i][y]));
else if (get<0>(op[i][y]) - (y - x + get<0>(op[i][y]) - get<0>(op[i][x]) - a[i]) >=
opa[bl[i]].size())
ed[get<2>(op[i][x])] = max(ed[get<2>(op[i][x])], m + 1);
else
ed[get<2>(op[i][x])] =
max(ed[get<2>(op[i][x])],
opa[bl[i]][get<0>(op[i][y]) - (y - x + get<0>(op[i][y]) - get<0>(op[i][x]) - a[i])]);
}
}

for (int i = 1; i <= m; i++) G[X[i]].push_back(make_pair(i, ed[i]));
for (int i = 1; i <= 100000; i++) {
int Max = 0;
for (int j = 0, sz = G[i].size(); j < sz; j++) {
if (G[i][j].first >= Max)
ans[G[i][j].first]++, ans[G[i][j].second]--;
else if (Max <= G[i][j].second)
ans[Max]++, ans[G[i][j].second]--;
Max = max(Max, G[i][j].second);
}
}
for (int i = 1; i <= m; i++) ans[i] += ans[i - 1], printf("%d\n", ans[i]);
}


Posted on Thu, 07 Nov 2019 13:23:53 -0800 by f8ball