109892024-05-02 16:44:00mraronSiklóernyőzéscpp17Accepted 100/1001.228s93312 KiB
#include<bits/stdc++.h>
using namespace std;

#define LOG(x) cerr<<(#x)<<" = "<<x<<"\n";  

int n,q;
int a[200010];
int qL[200010], qR[200010];

void read() {
    cin>>n>>q;
    for(int i=0;i<n;++i) {
        cin>>a[i];
    }
    for(int i=0;i<q;++i) {
        cin>>qL[i]>>qR[i];
    }
}

struct node {
    int mx, lazy;
    node *left,*right;
};

node* build(int L, int R) {
    if(L==R){
        return new node{0,0,nullptr,nullptr};
    }else {
        node* res=new node{0,0,build(L, (L+R)/2),build((L+R)/2+1, R)};
        return res;
    }
}

void push(node* root) {
    if(root->lazy>0) {
        root->mx+=root->lazy;
        if(root->left!=nullptr) {
            root->left->lazy+=root->lazy;
        }
        if(root->right!=nullptr) {
            root->right->lazy+=root->lazy;
        }
        root->lazy=0;
    }
} 

void range_incr(node *root, int L, int R, int i, int j) {
    push(root);
    if(R<i || j<L) {
        return ;
    }
    if(i<=L && R<=j) {
        root->lazy++;
        push(root);
        return ;
    }
    range_incr(root->left, L, (L+R)/2, i, j);
    range_incr(root->right, (L+R)/2+1, R, i, j);
    root->mx=max(root->left->mx, root->right->mx);
    return ;
}

int range_mx(node* root, int L, int R, int i, int j) {
    push(root);
    if(R<i || j<L) return 0;
    if(i<=L && R<=j) return root->mx;
    return max(range_mx(root->left, L, (L+R)/2, i, j), range_mx(root->right, (L+R)/2+1, R, i, j));
}

void debug(node* root) {
    for(int i=0;i<n;++i) cerr<<range_mx(root, 0,n-1,i,i)<<" ";
    cerr<<"\n";
}

