PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Andrii Orap
Tester: Istvan Nagy
Editorialist: Andrii Orap
DIFFICULTY:
HARD?
PREREQUISITES:
Persistent segment tree with lazy propagation
PROBLEM:
Given an integer array A of length N and M queries of type L and R. For each query find maximum F(A[i..j]) for some L \leq i \leq j \leq R, where F(B) of array B is the number of changes of maximum on prefixes of array B.
QUICK EXPLANATION:
Offline solution: Iterate i from left to right, for each position j maintain the number of maximum changes on subarray A[j..i]. For queries L, R that ends in i find maximum on range from L to R.
Online solution: use persistent segment tree with lazy propagation.
EXPLANATION:
SUBTASK 1
Let’s dp_{i,j}~- answer for subarray A[i..j], using that we can answer the queries in O(1).
We can precalculate this array in O(N^2). Initial value of dp_{i,j} is the number of maximum changes on prefices of subarray A[i..j]. Notice, that initially dp_{i,j} \leq dp_{i,j+1}. After that we can make transitions: dp_{i,j}=max(dp_{i,j}, dp_{i+1,j}).
Time complexity is O(N^2+Q).
SUBTASK 2
Suppose that A_0=\infty (very big number).
For each position i find the largest 0 \leq j \leq i such that A_j \geq A_i using stack in O(N). Let’s call this value pos_i.
Process queries offline. For each query (L_i,R_i) add pair (L_i,i) to some vector for position R_i. Iterate i from 1 to N. For each j (1 \leq j \leq i) maintain the number of maximum changes on subarray A[j..i], call this value as val_j. Then if we stay at i, we must add +1 in array val on range from pos_i+1 to i. We can do it using segment tree with lazy propagation. After that process queries at position i, for each pair (R_j, j) the answer is maximum on range from L_j to i in array val (using segment tree).
Time complexity is O((N+Q)logN).
SUBTASK 3
Do the same as in previous subtask, but using persistent segment tree with lazy propagation (online queries). E.g root_i contains segment tree for val[1..i] at state-position i. After that for each query (L,R) the answer is maximum on range from L to R in root_R.
Time complexity is O((N+Q)logN).
SOLUTIONS:
Setter's Solution, first subtask
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int n, m, a[N], dp[N][N];
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
while (t--) {
int n, m, s;
cin >> n >> m >> s;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for(int i = 1; i <= n; i++){
int cur = 0, mx = 0;
for(int j = i; j <= n; j++){
if(a[j] > mx){
mx = a[j];
cur++;
}
dp[i][j] = cur;
}
}
for(int sz = 2; sz <= n; sz++){
for(int i = 1; i + sz - 1 <= n; i++){
int j = i + sz - 1;
dp[i][j] = max(dp[i][j], dp[i + 1][j]);
}
}
int lst = 0;
for (int i = 1; i <= m; i++) {
int l, r;
cin >> l >> r;
l = (l + s * 1LL * lst - 1) % n + 1;
r = (r + s * 1LL * lst - 1) % n + 1;
if(l > r) swap(l, r);
cout << (lst = dp[l][r]) << "\n";
}
}
}
Setter's Solution, second subtask
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, a[N], ans[N], t[4 * N], ob[4 * N];
vector < pair < int, int > > q[N];
void bld(int v, int l, int r) {
t[v] = ob[v] = 0;
if (l == r) return;
int mid = (r + l) >> 1;
bld(v + v, l, mid);
bld(v + v + 1, mid + 1, r);
}
void push(int v) {
if (ob[v]) {
ob[v + v] += ob[v];
t[v + v] += ob[v];
ob[v + v + 1] += ob[v];
t[v + v + 1] += ob[v];
ob[v] = 0;
}
}
void update(int v, int l, int r, int tl, int tr) {
if (l > r || l > tr || tl > r) {
return;
}
if (tl <= l && r <= tr) {
t[v] += 1;
ob[v] += 1;
return;
}
push(v);
int mid = (r + l) >> 1;
update(v + v, l, mid, tl, tr);
update(v + v + 1, mid + 1, r, tl, tr);
t[v] = max(t[v + v], t[v + v + 1]);
}
int get(int v, int l, int r, int tl, int tr) {
if (l > r || l > tr || tl > r) {
return 0;
}
if (tl <= l && r <= tr) {
return t[v];
}
push(v);
int mid = (r + l) >> 1;
return max(get(v + v, l, mid, tl, tr), get(v + v + 1, mid + 1, r, tl, tr));
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
while (t--) {
int s;
cin >> n >> m >> s;
bld(1, 1, n);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= m; i++) {
int l, r;
cin >> l >> r;
if(l > r) swap(l, r);
q[r].push_back(make_pair(l, i));
}
vector < int > st;
st.push_back(0);
a[0] = 1e9;
for (int i = 1; i <= n; i++) {
while(a[st.back()] < a[i]){
st.pop_back();
}
update(1, 1, n, st.back() + 1, i);
for (auto it : q[i]) {
int l = it.first,
num = it.second;
ans[num] = get(1, 1, n, l, i);
}
st.push_back(i);
}
for (int i = 1; i <= m; i++) {
cout << ans[i] << "\n";
}
for(int i = 1; i <= n; i++){
q[i].clear();
}
}
}
Setter's Solution, third subtask
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, s, a[N];
struct item{
int val, ob;
item *l, *r;
item(){
val = ob = 0;
l = r = nullptr;
}
item(const item* other){
if(other == nullptr){
val = ob = 0;
l = r = nullptr;
}
else{
val = other->val;
ob = other->ob;
l = other->l;
r = other->r;
}
}
};
void push(item*& v, int l, int r){
v->l = new item(v->l);
v->r = new item(v->r);
if(v->ob){
v->val += v->ob;
if(l < r){
v->l->ob += v->ob;
v->r->ob += v->ob;
}
v->ob = 0;
}
}
void update(item*& v, int l, int r, int tl, int tr){
push(v, l, r);
if(l > r || tl > r || l > tr){
return;
}
if(tl <= l && r <= tr){
v->val++;
v->l->ob++;
v->r->ob++;
return;
}
int mid = (r + l) >> 1;
update(v->l, l, mid, tl, tr);
update(v->r, mid + 1, r, tl, tr);
v->val = max(v->l->val, v->r->val);
}
int get(item* v, int l, int r, int tl, int tr){
if(!v) return 0;
push(v, l, r);
if(l > r || tl > r || l > tr){
return 0;
}
if(tl <= l && r <= tr){
return v->val;
}
int mid = (r + l) >> 1;
return max(get(v->l, l, mid, tl, tr), get(v->r, mid + 1, r, tl, tr));
}
item* rt[N];
mt19937 rnd(time(nullptr));
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m >> s;
vector < int > st;
st.push_back(0);
a[0] = 1e9;
rt[0] = new item();
for(int i = 1; i <= n; i++){
cin >> a[i];
while(a[st.back()] < a[i]){
st.pop_back();
}
rt[i] = new item(rt[i - 1]);
update(rt[i], 1, n, st.back() + 1, i);
st.push_back(i);
}
int lst = 0;
while(m--){
int x, y;
cin >> x >> y;
int l = (x + s * 1LL * lst - 1) % n + 1,
r = (y + s * 1LL * lst - 1) % n + 1;
if(l > r){
swap(l, r);
}
cout << (lst = get(rt[r], 1, n, l, r)) << "\n";
}
}
In my case I used constant of 330, but I suspect many other values work too - it essentially got accepted on a very first attempt of choosing this constant.