# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
54262063 |
Practice:
Ark_ |
1117G
- 12
|
GNU C++11
|
Accepted
|
1794 ms
|
112724 KB
|
2019-05-17 05:48:43 |
2019-05-17 05:48:43 |
|
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e6 + 5;
int n, q, a[MAXN], L[MAXN], st[MAXN], top, ql[MAXN], qr[MAXN];
LL ans[MAXN];
vector<int> G[MAXN], Q[MAXN];
struct BIT {
LL T[MAXN];
inline void upd(int x, int val) {
while(x <= n) T[x] += val, x += x&-x;
}
inline LL qsum(int x) { LL re = 0;
while(x) re += T[x], x -= x&-x;
return re;
}
}tr[2];
inline void solve() {
memset(G, 0, sizeof G);
memset(Q, 0, sizeof Q);
for(int i = 1; i <= q; ++i)
Q[ql[i]].push_back(i), ans[i] += 1ll * (ql[i] + qr[i]) * (qr[i] - ql[i] + 1) / 2;
top = 0;
for(int i = 1; i <= n; ++i) {
while(top && a[st[top]] < a[i])--top;
L[i] = st[top] + 1, st[++top] = i;
G[L[i]].push_back(i);
tr[0].upd(i, L[i]);
}
for(int i = 1; i <= n; ++i) {
for(auto x : G[i]) tr[0].upd(x, -i), tr[1].upd(x, 1);
for(auto x : Q[i]) ans[x] -= tr[0].qsum(qr[x]) + tr[1].qsum(qr[x]) * i;
tr[1].upd(i, -1);
}
}
int main() {
scanf("%d%d", &n, &q);
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for(int i = 1; i <= q; ++i) scanf("%d", &ql[i]);
for(int i = 1; i <= q; ++i) scanf("%d", &qr[i]);
solve();
reverse(a + 1, a + n + 1);
for(int i = 1; i <= q; ++i)
ql[i] = n-ql[i]+1, qr[i] = n-qr[i]+1, swap(ql[i], qr[i]);
solve();
for(int i = 1; i <= q; ++i) {
printf("%I64d ", ans[i] + (qr[i] - ql[i] + 1));
}
}
Click to see test details