void solve() {
    stack<int, vector<int>> stL, stR; 
    a[n]=n+1;
    vector<int> toLeft(n,n), toRight(n,n), L(n,-1), R(n,-1), par(n,-1);
    for(int i=0, j=n-1;i<n;++i,j--) {
        while(!stL.empty() && a[stL.top()]<a[i]) stL.pop();
        while(!stR.empty() && a[stR.top()]<a[j]) stR.pop();
        if(!stL.empty()) toLeft[i]=stL.top();
        if(!stR.empty()) toRight[j]=stR.top();
        stL.push(i);stR.push(j);
    }
    for(int i=0;i<n;++i) {
        if(a[toLeft[i]]<a[toRight[i]]) par[i]=toLeft[i], R[toLeft[i]]=i;
        else if(a[toLeft[i]]>a[toRight[i]]) par[i]=toRight[i], L[toRight[i]]=i;
    }
    vector<vector<int>> adj(200010);
    int root;
    for(int i=0;i<n;++i) {
        if(par[i]>=0) adj[par[i]].push_back(i);
        else root=i;
    }
    vector<vector<int>> dp(18, vector<int>(n));
    vector<int> lvl(n), eL(n), eR(n); int ind=0;
    auto dfs=[&](auto self, int x) -> void {
        eL[x]=ind++;
        sort(adj[x].begin(), adj[x].end());
        for(int i:adj[x]) {
            dp[0][i]=x;
            lvl[i]=lvl[x]+1;
            self(self, i);
        }
        eR[x]=ind-1;
    };
    dp[0][root]=root;
    dfs(dfs, root);
    for(int j=1;j<18;++j)
        for(int i=0;i<n;++i) {
            dp[j][i]=dp[j-1][dp[j-1][i]];
        }
    auto lca=[&](int x, int y) -> int {
        if(lvl[x]>lvl[y]) swap(x,y);
        if(lvl[y]>lvl[x]) {
            for(int j=17;j>=0;j--) {
                int py=dp[j][y];
                if(lvl[py]>lvl[x]) y=py;
            }
            y=dp[0][y];
        }
        if(x==y) return y;
        for(int j=17;j>=0;j--) {
            int px=dp[j][x], py=dp[j][y];
            if(px!=py) x=px, y=py;
        }
        return dp[0][x];
    };

    vector<int> qs(q), bal(q), jobb(q), mx_ind(q);
    for(int i=0;i<q;++i) mx_ind[i]=lca(qL[i]-1, qR[i]-1);
    iota(qs.begin(), qs.end(), 0);
   
    auto tree=build(0,n-1);
    sort(qs.begin(), qs.end(), [&](int x, int y) {
        return qL[x]>qL[y];
    });
    for(int idx=0,j=n;idx<qs.size();++idx) {
        int i=qs[idx];
        while(j>=qL[i]) {
            j--;
            range_incr(tree, 0,n-1, eL[j], eR[j]);
        }
        if(L[mx_ind[i]]>=0) {
            bal[i]=range_mx(tree, 0, n-1, eL[L[mx_ind[i]]], eR[L[mx_ind[i]]])-range_mx(tree, 0, n-1, eL[mx_ind[i]], eL[mx_ind[i]]);
        }
    }
    sort(qs.begin(), qs.end(), [&](int x, int y) {
        return qR[x]<qR[y];
    });
    tree=build(0,n-1);
    for(int idx=0,j=0;idx<qs.size();++idx) {
        int i=qs[idx];
        while(j<qR[i]) {
            range_incr(tree, 0,n-1, eL[j], eR[j]);
            j++;
        }
        
        if(R[mx_ind[i]]>=0) {
            jobb[i]=range_mx(tree, 0, n-1, eL[R[mx_ind[i]]], eR[R[mx_ind[i]]])-range_mx(tree, 0, n-1, eL[mx_ind[i]], eL[mx_ind[i]]);
        }
    }

    
    for(int i=0;i<q;++i) {
        cout<<max(bal[i],jobb[i])<<"\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    read();
    solve();
    return 0; 
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted6ms5092 KiB
2Accepted1.085s64256 KiB
subtask25/5
3Accepted915ms93144 KiB
4Accepted874ms93312 KiB
5Accepted890ms89540 KiB
6Accepted792ms92844 KiB
7Accepted861ms84092 KiB
8Accepted619ms84580 KiB
subtask313/13
9Accepted8ms5732 KiB
10Accepted9ms5884 KiB
11Accepted8ms5936 KiB
12Accepted8ms5900 KiB
13Accepted9ms5860 KiB
14Accepted8ms5860 KiB
15Accepted8ms6116 KiB
16Accepted9ms6116 KiB
17Accepted8ms6136 KiB
subtask410/10
18Accepted8ms5732 KiB
19Accepted9ms5884 KiB
20Accepted8ms5936 KiB
21Accepted8ms5900 KiB
22Accepted9ms5860 KiB
23Accepted8ms5860 KiB
24Accepted8ms6116 KiB
25Accepted9ms6116 KiB
26Accepted8ms6136 KiB
27Accepted287ms56484 KiB
28Accepted273ms56532 KiB
29Accepted289ms56524 KiB
30Accepted291ms56520 KiB
31Accepted273ms56560 KiB
32Accepted273ms56552 KiB
33Accepted333ms71760 KiB
34Accepted331ms71724 KiB
35Accepted326ms63464 KiB
36Accepted344ms79820 KiB
subtask515/15
37Accepted8ms5732 KiB
38Accepted9ms5884 KiB
39Accepted8ms5936 KiB
40Accepted8ms5900 KiB
41Accepted9ms5860 KiB
42Accepted8ms5860 KiB
43Accepted8ms6116 KiB
44Accepted9ms6116 KiB
45Accepted8ms6136 KiB
46Accepted216ms13740 KiB
47Accepted216ms13720 KiB
48Accepted266ms13368 KiB
49Accepted252ms13412 KiB
50Accepted300ms13028 KiB
51Accepted300ms12996 KiB
52Accepted291ms13028 KiB
53Accepted294ms12944 KiB
54Accepted277ms13540 KiB
55Accepted268ms13348 KiB
56Accepted277ms13412 KiB
57Accepted286ms13284 KiB
subtask610/10
58Accepted630ms63488 KiB
59Accepted647ms63360 KiB
60Accepted628ms63500 KiB
61Accepted644ms63436 KiB
62Accepted633ms63548 KiB
63Accepted630ms63488 KiB
64Accepted602ms79476 KiB
65Accepted523ms76300 KiB
66Accepted508ms70228 KiB
67Accepted607ms84556 KiB
subtask711/11
68Accepted8ms5732 KiB
69Accepted9ms5884 KiB
70Accepted8ms5936 KiB
71Accepted8ms5900 KiB
72Accepted9ms5860 KiB
73Accepted8ms5860 KiB
74Accepted8ms6116 KiB
75Accepted9ms6116 KiB
76Accepted8ms6136 KiB
77Accepted287ms56484 KiB
78Accepted273ms56532 KiB
79Accepted289ms56524 KiB
80Accepted291ms56520 KiB
81Accepted273ms56560 KiB
82Accepted273ms56552 KiB
83Accepted333ms71760 KiB
84Accepted331ms71724 KiB
85Accepted326ms63464 KiB
86Accepted344ms79820 KiB
87Accepted630ms63488 KiB
88Accepted647ms63360 KiB
89Accepted628ms63500 KiB
90Accepted644ms63436 KiB
91Accepted633ms63548 KiB
92Accepted630ms63488 KiB
93Accepted602ms79476 KiB
94Accepted523ms76300 KiB
95Accepted508ms70228 KiB
96Accepted607ms84556 KiB
97Accepted652ms64324 KiB
98Accepted621ms64396 KiB
99Accepted629ms64376 KiB
100Accepted642ms64432 KiB
101Accepted638ms64344 KiB
102Accepted638ms64428 KiB
103Accepted708ms80484 KiB
104Accepted672ms74104 KiB
105Accepted689ms70604 KiB
106Accepted663ms81616 KiB
subtask821/21
107Accepted7ms5232 KiB
108Accepted955ms60628 KiB
109Accepted1.1s64312 KiB
110Accepted949ms64292 KiB
111Accepted1.087s64340 KiB
112Accepted902ms64340 KiB
113Accepted1.062s64332 KiB
114Accepted1.062s64256 KiB
115Accepted652ms63316 KiB
116Accepted602ms63420 KiB
117Accepted648ms63488 KiB
118Accepted629ms63444 KiB
119Accepted601ms63444 KiB
120Accepted621ms63444 KiB
121Accepted958ms64212 KiB
122Accepted871ms64256 KiB
subtask915/15
123Accepted7ms5232 KiB
124Accepted955ms60628 KiB
125Accepted915ms93144 KiB
126Accepted874ms93312 KiB
127Accepted890ms89540 KiB
128Accepted792ms92844 KiB
129Accepted861ms84092 KiB
130Accepted619ms84580 KiB
131Accepted8ms5732 KiB
132Accepted9ms5884 KiB
133Accepted8ms5936 KiB
134Accepted8ms5900 KiB
135Accepted9ms5860 KiB
136Accepted8ms5860 KiB
137Accepted8ms6116 KiB
138Accepted9ms6116 KiB
139Accepted8ms6136 KiB
140Accepted287ms56484 KiB
141Accepted273ms56532 KiB
142Accepted289ms56524 KiB
143Accepted291ms56520 KiB
144Accepted273ms56560 KiB
145Accepted273ms56552 KiB
146Accepted333ms71760 KiB
147Accepted331ms71724 KiB
148Accepted326ms63464 KiB
149Accepted344ms79820 KiB
150Accepted216ms13740 KiB
151Accepted216ms13720 KiB
152Accepted266ms13368 KiB
153Accepted252ms13412 KiB
154Accepted300ms13028 KiB
155Accepted300ms12996 KiB
156Accepted291ms13028 KiB
157Accepted294ms12944 KiB
158Accepted277ms13540 KiB
159Accepted268ms13348 KiB
160Accepted277ms13412 KiB
161Accepted286ms13284 KiB
162Accepted630ms63488 KiB
163Accepted647ms63360 KiB
164Accepted628ms63500 KiB
165Accepted644ms63436 KiB
166Accepted633ms63548 KiB
167Accepted630ms63488 KiB
168Accepted602ms79476 KiB
169Accepted523ms76300 KiB
170Accepted508ms70228 KiB
171Accepted607ms84556 KiB
172Accepted652ms64324 KiB
173Accepted621ms64396 KiB
174Accepted629ms64376 KiB
175Accepted642ms64432 KiB
176Accepted638ms64344 KiB
177Accepted638ms64428 KiB
178Accepted708ms80484 KiB
179Accepted672ms74104 KiB
180Accepted689ms70604 KiB
181Accepted663ms81616 KiB
182Accepted1.1s64312 KiB
183Accepted949ms64292 KiB
184Accepted1.087s64340 KiB
185Accepted902ms64340 KiB
186Accepted1.062s64332 KiB
187Accepted1.062s64256 KiB
188Accepted652ms63316 KiB
189Accepted602ms63420 KiB
190Accepted648ms63488 KiB
191Accepted629ms63444 KiB
192Accepted601ms63444 KiB
193Accepted621ms63444 KiB
194Accepted958ms64212 KiB
195Accepted871ms64256 KiB
196Accepted984ms80204 KiB
197Accepted1.148s80208 KiB
198Accepted1.059s79080 KiB
199Accepted1.052s72660 KiB
200Accepted1.087s72512 KiB
201Accepted1.218s70912 KiB
202Accepted1.008s68864 KiB
203Accepted1.228s68052 KiB
204Accepted1.116s67412 KiB
205Accepted970ms67156 KiB