PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Ildar Gainullin
Tester: Suchan Park
Editorialist: William Lin
DIFFICULTY:
Hard
PREREQUISITES:
PROBLEM:
You are given a permutation p. A subarray p[l, r] is interesting if \max(p[l, r])-\min(p[l, r])=r-l. Find the number of pairs of non-containing interesting subarrays such that both subarrays have \ge X elements in common. Two subarrays are non-containing if there exists an element of the first subarray which is not in the second subarray and there exists an element of the second subarray which is not in the first subarray.
QUICK EXPLANATION:
Build the Divide-Combine Tree for p. Note that the intersection of two interesting subarrays is also an interesting subarray, and the intersection must correspond to a range of children of a combine node. The two interesting subarrays must also be a range of children of the same combine node. Our problem reduces to the following (A_i is the length of child i): given an array A, find the number of non-containing pairs of subarrays such that their intersection has a sum \ge X, which can be solved easily with two-pointers.
EXPLANATION:
Observation 1. An alternate definition for an interesting subarray: A subarray is interesting if for any a\le b\le c such that a and c are both in the subarray, b is also in the subarray.
Proof
A subarray p[l, r] has r-l+1 elements and there are \max(p[l, r])-\min(p[l, r])+1 values between \min(p[l, r]) and \max(p[l, r]). Since each value only appears once in the permutation, if \max(p[l, r])-\min(p[l, r])=r-l, it means that all values between \min(p[l, r]) and \max(p[l, r]) appear in the subarray, which satisfies the alternative definition.
On the other hand, if \max(p[l, r])-\min(p[l, r])>r-l, at least one element between \min(p[l, r]) and \max(p[l, r]) which is not \min(p[l, r]) or \max(p[l, r]) will not be in the subarray (we cannot fit more than r-l+1 values in a subarray of size r-l+1), which doesn’t satisfy the alternative definition. Note that \max(p[l, r])-\min(p[l, r])<r-l cannot occur since we need at least r-l+1 values in the subarray.
Observation 2. The intersection of two interesting subarrays is also an interesting subarray.
Proof
We will prove this by contradiction. Let the minimum value in the intersection be a and the maximum value in the intersection be b. Since the intersection is not interesting, there is some value x between a and b that does not occur in the intersection.
Since the two subarrays are interesting, they must both contain x. Since all values are distinct in p, x can only be in the intersection of the two subarrays, which is a contradiction.
In the divide-combine tree of p, interesting subarrays are represented by all nodes (type A) and subarrays of children of combine nodes which have more than one child and do not contain all children (type B).
Observation 3. Two subarrays of both type A cannot form a pair of non-containing subarrays that intersect.
Proof
The subarrays will only intersect if the node corresponding to one subarray is an ancestor of the node corresponding to the other subarray. But in that case, the subarray of the ancestor will contain the entire subarray of the descendant.
Observation 4. Two subarrays of type A and type B cannot form a pair of non-containing subarrays that intersect.
Proof
Let’s say the subarray of type A corresponds to node u and the subarray of type B corresponds to the subarray of children of combine node v. If u and v are not ancestors of each other, then there is no intersection. If u is an ancestor of v (including v), since u completely contains v and v completely contains any subarray of its children, the subarrays are not non-containing. If v is an ancestor of u (not including u), then u is completely contained in one child of v. That child is either completely inside the subarray of children or completely outside of it, so it’s impossible for the pair of subarrays to be non-containing and intersecting at the same time.
The only case left is the case with two subarrays of type B. Note that they should be from the same combine node u or else they can’t intersect, so let’s iterate over all combine nodes u. Let’s say the children of u correspond to subarrays of length l_1, l_2, \dots, l_m. If the first subarray has the children in the range [a, c] and the second subarray has the children in the range [b, d], then we want a< b\le c< d and l_b+l_{b+1}+\dots+l_c \ge X.
The number of such (a, b, c, d) can be computed with many methods such as two-pointers. Let’s iterate over b while maintaining the minimum c such that l_b+l_{b+1}+\dots+l_c \ge X. a has to satisfy 1\le a < b, giving b-1 choices. c and d have to satisfy b \le c < d \le m, giving \frac{(m-b+1)(m-b)}{2} choices. In total, we add (b-1)\frac{(m-b+1)(m-b)}{2} to the answer.
The final time complexity is O(N \log N) (which comes from building the divide-combine tree).
SOLUTIONS:
Setter's Solution
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
using namespace std;
typedef long long ll;
#ifdef iq
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
#define rg register
using namespace std;
const int N = 600010;
const int MOD = 998244353;
int n, x, a[N], st1[N], st2[N], tp1, tp2, rt;
int L[N], R[N], M[N], id[N], cnt, typ[N], bin[20], st[N], tp;
//æ�¬ç¯�代ç �å��é¢�åº�为 CERC2017 Intrinsic Interval
// aæ�°ç»�å�³ä¸ºå��é¢�ä¸å¯¹åº�ç��æ��å��
// st1å��st2å��å�«ä¸¤ä¸ªå��è°�æ �ï¼�tp1ã��tp2为对åº�ç��æ �顶ï¼�rt为æ��å��æ �ç��æ ¹
// Lã��Ræ�°ç»�表示该æ��å��æ �è��ç�¹ç��å·¦å�³ç«¯ç�¹ï¼�Mæ�°ç»�ç��ä½�ç�¨å�¨æ��å��æ �æ��é� æ�¶æ��æ��å�°
// idå�å�¨ç��æ�¯æ��å��ä¸æ��ä¸�ä½�置对åº�ç��è��ç�¹ç¼�å�·ï¼�typç�¨äº�æ �è®°æ��ç�¹è¿�æ�¯å��ç�¹
// st为å�å�¨æ��å��æ �è��ç�¹ç¼�å�·ç��æ �ï¼�tp为å�¶æ �顶
struct RMQ { // ��� RMQ�Max & Min�
int lg[N], mn[N][20], mx[N][20];
void chkmn(int& x, int y) {
if (x > y) x = y;
}
void chkmx(int& x, int y) {
if (x < y) x = y;
}
void build() {
for (int i = bin[0] = 1; i < 20; ++i) bin[i] = bin[i - 1] << 1;
for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
for (int i = 1; i <= n; ++i) mn[i][0] = mx[i][0] = a[i];
for (int i = 1; i < 20; ++i)
for (int j = 1; j + bin[i] - 1 <= n; ++j)
mn[j][i] = min(mn[j][i - 1], mn[j + bin[i - 1]][i - 1]),
mx[j][i] = max(mx[j][i - 1], mx[j + bin[i - 1]][i - 1]);
}
int ask_mn(int l, int r) {
int t = lg[r - l + 1];
return min(mn[l][t], mn[r - bin[t] + 1][t]);
}
int ask_mx(int l, int r) {
int t = lg[r - l + 1];
return max(mx[l][t], mx[r - bin[t] + 1][t]);
}
} D;
// 维� L_i
struct SEG { // 线段æ �
#define ls (k << 1)
#define rs (k << 1 | 1)
int mn[N << 1], ly[N << 1]; // å�ºé�´å� ï¼�å�ºé�´æ��å°�å�¼
void pushup(int k) { mn[k] = min(mn[ls], mn[rs]); }
void mfy(int k, int v) { mn[k] += v, ly[k] += v; }
void pushdown(int k) {
if (ly[k]) mfy(ls, ly[k]), mfy(rs, ly[k]), ly[k] = 0;
}
void update(int k, int l, int r, int x, int y, int v) {
if (l == x && r == y) {
mfy(k, v);
return;
}
pushdown(k);
int mid = (l + r) >> 1;
if (y <= mid)
update(ls, l, mid, x, y, v);
else if (x > mid)
update(rs, mid + 1, r, x, y, v);
else
update(ls, l, mid, x, mid, v), update(rs, mid + 1, r, mid + 1, y, v);
pushup(k);
}
int query(int k, int l, int r) { // 询� 0 ��置
if (l == r) return l;
pushdown(k);
int mid = (l + r) >> 1;
if (!mn[ls])
return query(ls, l, mid);
else
return query(rs, mid + 1, r);
// å¦�æ��ä¸�å�å�¨ 0 ç��ä½�置就ä¼�è�ªå�¨è¿�å��å½�å��ä½ æ�¥è¯¢ç��ä½�ç½®
}
} T;
int o = 1, hd[N];
struct Edge {
int v, nt;
} E[N << 1];
void add(int u, int v) { // æ �ç»�æ��å� è¾¹
E[o] = (Edge){v, hd[u]};
hd[u] = o++;
}
ll ans = 0;
ll fenw[N];
void inc(int x, int y) {
for (; x < N; x = (x | (x + 1))) {
fenw[x] += y;
}
}
ll get(int x) {
ll ok = 0;
for (; x >= 0; x = (x & (x + 1)) - 1) {
ok += fenw[x];
}
return ok;
}
void dfs(int u) {
if (typ[u]) {
vector <int> lens;
for (int i = hd[u]; i; i = E[i].nt) {
lens.push_back(R[E[i].v] - L[E[i].v] + 1);
}
int ret = 0;
vector <pair <int, int> >undo;
for (int i = 0; i < (int) lens.size(); i++) {
ret += lens[i];
ll f = get(ret - x) % MOD;
int b = (int) lens.size() - 1 - i;
ans += (f * b) % MOD;
if (ans >= MOD) ans -= MOD;
undo.push_back({ret, i + 1});
inc(ret, i + 1);
}
for (auto c : undo) {
inc(c.first, -c.second);
}
/*
for (int i = 0; i < (int) lens.size(); i++) {
int sum = 0;
for (int j = i; j < (int) lens.size(); j++) {
sum += lens[j];
if (sum >= x) {
int a = i, b = (int) lens.size() - 1 - j;
ans += (a * (ll) b) % MOD;
if (ans >= MOD) ans -= MOD;
}
}
}
*/
}
for (int i = hd[u]; i; i = E[i].nt) {
int v = E[i].v;
dfs(v);
}
}
// å�¤æ�å½�å��å�ºé�´æ�¯å�¦ä¸ºè¿�ç»æ®µ
bool judge(int l, int r) { return D.ask_mx(l, r) - D.ask_mn(l, r) == r - l; }
// 建æ �
void build() {
for (int i = 1; i <= n; ++i) {
// å��è°�æ �
// ��� [st1[tp1-1]+1,st1[tp1]] ����就� a[st1[tp1]]
// ç�°å�¨æ��å®�å�ºæ �ï¼�æ��å�³ç��è¦�æ��å¤�å��æ��ç�� Min å� å��æ�¥ã��
// 线段æ �ç��å�¶ç»�ç�¹ä½�ç½® j ç»´æ�¤ç��æ�¯ä»� j å�°å½�å��ç�� i ç��
// Max{j,i}-Min{j,i}-(i-j)
// å�ºé�´å� å�ªæ�¯ä¸�个 Tagã��
// ç»´æ�¤å��è°�æ �ç��ç�®ç��æ�¯è¾�å�©çº¿æ®µæ �ä»� i-1 æ�´æ�°å�° iã��
// ��� i ������询������������解
while (tp1 && a[i] <= a[st1[tp1]]) // å��è°�é��å¢�ç��æ �ï¼�ç»´æ�¤ Min
T.update(1, 1, n, st1[tp1 - 1] + 1, st1[tp1], a[st1[tp1]]), tp1--;
while (tp2 && a[i] >= a[st2[tp2]])
T.update(1, 1, n, st2[tp2 - 1] + 1, st2[tp2], -a[st2[tp2]]), tp2--;
T.update(1, 1, n, st1[tp1] + 1, i, -a[i]);
st1[++tp1] = i;
T.update(1, 1, n, st2[tp2] + 1, i, a[i]);
st2[++tp2] = i;
id[i] = ++cnt;
L[cnt] = R[cnt] = i; // ��� L,R ��������
int le = T.query(1, 1, n), now = cnt;
while (tp && L[st[tp]] >= le) {
if (typ[st[tp]] && judge(M[st[tp]], i)) {
// å�¤æ�æ�¯å�¦è�½æ��为å�¿å�ï¼�å¦�æ��è�½å°±å��
R[st[tp]] = i, add(st[tp], now), now = st[tp--];
} else if (judge(L[st[tp]], i)) {
typ[++cnt] = 1; // å��ç�¹ä¸�å®�æ�¯è¢«è¿�æ ·å»ºå�ºæ�¥ç��
L[cnt] = L[st[tp]], R[cnt] = i, M[cnt] = L[now];
//è¿�é��Mæ�°ç»�ç��ä½�ç�¨æ�¯ä¿�è¯�å��ç�¹ç��å�¿å�æ��å��æ�¯å��è°�ç��
add(cnt, st[tp--]), add(cnt, now);
now = cnt;
} else {
add(++cnt, now); // æ�°å»ºä¸�个ç»�ç�¹ï¼�æ�� now æ·»å� 为å�¿å�
// å¦�æ��ä»�å½�å��ç»�ç�¹å¼�å§�ä¸�è�½æ��æ��è¿�ç»æ®µï¼�å°±å��并ã��
// ç�´å�°æ�¾å�°ä¸�个ç»�ç�¹è�½æ��æ��è¿�ç»æ®µã��è��ä¸�æ��们ä¸�å®�è�½æ�¾å�°è¿�æ ·
// �个���
do
add(cnt, st[tp--]);
while (tp && !judge(L[st[tp]], i));
L[cnt] = L[st[tp]], R[cnt] = i, add(cnt, st[tp--]);
now = cnt;
}
}
st[++tp] = now; // å¢�é��ç»�æ��ï¼�æ��å½�å��ç�¹å�§æ �
T.update(1, 1, n, 1, i, -1); // å� 为å�ºé�´å�³ç«¯ç�¹å��å��移å�¨ä¸�æ ¼ï¼�å� æ¤æ�´ä½� -1
}
rt = st[1]; // æ �ä¸æ��å��å�©ä¸�ç��ç�¹æ�¯æ ¹ç»�ç�¹
}
int main() {
#ifdef iq
freopen("a.in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin >> n >> x;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
D.build();
build();
dfs(rt);
cout << (2 * ans) % MOD << endl;
return 0;
}
Tester's Solution
//
// Created by ��찬 on 2020/02/22.
//
#include <bits/stdc++.h>
namespace {
const int BUFFER_SIZE = int(1.1e5);
char _buf[BUFFER_SIZE + 10];
int _buf_pos, _buf_len;
char seekChar() {
if(_buf_pos >= _buf_len) {
_buf_len = fread(_buf, 1, BUFFER_SIZE, stdin);
_buf_pos = 0;
}
assert(_buf_pos < _buf_len);
return _buf[_buf_pos];
}
bool seekEof() {
if(_buf_pos >= _buf_len) {
_buf_len = fread(_buf, 1, BUFFER_SIZE, stdin);
_buf_pos = 0;
}
return _buf_pos >= _buf_len;
}
char readChar() {
char ret = seekChar();
_buf_pos++;
return ret;
}
int readInt(int lb, int rb) {
char c = readChar();
int mul = 1;
if(c == '-') {
c = readChar();
mul = -1;
}
assert(isdigit(c));
long long ret = c - '0';
char first_digit = c;
int len = 0;
while(!seekEof() && isdigit(seekChar()) && ++len <= 19) {
ret = ret * 10 + readChar() - '0';
}
ret *= mul;
if(len >= 2) assert(first_digit != '0');
assert(len <= 18);
assert(lb <= ret && ret <= rb);
return (int)ret;
}
void readEoln() {
char c = readChar();
assert(c == '\n');
//assert(c == '\n' || (c == '\r' && readChar() == '\n'));
}
void readSpace() {
char c = readChar();
assert(c == ' ');
}
}
const int MOD = 998244353;
namespace Solver {
struct PermutationIntervalChecker {
std::vector<int> lg2;
std::vector<std::vector<int>> min, max;
int n;
public:
explicit PermutationIntervalChecker(const std::vector<int> &a) {
n = a.size();
lg2.resize(n + 1);
for(int i = 2; i <= n; i++) lg2[i] = lg2[i>>1] + 1;
min.resize(lg2[n]+1, std::vector<int>(n));
max.resize(lg2[n]+1, std::vector<int>(n));
min[0] = a;
max[0] = a;
for(int k = 0; k < lg2[n]; k++) {
for(int i = 0; i + (2 << k) - 1 < n; i++) {
min[k + 1][i] = std::min(min[k][i], min[k][i + (1<<k)]);
max[k + 1][i] = std::max(max[k][i], max[k][i + (1<<k)]);
}
}
}
bool is_interesting (int l, int r) {
int k = lg2[r - l + 1];
return std::max(max[k][l], max[k][r - (1<<k) + 1]) - std::min(min[k][l], min[k][r - (1<<k) + 1]) == r - l;
}
};
class LazySegmentTree {
typedef int T1; // Change this to what you need
typedef int T2; // Change this to what you need
T1 id = 0, initval = 0;
T2 unused = 0;
T1 combine(T1 a, T1 b){ return std::min(a, b); }
T2 combineL(T2 a, T2 b){ return a + b; }
void unlazy(int i, int nl, int nr){ arr[i] += lazy[i]; }
int n; std::vector<T1> arr; std::vector<T2> lazy;
void propagate(int x, int nl, int nr){
if(lazy[x] == unused) return;
if(x < n){
lazy[x*2] = combineL(lazy[x*2], lazy[x]);
lazy[x*2+1] = combineL(lazy[x*2+1], lazy[x]);
}
unlazy(x, nl, nr);
lazy[x] = unused;
}
void update(int l,int r,T2 val,int x,int nl,int nr){
propagate(x, nl, nr);
if(r < nl || nr < l) return;
if(l <= nl && nr <= r){
lazy[x] = combineL(lazy[x], val);
propagate(x, nl, nr);
return;
}
int mid = (nl + nr) / 2;
update(l,r,val,x*2,nl,mid);
update(l,r,val,x*2+1,mid+1,nr);
arr[x] = combine(arr[x*2], arr[x*2+1]);
}
T1 query(int l,int r,int x,int nl,int nr){
propagate(x, nl, nr);
if(r < nl || nr < l) return id;
if(l <= nl && nr <= r) return arr[x];
int mid = (nl + nr) / 2;
return combine(query(l,r,x*2,nl,mid),
query(l,r,x*2+1,mid+1,nr));
}
int find_zero(int x, int nl, int nr) {
if(nl == nr) return nl;
propagate(x, nl, nr);
int mid = (nl + nr) / 2;
if(arr[x*2] + lazy[x*2] == 0) {
return find_zero(x*2, nl, mid);
}else {
return find_zero(x*2+1, mid+1, nr);
}
}
public:
explicit LazySegmentTree(int sz) {
n = 1;
while(n < sz) n *= 2;
arr.resize(n*2, initval); lazy.resize(n*2, unused);
}
void update(int l,int r,T2 val)
{update(l,r,val,1,0,n-1);}
int find_zero() {
return find_zero(1, 0, n-1);
}
};
enum NODE_TYPE { ANALYTIC, CONVERGE };
struct Node {
int l, r, m;
NODE_TYPE type = ANALYTIC;
std::vector<std::reference_wrapper<Node>> children;
};
class PermutationTree {
std::vector<Node> tree;
std::vector<int> id;
int n;
Node root;
long long dfs (Node &node, int x) {
long long ret = 0;
for(Node &child : node.children) {
ret += dfs(child, x);
}
if(node.type == CONVERGE) {
struct State { int cl, cr, len; };
std::vector<State> states;
int cl = 0, cr = node.children.size() - 1;
for(Node &child : node.children) {
states.push_back({ cl, cr, child.r - child.l + 1 });
cl += 1;
cr -= 1;
}
for(int i = 0, j = 0, len = 0, sumcl = 0; j < states.size(); j++) {
len += states[j].len;
while(i <= j && len >= x) {
len -= states[i].len;
(sumcl += states[i].cl) %= MOD;
i++;
}
ret += 1ll * sumcl * states[j].cr % MOD;
}
}
ret %= MOD;
return ret;
}
public:
explicit PermutationTree (const std::vector<int> &p) {
n = p.size();
PermutationIntervalChecker checker(p);
LazySegmentTree seg(n); // For each j, contains {max(p[j..i]) - min(p[j..i])} - {i-j}
std::stack<int> stkMin, stkMax;
std::stack<std::reference_wrapper<Node>> stkPath;
tree.reserve(n*2);
id.resize(n);
for(int i = 0; i < n; i++) {
auto processHistogram = [&](std::stack<int> &stk, int coef) {
while(!stk.empty() && (p[i] - p[stk.top()]) * coef > 0) {
int r = stk.top(); stk.pop();
int l = (stk.empty() ? -1 : stk.top()) + 1;
seg.update(l, r, -coef * p[r]);
}
int l = (stk.empty() ? -1 : stk.top()) + 1;
seg.update(l, i, coef * p[i]);
stk.push(i);
};
processHistogram(stkMax, +1);
processHistogram(stkMin, -1);
id[i] = tree.size();
tree.push_back({i, i});
int le = seg.find_zero();
std::reference_wrapper<Node> cur = tree.back();
while(!stkPath.empty() && stkPath.top().get().l >= le) {
Node &node = stkPath.top();
if(node.l < le) break;
if(node.type == CONVERGE && checker.is_interesting(node.m, i)) {
node.r = i;
node.children.push_back(cur);
cur = node;
stkPath.pop();
}else if(checker.is_interesting(node.l, i)) {
tree.push_back({node.l, i, cur.get().l, CONVERGE, {node, cur}});
stkPath.pop();
cur = tree.back();
}else {
tree.push_back({});
Node &new_node = tree.back();
new_node.children.push_back(cur);
do {
new_node.children.push_back(stkPath.top());
stkPath.pop();
}while(!stkPath.empty() && !checker.is_interesting(stkPath.top().get().l, i));
assert(!stkPath.empty());
new_node.l = stkPath.top().get().l;
new_node.r = i;
new_node.type = ANALYTIC;
new_node.children.push_back(stkPath.top());
stkPath.pop();
cur = new_node;
}
}
stkPath.push(cur);
seg.update(0, i, -1);
}
while(stkPath.size() > 1) stkPath.pop();
assert(stkPath.size() == 1);
root = stkPath.top();
}
int solve(int x) {
return dfs(root, x) % MOD;
}
};
int solve (const std::vector<int>& p, int x) {
PermutationTree tree(p);
return tree.solve(x);
}
};
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
int N = readInt(1, 300000);
readSpace();
int X = readInt(1, N);
readEoln();
std::vector<int> p(N);
std::vector<bool> used(N);
for(int i = 0; i < N; i++) {
p[i] = readInt(1, N) - 1;
if(i+1 < N) readSpace(); else readEoln();
assert(!used[p[i]]);
used[p[i]] = true;
}
assert(feof(stdin));
printf("%d\n", Solver::solve(p, X) * 2 % MOD);
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
const int mxN=3e5, M=998244353;
int n, x, ans;
struct dct {
int p[mxN], nb[mxN], ns[mxN], st1[4*mxN], st2[4*mxN], lz[4*mxN], st[mxN], s, l[2*mxN], r[2*mxN], rt;
bool t[2*mxN];
vector<int> c[2*mxN];
void app(int i, int x) {
st1[i]+=x;
lz[i]+=x;
}
void psh(int i) {
app(2*i, lz[i]);
app(2*i+1, lz[i]);
lz[i]=0;
}
void cmb(int i) {
if(st1[2*i]<=st1[2*i+1]) {
st1[i]=st1[2*i];
st2[i]=st2[2*i];
} else {
st1[i]=st1[2*i+1];
st2[i]=st2[2*i+1];
}
}
void upd(int l1, int r1, int x, int i=1, int l2=0, int r2=n-1) {
if(l1<=l2&&r2<=r1) {
app(i, x);
return;
}
int m2=(l2+r2)/2;
psh(i);
if(l1<=m2)
upd(l1, r1, x, 2*i, l2, m2);
if(m2<r1)
upd(l1, r1, x, 2*i+1, m2+1, r2);
cmb(i);
}
int qry(int l1, int i=1, int l2=0, int r2=n-1) {
if(l2==r2)
return st1[i];
int m2=(l2+r2)/2;
psh(i);
return l1<=m2?qry(l1, 2*i, l2, m2):qry(l1, 2*i+1, m2+1, r2);
}
void bld2(int i=1, int l2=0, int r2=n-1) {
if(l2==r2) {
st1[i]=l2;
st2[i]=l2;
return;
}
int m2=(l2+r2)/2;
bld2(2*i, l2, m2);
bld2(2*i+1, m2+1, r2);
cmb(i);
}
void bld(int n) {
bld2();
for(int i=0, sth=0; i<n; ++i) {
for(nb[i]=i-1; ~nb[i]&&p[nb[i]]<p[i]; nb[i]=nb[nb[i]])
upd(nb[nb[i]]+1, nb[i], p[i]-p[nb[i]]);
for(ns[i]=i-1; ~ns[i]&&p[ns[i]]>p[i]; ns[i]=ns[ns[i]])
upd(ns[ns[i]]+1, ns[i], p[ns[i]]-p[i]);
int u=s++;
l[u]=r[u]=i;
while(sth&&st2[1]<=l[st[sth-1]]) {
if(t[st[sth-1]]&&qry(l[c[st[sth-1]][1]])<=i) {
r[st[sth-1]]=i;
c[st[sth-1]].push_back(u);
u=st[--sth];
} else if(qry(l[st[sth-1]])<=i) {
t[s]=1;
l[s]=l[st[sth-1]];
r[s]=i;
c[s].push_back(st[--sth]);
c[s].push_back(u);
u=s++;
} else {
c[s].push_back(u);
do
c[s].push_back(st[--sth]);
while(qry(l[st[sth]])>i);
l[s]=l[st[sth]];
r[s]=i;
u=s++;
}
}
st[sth++]=u;
}
rt=st[0];
}
} dct;
void dfs(int u=dct.rt) {
if(dct.t[u]) {
//combine node
//find length of children
vector<int> w;
for(int v : dct.c[u])
w.push_back(dct.r[v]-dct.l[v]+1);
//fix the start of the intersection
//use 2 pointers to find minimum end of the intersection
for(int i=0, j=0, y=0; ; ++i) {
while(j<w.size()&&y<x)
y+=w[j++];
if(y<x)
break;
ans=(ans+(long long)i*(w.size()-j)*(w.size()-j+1)/2)%M;
y-=w[i];
}
}
for(int v : dct.c[u])
dfs(v);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
//input
cin >> n >> x;
for(int i=0; i<n; ++i)
cin >> dct.p[i];
//main
dct.bld(n);
dfs();
//output
cout << 2*ans%M;
}
SIMILAR PROBLEMS:
Please give me suggestions if anything is unclear so that I can improve. Thanks 
