/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define cerr if(false) cerr
const int N = 1e5+100, M = 1e5+10, K = 21, MX = 30;
struct Fenwick{
vector<int> t;
Fenwick(int n){
t.resize(n + 1);
}
void add(int v){
while(v < t.size()){
t[v]++;
v += v & -v;
}
}
int get(int v){
int res=0;
while(v > 0){
res+=t[v];
v -= v&-v;
}
return res;
}
};
int n, k, q, a[N], d[N], rmq[N][K], rmq2[N][K], lazy[N];
vector<pii> g[N];
vector<pii> G[N];
vector<pii> A[N][21];
vector<int> ANS(N, MOD);
vector<int> ANS2(N, MOD);
vector<int> ANS3(N, MOD);
vector<int> ANS4(N, MOD);
vector<int> ANS5(N, MOD);
vector<array<int, 3>> Q[N];
vector<array<int, 2>> Q1[N];
vector<array<int, 2>> Q2[N];
vector<array<int, 2>> Q3[N];
vector<array<int, 2>> Q4[N];
set<array<int, 2>> T[N];
int maxc(int x, int y){
return a[x] >= a[y] ? x : y; // left most
}
int maxc2(int x, int y){
return a[y] >= a[x] ? y : x; // right most
}
int get(int l, int r){
int k = int(log2(r-l+1));
return maxc(rmq[l][k], rmq[r-(1<<k)+1][k]);
}
int get2(int l, int r){
int k = int(log2(r-l+1));
return maxc2(rmq2[l][k], rmq2[r-(1<<k)+1][k]);
}
void add(int l, int r, int lev, int idx){
if(l > r) return;
int L = 1, R = r, res = r;
if(a[get(l, r)] < lev) return;
while(L <= R){
int mid = L+R>>1;
if(a[get(mid, r)] > lev){
L = mid + 1;
}else{
res = mid;
R = mid - 1;
}
}
if(a[get(res, r)] == lev){
cerr << get2(res, r) << ' ' << idx << "f\n";
Q1[get2(res, r)].pb({idx, r+1});
}
}
void add2(int l, int r, int lev, int idx){
if(l > r) return;
int L = l, R = r, res = l;
if(a[get(l, r)] < lev) return;
while(L <= R){
int mid = L+R>>1;
if(a[get(l, mid)] > lev){
R = mid - 1;
}else{
res = mid;
L = mid + 1;
}
}
if(a[get(l, res)] == lev){
Q2[get(l, res)].pb({idx, l-1});
}
}
void add3(int l, int r, int lev, int idx){
if(l > r) return;
int L = 1, R = r, res = r;
if(a[get(l, r)] < lev) return;
while(L <= R){
int mid = L+R>>1;
if(a[get(mid, r)] > lev){
L = mid + 1;
}else{
res = mid;
R = mid - 1;
}
}
if(a[get(res, r)] == lev){
cerr << get2(res, r) << ' ' << idx << "f\n";
Q3[get2(res, r)].pb({idx, r+1});
}
}
void add4(int l, int r, int lev, int idx){
if(l > r) return;
int L = l, R = r, res = l;
if(a[get(l, r)] < lev) return;
while(L <= R){
int mid = L+R>>1;
if(a[get(l, mid)] > lev){
R = mid - 1;
}else{
res = mid;
L = mid + 1;
}
}
if(a[get(l, res)] == lev){
Q4[get(l, res)].pb({idx, l-1});
}
}
void solve(){
cin >> n >> k >> q;
vector<vi> C(k + 1);
for(int i = 1; i <= n; ++i){
cin >> a[i];
C[a[i]].pb(i);
rmq[i][0] = i;
rmq2[i][0] = i;
}
for(int j = 1; j < K; ++j){
for(int i = 1; i + (1<<j) <= n + 1; ++i){
rmq[i][j] = maxc(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
rmq2[i][j] = maxc2(rmq2[i][j-1], rmq2[i+(1<<(j-1))][j-1]);
}
}
Fenwick fw(n);
for(int i = k; i >= 1; --i){
for(int x: C[i]) fw.add(x);
for(int j = 0; j < C[i].size(); ++j){
d[C[i][j]] = fw.get(C[i][j]);
}
}
{
vector<pii> Q;
vector<int> W(n + 1);
int w = 1;
for(int i = 1; i <= n; ++i){
while(Q.size() && Q.back().ff <= a[i]) Q.pop_back();
if(Q.size()){
int v = i;
int u = Q.back().ss;
int last_pos = lower_bound(all(C[a[i]]), i) - C[a[i]].begin();
if(last_pos > 0 && C[a[i]][last_pos - 1] > u){
W[i] = W[C[a[i]][last_pos - 1]] + 1;
}else{
W[i] = 1;
}
g[v].pb({u, W[i]});
G[u].pb({v, W[i]});
}
Q.pb({a[i], i});
}
Q.clear();
w = 1;
for(int i = n; i >= 1; --i){
while(Q.size() && Q.back().ff <= a[i]) Q.pop_back();
if(Q.size()){
int v = i;
int u = Q.back().ss;
int last_pos = upper_bound(all(C[a[i]]), i) - C[a[i]].begin();
if(last_pos < C[a[i]].size() && C[a[i]][last_pos] < u){
W[i] = W[C[a[i]][last_pos]] + 1;
}else{
W[i] = 1;
}
g[v].pb({u, W[i]});
G[u].pb({v, W[i]});
}else
W[i] = 0;
Q.pb({a[i], i});
}
}
for(int i = 1; i <= q; ++i){
int l, r; cin >> l >> r;
if(l > r) swap(l, r);
int level1 = get(l, r);
int level2 = get2(l, r);
Q1[level1].pb({i, l});
if(a[level1] > a[l])
add(1, l-1, a[level1], i);
Q2[level2].pb({i, r});
if(a[level1] > a[r])
add2(r+1, n, a[level2], i);
// cerr << l << ' ' << r << ' ' << level1 << " gg1\n";
// cerr << l << ' ' << r << ' ' << level2 << " gg2\n";
if(g[level1].size() == 2){
int ww = max(a[g[level1][0].ff], a[g[level1][1].ff]);
// cerr << ww << " fiucll" << '\n';
add3(1, l-1, ww, i);
add4(r+1, n, ww, i);
}
for(auto [node, W]: g[level1]){ // these nodes are same for level1 and level2
// cout << l << ' ' << r << ' ' << node << " gg\n";
Q[node].pb({i, l, r});
}
}
vector<pii> pts;
for(int i = 1; i <= n; ++i){
pts.pb({a[i], i});
lazy[i] = 0;
}
sort(all(pts));
vector<int> done(n + 1);
for(int i = 1; i <= n; ++i){
done[i] = g[i].size();
}
for(auto [_, v]: pts){
int big = -1;
int ww = 0;
for(auto [u, w]: G[v]){
if(big == -1 || T[u].size() > T[big].size()) big = u, ww = w;
}
if(big != -1){
if(done[big] == 1){
T[v].swap(T[big]);
--done[big];
}else{
T[v] = T[big];
--done[big];
}
lazy[v] = lazy[big] + ww;
}
T[v].insert({v, -lazy[v]});
for(auto [u, w]: G[v]){
if(u != big){
--done[u];
for(auto [node, dist]: T[u]){
auto it = T[v].lower_bound(array<int,2>{node, -MOD});
int nw = dist + lazy[u] + w - lazy[v];
if(it != T[v].end() && (*it)[0] == node){
if((*it)[1] > nw){
T[v].erase(it);
T[v].insert({node, nw});
}
}else{
T[v].insert({node, nw});
}
}
}
}
cerr << v << ' ' << lazy[v] << ":\n";
for(auto [pt, t]: T[v]){
cerr << pt << ' ' << t << '\n';
}
for(auto [idx, pt]: Q1[v]){
auto it = T[v].lower_bound(array<int, 2>{pt, -MOD});
assert(it != T[v].end());
assert((*it)[0] == pt);
ANS2[idx] = min(ANS2[idx], (*it)[1] + lazy[v] - d[v]);
cerr << "# " << v << ' ' << idx << ' ' << pt << ' ' << (*it)[1] + lazy[v] << ' ' << d[v] << '\n';
}
for(auto [idx, pt]: Q2[v]){
auto it = T[v].lower_bound(array<int, 2>{pt, -MOD});
assert(it != T[v].end());
assert((*it)[0] == pt);
ANS3[idx] = min((*it)[1] + lazy[v] + d[v], ANS3[idx]);
cerr << "# " << v << ' ' << idx << ' ' << pt << ' ' << (*it)[1] + lazy[v] << ' ' << d[v] << '\n';
}
for(auto [idx, pt]: Q3[v]){
auto it = T[v].lower_bound(array<int, 2>{pt, -MOD});
assert(it != T[v].end());
assert((*it)[0] == pt);
ANS4[idx] = min(ANS4[idx], (*it)[1] + lazy[v] - d[v]);
cerr << "# " << v << ' ' << idx << ' ' << pt << ' ' << (*it)[1] + lazy[v] << ' ' << d[v] << '\n';
}
for(auto [idx, pt]: Q4[v]){
auto it = T[v].lower_bound(array<int, 2>{pt, -MOD});
assert(it != T[v].end());
assert((*it)[0] == pt);
ANS5[idx] = min((*it)[1] + lazy[v] + d[v], ANS5[idx]);
cerr << "# " << v << ' ' << idx << ' ' << pt << ' ' << (*it)[1] + lazy[v] << ' ' << d[v] << '\n';
}
for(auto [idx, l, r]: Q[v]){
auto it = T[v].lower_bound(array<int, 2>{l, -MOD});
assert(it != T[v].end());
assert((*it)[0] == l);
auto it2 = T[v].lower_bound(array<int, 2>{r, -MOD});
assert(it != T[v].end());
assert((*it2)[0] == r);
ANS[idx] = min(ANS[idx], (*it)[1] + lazy[v] + (*it2)[1] + lazy[v]);
}
}
for(int i = 1; i <= q; ++i){
// cout << ANS2[i] << ' ' << ANS3[i] << ' ';
cout << min({ANS[i], ANS2[i] + ANS3[i], ANS4[i] + ANS5[i]}) - 1 << '\n';
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
en;
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |