109892024-05-02 16:44:00mraronSiklóernyőzéscpp17Elfogadva 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; 
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva6ms5092 KiB
2Elfogadva1.085s64256 KiB
subtask25/5
3Elfogadva915ms93144 KiB
4Elfogadva874ms93312 KiB
5Elfogadva890ms89540 KiB
6Elfogadva792ms92844 KiB
7Elfogadva861ms84092 KiB
8Elfogadva619ms84580 KiB
subtask313/13
9Elfogadva8ms5732 KiB
10Elfogadva9ms5884 KiB
11Elfogadva8ms5936 KiB
12Elfogadva8ms5900 KiB
13Elfogadva9ms5860 KiB
14Elfogadva8ms5860 KiB
15Elfogadva8ms6116 KiB
16Elfogadva9ms6116 KiB
17Elfogadva8ms6136 KiB
subtask410/10
18Elfogadva8ms5732 KiB
19Elfogadva9ms5884 KiB
20Elfogadva8ms5936 KiB
21Elfogadva8ms5900 KiB
22Elfogadva9ms5860 KiB
23Elfogadva8ms5860 KiB
24Elfogadva8ms6116 KiB
25Elfogadva9ms6116 KiB
26Elfogadva8ms6136 KiB
27Elfogadva287ms56484 KiB
28Elfogadva273ms56532 KiB
29Elfogadva289ms56524 KiB
30Elfogadva291ms56520 KiB
31Elfogadva273ms56560 KiB
32Elfogadva273ms56552 KiB
33Elfogadva333ms71760 KiB
34Elfogadva331ms71724 KiB
35Elfogadva326ms63464 KiB
36Elfogadva344ms79820 KiB
subtask515/15
37Elfogadva8ms5732 KiB
38Elfogadva9ms5884 KiB
39Elfogadva8ms5936 KiB
40Elfogadva8ms5900 KiB
41Elfogadva9ms5860 KiB
42Elfogadva8ms5860 KiB
43Elfogadva8ms6116 KiB
44Elfogadva9ms6116 KiB
45Elfogadva8ms6136 KiB
46Elfogadva216ms13740 KiB
47Elfogadva216ms13720 KiB
48Elfogadva266ms13368 KiB
49Elfogadva252ms13412 KiB
50Elfogadva300ms13028 KiB
51Elfogadva300ms12996 KiB
52Elfogadva291ms13028 KiB
53Elfogadva294ms12944 KiB
54Elfogadva277ms13540 KiB
55Elfogadva268ms13348 KiB
56Elfogadva277ms13412 KiB
57Elfogadva286ms13284 KiB
subtask610/10
58Elfogadva630ms63488 KiB
59Elfogadva647ms63360 KiB
60Elfogadva628ms63500 KiB
61Elfogadva644ms63436 KiB
62Elfogadva633ms63548 KiB
63Elfogadva630ms63488 KiB
64Elfogadva602ms79476 KiB
65Elfogadva523ms76300 KiB
66Elfogadva508ms70228 KiB
67Elfogadva607ms84556 KiB
subtask711/11
68Elfogadva8ms5732 KiB
69Elfogadva9ms5884 KiB
70Elfogadva8ms5936 KiB
71Elfogadva8ms5900 KiB
72Elfogadva9ms5860 KiB
73Elfogadva8ms5860 KiB
74Elfogadva8ms6116 KiB
75Elfogadva9ms6116 KiB
76Elfogadva8ms6136 KiB
77Elfogadva287ms56484 KiB
78Elfogadva273ms56532 KiB
79Elfogadva289ms56524 KiB
80Elfogadva291ms56520 KiB
81Elfogadva273ms56560 KiB
82Elfogadva273ms56552 KiB
83Elfogadva333ms71760 KiB
84Elfogadva331ms71724 KiB
85Elfogadva326ms63464 KiB
86Elfogadva344ms79820 KiB
87Elfogadva630ms63488 KiB
88Elfogadva647ms63360 KiB
89Elfogadva628ms63500 KiB
90Elfogadva644ms63436 KiB
91Elfogadva633ms63548 KiB
92Elfogadva630ms63488 KiB
93Elfogadva602ms79476 KiB
94Elfogadva523ms76300 KiB
95Elfogadva508ms70228 KiB
96Elfogadva607ms84556 KiB
97Elfogadva652ms64324 KiB
98Elfogadva621ms64396 KiB
99Elfogadva629ms64376 KiB
100Elfogadva642ms64432 KiB
101Elfogadva638ms64344 KiB
102Elfogadva638ms64428 KiB
103Elfogadva708ms80484 KiB
104Elfogadva672ms74104 KiB
105Elfogadva689ms70604 KiB
106Elfogadva663ms81616 KiB
subtask821/21
107Elfogadva7ms5232 KiB
108Elfogadva955ms60628 KiB
109Elfogadva1.1s64312 KiB
110Elfogadva949ms64292 KiB
111Elfogadva1.087s64340 KiB
112Elfogadva902ms64340 KiB
113Elfogadva1.062s64332 KiB
114Elfogadva1.062s64256 KiB
115Elfogadva652ms63316 KiB
116Elfogadva602ms63420 KiB
117Elfogadva648ms63488 KiB
118Elfogadva629ms63444 KiB
119Elfogadva601ms63444 KiB
120Elfogadva621ms63444 KiB
121Elfogadva958ms64212 KiB
122Elfogadva871ms64256 KiB
subtask915/15
123Elfogadva7ms5232 KiB
124Elfogadva955ms60628 KiB
125Elfogadva915ms93144 KiB
126Elfogadva874ms93312 KiB
127Elfogadva890ms89540 KiB
128Elfogadva792ms92844 KiB
129Elfogadva861ms84092 KiB
130Elfogadva619ms84580 KiB
131Elfogadva8ms5732 KiB
132Elfogadva9ms5884 KiB
133Elfogadva8ms5936 KiB
134Elfogadva8ms5900 KiB
135Elfogadva9ms5860 KiB
136Elfogadva8ms5860 KiB
137Elfogadva8ms6116 KiB
138Elfogadva9ms6116 KiB
139Elfogadva8ms6136 KiB
140Elfogadva287ms56484 KiB
141Elfogadva273ms56532 KiB
142Elfogadva289ms56524 KiB
143Elfogadva291ms56520 KiB
144Elfogadva273ms56560 KiB
145Elfogadva273ms56552 KiB
146Elfogadva333ms71760 KiB
147Elfogadva331ms71724 KiB
148Elfogadva326ms63464 KiB
149Elfogadva344ms79820 KiB
150Elfogadva216ms13740 KiB
151Elfogadva216ms13720 KiB
152Elfogadva266ms13368 KiB
153Elfogadva252ms13412 KiB
154Elfogadva300ms13028 KiB
155Elfogadva300ms12996 KiB
156Elfogadva291ms13028 KiB
157Elfogadva294ms12944 KiB
158Elfogadva277ms13540 KiB
159Elfogadva268ms13348 KiB
160Elfogadva277ms13412 KiB
161Elfogadva286ms13284 KiB
162Elfogadva630ms63488 KiB
163Elfogadva647ms63360 KiB
164Elfogadva628ms63500 KiB
165Elfogadva644ms63436 KiB
166Elfogadva633ms63548 KiB
167Elfogadva630ms63488 KiB
168Elfogadva602ms79476 KiB
169Elfogadva523ms76300 KiB
170Elfogadva508ms70228 KiB
171Elfogadva607ms84556 KiB
172Elfogadva652ms64324 KiB
173Elfogadva621ms64396 KiB
174Elfogadva629ms64376 KiB
175Elfogadva642ms64432 KiB
176Elfogadva638ms64344 KiB
177Elfogadva638ms64428 KiB
178Elfogadva708ms80484 KiB
179Elfogadva672ms74104 KiB
180Elfogadva689ms70604 KiB
181Elfogadva663ms81616 KiB
182Elfogadva1.1s64312 KiB
183Elfogadva949ms64292 KiB
184Elfogadva1.087s64340 KiB
185Elfogadva902ms64340 KiB
186Elfogadva1.062s64332 KiB
187Elfogadva1.062s64256 KiB
188Elfogadva652ms63316 KiB
189Elfogadva602ms63420 KiB
190Elfogadva648ms63488 KiB
191Elfogadva629ms63444 KiB
192Elfogadva601ms63444 KiB
193Elfogadva621ms63444 KiB
194Elfogadva958ms64212 KiB
195Elfogadva871ms64256 KiB
196Elfogadva984ms80204 KiB
197Elfogadva1.148s80208 KiB
198Elfogadva1.059s79080 KiB
199Elfogadva1.052s72660 KiB
200Elfogadva1.087s72512 KiB
201Elfogadva1.218s70912 KiB
202Elfogadva1.008s68864 KiB
203Elfogadva1.228s68052 KiB
204Elfogadva1.116s67412 KiB
205Elfogadva970ms67156 KiB