Description：

给定 $n,k,$ 序列 $a$ ，记 $\begin{align}f(l,r)=\sum_{i=l}^{r}a_i-max_{i=l}^r{\ a_i}\end{align}$

求满足 $1\le l < r \le n$ ， $k|f(l,r)$ 的整数对 $(l,r)$ 的数量。

$1\le n \le 3\times 10^5$

Solution：

考虑分治，用数据结构求出 $[l,r]$ 中的最大值 $a_p$ ，则对于所有 $l \le p\le r$ 的区间，最大值都是 $a_p$ ，可以枚举较小的一边，假如枚举左边，设边界为 $l_p$ ，那么问题就变成了询问有多少 $r_p\in[p,r]$ 满足 $k|sum[r]-sum[l-1]-a_p$ ，即 $(sum[r]-sum[l-1]-a_p)\%k=0$ ，移项得 $sum[r]=sum[l-1]+a_p(mod\ k)$ ，如果枚举右边，那么问题变成了有多少 $l\in[l,p]$ 满足 $(sum[r] - sum[l - 1]-a_p)\%k=0$ ，即 $sum[l-1]=sum[r]-a_p(mod\ k)$ ，于是问题又变成了询问 $[l,r]$ 中 $sum[p]\%k=w$ 的数有多少，可以离线后开一个桶，并记录每个询问对答案是增加还是减少即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 300010

int a[MAXN];

int sum[MAXN];

struct node

{

	int lc,rc;

	int p;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r){t[rt].p = l;return;}

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	if(a[t[t[rt].rc].p] > a[t[t[rt].lc].p])t[rt].p = t[t[rt].rc].p;

	else t[rt].p = t[t[rt].lc].p;

	return;

}

int query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].p;

	int res = 0;

	if(L <= mid)

	{

		int p = query(t[rt].lc,L,R,l,mid);

		if(a[p] > a[res])res = p;

	}

	if(R > mid)

	{

		int p = query(t[rt].rc,L,R,mid + 1,r);

		if(a[p] > a[res])res = p;

	}

	return res;

}

struct quer

{

	int p,k,type;

}q[MAXN * 30];

int qnum = 0;

void add(int l,int r,int k)

{

	++qnum;q[qnum].k = k;q[qnum].type = 1;q[qnum].p = r;

	if(l != 0){++qnum;q[qnum].k = k;q[qnum].type = -1;q[qnum].p = l - 1;}

	return;

}

bool cmp(quer a,quer b){return a.p < b.p;}

void divide(int l,int r)

{

	if(l >= r)return;

	int p = query(root,l,r,1,n);

	divide(l,p - 1);divide(p + 1,r);

	if(p - l + 1 < r - p + 1)

		for(int i = l;i <= p;++i)

			add(max(i + 1,p),r,(sum[i - 1] + a[p] % k) % k);

	else

		for(int i = p;i <= r;++i)

			add(l - 1,min(p - 1,i - 2),(sum[i] - (a[p] % k) + k) % k);

	return;

}

typedef long long ll;

int basket[1000000];

int work()

{

	int ans = 0;

	sort(q + 1,q + 1 + qnum,cmp);

	memset(basket,0,sizeof(basket));

	for(int i = 0,cur = 1;cur <= qnum;)

	{

		if(i <= q[cur].p)

		{

			basket[sum[i] % k]++;

			++i;

		}

		else

		{

			ans += q[cur].type * basket[q[cur].k];

			++cur;

		}

	}

	return ans;

}

int main()

{

	freopen("interval.in","r",stdin);

	freopen("interval.out","w",stdout);

	scanf("%d%d",&n,&k);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(int i = 1;i <= n;++i)sum[i] = (sum[i - 1] + a[i]) % k;

	build(root,1,n);

	divide(1,n);

	printf("%d\n",work());

	fclose(stdin);

	fclose(stdout);

	return 0;

}