第一次知道单调栈搞出来的区间也能启发式合并。。。

你把它想想成一个树的形式， 可以发现确实可以启发式合并。

#include
     
      #define LL long long#define fi first#define se second#define mk make_pair#define PII pair
      
       #define PLI pair
       
        #define ull unsigned long longusing namespace std;const int N = 3e5 + 7;const int inf = 0x3f3f3f3f;const LL INF = 0x3f3f3f3f3f3f3f3f;const int mod = 1e9 + 7;const double eps = 1e-8;int n, k, tot, a[N], stk[N], L[N], R[N], sum[N];vector
        
          num[1000007];void add(int &a, int b) {    a += b; if(a >= mod) a -= mod;}int cal(int x, int l, int r) {    auto it1 = upper_bound(num[x].begin(), num[x].end(), r);    auto it2 = lower_bound(num[x].begin(), num[x].end(), l);    return it1 - it2;}int main() {    scanf("%d%d", &n, &k);    num[0].push_back(0);    for(int i = 1; i <= n; i++) {       scanf("%d", &a[i]);       sum[i] = (sum[i-1]+a[i]%k)%k;       num[sum[i]].push_back(i);    }    a[0] = a[n+1] = inf;    stk[++tot] = 0;    for(int i = 1; i <= n; i++) {        while(tot && a[stk[tot]] < a[i]) tot--;        L[i] = stk[tot];        stk[++tot] = i;    }    tot = 0;    stk[++tot] = n+1;    for(int i = n; i >= 1; i--) {        while(tot && a[stk[tot]] <= a[i]) tot--;        R[i] = stk[tot];        stk[++tot] = i;    }    LL ans = 0;    for(int i = 1; i <= n; i++) {        if(i - L[i] < R[i] - i) {            for(int j = L[i]; j < i; j++)                ans += cal((sum[j]+a[i])%k, i, R[i]-1);        } else {            for(int j = i; j < R[i]; j++) {                ans += cal((sum[j]-(a[i]%k)+k)%k, L[i], i-1);            }        }    }    printf("%lld\n", ans - n);    return 0;}/**/