上海市计算机学会竞赛平台2025年5月月赛丙组稳定区间

题目描述

Carol 有一个长度为 nn 的数组 aa，他定义函数 f(l,r)=∑i=lr−1(ai−ai+1)f(l,r)=∑i=lr−1​(ai​−ai+1​)，其中 1≤l≤r≤n1≤l≤r≤n，特殊地，f(i,i)f(i,i) 定义为 00。

如果 f(l,r)≠(ar−al)f(l,r)​=(ar​−al​)，则称一个子区间 [l,r](1≤l≤r≤n)[l,r](1≤l≤r≤n) 是不稳定的。

Carol 想知道数组 aa 有多少个不稳定的子数组。

输入格式

第一行一个整数 TT 表示数据组数，对于每组数据：

第一行一个整数 nn 表示数组长度。

第二行 nn 个整数 a1,a2,…,ana1​,a2​,…,an​ 表示数组 aa。

输出格式

对于每组数据，输出一行一个整数表示答案。

数据范围

对于 30%30% 的数据，∑n≤1000∑n≤1000，0≤ai≤10≤ai​≤1。

对于 60%60% 的数据，∑n≤105∑n≤105，0≤ai≤10≤ai​≤1。

对于 100%100% 的数据，1≤T≤1051≤T≤105，n≥1n≥1，∑n≤105∑n≤105，0≤ai≤1090≤ai​≤109。

样例数据

输入:

3
3
10 20 30
4
1 2 1 2
5
1 2 3 4 5

输出:

3
4
10

说明:

对于第一组数据，子区间[1,2],[2,3],[1,3]都是不稳定的。

详见代码：

#include <bits/stdc++.h>
using namespace std;
map <int,int> mp;
long long t,n,a;
int main()
{cin>>t;while(t--){mp.clear();cin>>n;long long cnt=0;for(int i=1;i<=n;i++){cin>>a;cnt+=mp[a];mp[a]++;}cout<<n*(n-1)/2-cnt<<endl;}return 0;
}