## Nhận xét đầu
Ta thấy nếu ta phải đổi một đoạn cực dài thì ở vị trí **i** ta phải tìm tới một vị trí **j** gần nhất ở bên phải sao cho **a[j] > a[i]**, có thể dùng **stack** để làm bước này. Và sau đó đổi các điểm ở giữa trong khoản **i + 1 -> j – 1**. Sau đó từ j ta lại tiếp tục công việc này là tìm một điểm tiếp theo lớn hơn hẳn a[j]
Với một đoạn i -> j cơ bản lúc này ta có thể dùng công thức prefix sum để tính đáp án là số cái cần thêm vô ở giữa chúng bằng công thức sau:
$$
S = \text{prefix}[v - 1] - \text{prefix}[u - 1]
$$
$$
\text{len} = v - u
$$
$$
\text{Res} = \text{len} \times a[u] - S
$$
## Ta thấy ta có thể tính được một đoạn rồi. Ta có thể ghép các đoạn lại với nhau mà đúng hơm?
Vậy ta sẽ gọi **par[u][k]** là vị trí cuối cùng gần nhất của một dãy con tăng bắt đầu từ **u** và có $2^k$ phần tử.
Dễ hiểu hơn là nó có dạng như sau:
$$
a[u] < a[\text{par1}] < a[\text{par2}] < \dots < a[\text{par}_{2^k}]
$$
sao mà $\text{par}_{2^k}$ cho gần nhất là được.
Vậy ta gọi thêm **f[u][k]** là kết quả của bài toán từ thằng **u** tới vị trí **par[u][k]**.
Dùng **BINARY LIFTING** để xây 2 cái mảng này.
Để lấy truy vấn thì ta có thể nhảy từ **u** lên vị trí tổ tiên gần **r** nhất (mất $O(\log)$) sau đó tính toán lấy từ chỗ tổ tiên đó tới vị trí của **r** (mất $O(1)$)
**AC code nè**: $O((n + q) \cdot \log)$
```cpp
#include <bits/stdc++.h>
#define id1 first
#define id2 second
#define fastIO ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
#define open_file(name) freopen(name".INP","r", stdin); freopen(name".OUT","w", stdout);
#define foru(i,index_begin,index_end) for (int i=index_begin;i<=index_end;i++)
#define ford(i,index_begin,index_end) for (int i=index_begin;i>=index_end;i--)
#define name "TENJOKE"
#define el '\n'
using namespace std;
const long long maxn = 2e5 + 9, mod = 1e9 + 7, inf = 1e18, joker = 18;
int n, q, par[maxn][joker + 1];
long long a[maxn], f[maxn][joker + 1], s[maxn];
void input()
{
cin >> n >> q;
foru(i,1,n) cin >> a[i];
}
void binary_lifting()
{
stack<int> st; st.push(n + 1); a[n + 1] = inf;
ford(i,n,1)
{
while (a[st.top()] <= a[i]) st.pop();
par[i][0] = st.top(); st.push(i);
}
foru(u,1,n)
{
int v = par[u][0], len; long long S;
if (v == u + 1) continue;
S = s[v - 1] - s[u - 1];
len = v - u;
f[u][0] = len * a[u] - S;
}
foru(i,1,joker) foru(u,1,n) {
int mid = par[u][i - 1];
if (mid <= n)
{
par[u][i] = par[mid][i - 1];
f[u][i] = f[u][i - 1] + f[mid][i - 1];
}
else
{
par[u][i] = n + 1;
f[u][i] = f[u][i - 1];
}
}
}
long long Get(int l, int r)
{
long long res = 0;
ford(i,joker,0)
{
if (par[l][i] <= r)
{
res += f[l][i];
l = par[l][i];
}
}
if (l < r) res += (r - l) * a[l] - (s[r] - s[l]);
return res;
}
void s_p()
{
foru(i,1,n) s[i] = s[i - 1] + a[i];
binary_lifting();
}
void output()
{
foru(test,1,q)
{
int l, r; cin >> l >> r;
cout << Get(l, r) << el;
}
}
int main()
{
fastIO;
//open_file(name)
input();
s_p();
output();
return 0;
}
//be lan xinh nhat
TENJOKE
Created at
0 likes