GOODSEGS - Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author: Ildar Gainullin
Tester: Suchan Park
Editorialist: William Lin

DIFFICULTY:

Hard

PREREQUISITES:

Divide-Combine Tree

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 :slight_smile:

3 Likes

The Good Segs Guide.

https://codeforces.com/problemset/problem/526/F this is the similar category problem if you want to add. And very good explanation of its editorial https://www.cnblogs.com/yyf0309/p/7498514.html ( translate it)

1 Like

@tmwilliamlin can you please make a video on Divide and Combine Tree?
The code mentioned in the link is a bit difficult to understand.
Thanks

2 Likes

Not sure, I have other priorities now

1 Like

See the question and link I posted , you will get a much better explanation. It’s the exact same question and explained a lot easier.

Editorial finished and updated!

2 Likes

Come on, the most important thing is that special tree structure and you give us a link to Chinese website…

9 Likes

There is literally no other source. Both the setter and the tester (who are not Chinese) learned from it.

1 Like

If you are the real errichto you have another topic for your youtube tutorials :wink:
By sure, I would be watching it

3 Likes

How to solve ARMYOFME using this DCT?? @tmwilliamlin @ssjgz can you please give some hint?? I mean once I have this tree, how do I answer a query in O(log(N)) ?

This is a really good problem but I’m finding it really hard to understand the approach or even the suggested data structure divide-combine-tree. The translated page of the suggested link is not translated properly and it’s very difficult to understand. I request @tmwilliamlin, @nvdrag_123, @errichto or someone can please just at least shed some light on this mysterious data structure divide-combine-tree. Maybe the rest of us should be able to pick it up from there. @errichto of you did make a video on it be sure I’d be watching it;)