526互联

Contrast Value

发布时间 2023-07-10 18:22:33作者: o-Sakurajimamai-o

# Contrast Value

## 题面翻译

定义序列 $a_1,a_2,\dots,a_n$ 的权值是
$|a_1-a_2|+|a_2-a_3|+\dots+|a_{n-1}-a_n|$。

$T$ 次询问，每次给一个序列 $a$ ，一个 $a$ 的子序列 $b$ 合法当且仅当 $b$ 权值和 $a$ 相等，求 $b$ 的最小长度。

## 题目描述

For an array of integers $ [a_1, a_2, \dots, a_n] $ , let's call the value $ |a_1-a_2|+|a_2-a_3|+\cdots+|a_{n-1}-a_n| $ the contrast of the array. Note that the contrast of an array of size $ 1 $ is equal to $ 0 $ .

You are given an array of integers $ a $ . Your task is to build an array of $ b $ in such a way that all the following conditions are met:

- $ b $ is not empty, i.e there is at least one element;
- $ b $ is a subsequence of $ a $ , i.e $ b $ can be produced by deleting some elements from $ a $ (maybe zero);
- the contrast of $ b $ is equal to the contrast of $ a $ .

What is the minimum possible size of the array $ b $ ?

## 输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 3 \cdot 10^5 $ ) — the size of the array $ a $ .

The second line contains $ n $ integers $ a_1, a_2, \cdot, a_n $ ( $ 0 \le a_i \le 10^9 $ ) — elements of the array itself.

The sum of $ n $ over all test cases doesn't exceed $ 3 \cdot 10^5 $ .

## 输出格式

For each test case, print a single integer — the minimum possible size of the array $ b $ .

## 样例 #1

### 样例输入 #1

```
4
5
1 3 3 3 7
2
4 2
4
1 1 1 1
7
5 4 2 1 0 0 4
```

### 样例输出 #1

```
2
2
1
3
```

//Contrast Value
//对于任意的递减和递增的数组,有以下性质,利用前缀和维护和
//首尾元素之差等于数组中相邻元素只差的和
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
string s;
int n,t,a[N],f[N],res,num,ans,m;
bool vis[N];
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        res=0,num=0,ans=0,a[0]=0x3f3f3f;
        bool f1=true,f2=true;
        for(int i=0;i<n;i++){
            cin>>m;
            if(m==a[num]) continue;
            a[++num]=m;
        }
        for(int i=2;i<=num;i++) {
            if(a[i]>a[i-1]&&f2) res++,f1=true,f2=false;
            if(a[i]<a[i-1]&&f1) res++,f2=true,f1=false;
        }
        cout<<res+1<<endl;
    }
    return 0;
}