https://codeforces.com/contest/1550/problem/C
题目大意
曼哈顿距离𝑑(𝑝,𝑞)=|𝑥𝑝−𝑥𝑞|+|𝑦𝑝−𝑦𝑞| .
有三个点p,q,r,若𝑑(𝑝,𝑟)=𝑑(𝑝,𝑞)+𝑑(𝑞,𝑟) .则称这三个点组成Bad Triple
定义一个数组b1,b2,b3....bn是good array，如果不能从这个数组中选出三个不同的序号i,j,k，使得 (𝑏𝑖,𝑖), (𝑏𝑗,𝑗) and (𝑏_𝑘,𝑘) 组成Bad Triple.
目标：现给一个a数组，计算a数组中所有子数组有多少个是good array
另外由定义得知，长度为1或2的都是good array
数据范围
t 组test cases，[1, 5000]
array长度n, [1, 2*10^5]
array 大小 [1, 10^9]
test中所有n的和不超过 2*10^5
分析
暴力是肯定过不了的，那么我们从给的条件入手
设p，q，r是数组中按顺序的三点，那么可以知道他们的y是依次递增的，另外我们知道曼哈顿距离跟真实距离趋势是一致的，也就是真实距离长的曼哈顿距离也长，那么我们可以得出：
1、将pqr组成三角形，若pq是不是最长边，则一定不成立，所以一定是good。
若pq是最长边，则
d(p, q) = yq-yp + |xq-xp|
d(q, r) = yr-yq + |xr-xq|
d(p,r) = yr-yp + |xr-xp|
那么d(p,q) =? d(q,r) + d(p,r)
=》2yq - 2yr =？|xr-xq| + |xr - xp| - |xq-xp|
因为pq最长边，则xr在xp，xq之间，则右边=0
而左边不等于0，因此也一定不成立，所以一定也是good。
所以d(p,q) != d(q,r) + d(r,p)一定成立
2、同理，d(q,r) != d(p,q) + d(r, p)一定成立
3、最后是d(p,r) =? d(p,q) + d(p,r) =》yr-yp + |xr-xp| =? yq-yp + |xq-xp| + yr-yp + |xr-xp|
因为yq 在yp 和yr之间，因此等式变为 |xr-xp| =? |xq-xp| + |xr - xp|
那么可以知道若xq在xp和xr之间，则等式成立，此时这三点为bad，否则等式不成立。
结论：
所以要判断三点是否是good，只需要判断xq是否在xp和xr之间
换一种说法，就是：
对于连续三点，若其x坐标是递增或递减的，则这三点为bad，否则这三点是good。
算法：
对于我们要求解的问题：n长度的数组中有多少个子数组是good的，也就是说这些子数组中没有任意三点是bad，那么问题转化成了判断子数组中的是否存在任意三点是递增的或递减的，若存在，则这个子数组是bad，若不存在，这个子数组是good。
暴力肯定也是过不了的，那么我们期望得到一个接近O(n)的的算法，也就是期望只遍历数组一遍就能得到结果。
首先，我们可以得出简单的前置条件：若长度为n的序列是good的，那么其中的所有子序列是good的。那么我们只需要贪心的去找到全部尽可能长的good的子序列，再计算其中有多少个各个长度的子序列。
那么问题就转化成了：如何快速在线判断一个子数组中任意三点是递增或递减的。
为了满足O(n)的时间复杂度，我们用空间换时间，
由于长度1与2的序列都是good，我们初始化基础序列为[pleft, pright = pleft + 1],是good，对于判断递增，使用deque来记录直到当前序列中前2小的数，当下一个数[pright + 1]到来，判断其是否大于第二小的数。
若大于，则加上这个点后，子序列存在递增三点。此时pleft到pright是当前可以是good的最长序列，接着转移状态至寻找下一个最长子序列，若pright-pleft=1则代表长度为3的是bad，此时将基础状态同时右移1，否则的话将[pright-2, pright-1]作为基础序列。
若小于，且当前值大于第一小的数，则替换更新deque中第二小的数，这样才能确保当前deque中的序列是最小的两个，递增总是可以被找到。
对于判断递减也是一样的思路。
这样我们就可以在O(n)的时间里找到所有最长子序列。
另外这里有一个问题在于你需要去更新deque来确保你总是可以找到递增或递减，那么存在这样一种情况43765，当43进入deque后，当算法运行至6后需要更新deque中43为76，因此在这里使用一个备用deque2，在递增的情况下，当当前值小于deque.front的时候，将其加入deque2，若deque2.size=1时，若当前值小于deque.back，则也将其加入deque2，这时deque2中的序列优于deque中的序列，就用deque2的序列替代deque1的序列。
递减同理。
代码如下，由于修修补补，代码不够优雅。
#include <iostream>
#include <vector>
#include <deque>
#include <map>
using namespace std;
class myQueue{
public:
deque<int> q;
bool incFlag;
myQueue(bool _incFlag){
incFlag = _incFlag;
}
deque<int> get(){
return q;
}
int clear(){
q.clear();
return q.size();
}
int swap(myQueue _q){
q = deque<int>(_q.get());
return q.size();
}
void init(int x1, int x2){
q = deque<int>();
emplace(x1);
emplace(x2);
}
int size(){
return q.size();
}
int pop(){
int n = q.front();
q.pop_front();
return n;
}
int front(){
return q.front();
}
int back(){
return q.back();
}
int emplace(int n){
// the q will always has less equal to 2 elements
if(q.empty()){
q.emplace_back(n);
return q.size();
}
else{
if(incFlag){
if(q.size()== 1 && n < q.back()){
q.pop_back();
q.emplace_back(n);
return q.size();
}else{
if(n >= q.back()){
q.emplace_back(n);
return q.size();
}else if(n < q.back() && n >= q.front()){
q.pop_back();
q.emplace_back(n);
return q.size();
}
else{
return q.size();
}
}
}else{
if(q.size() == 1 && n > q.back()){
q.pop_back();
q.emplace_back(n);
return q.size();
}
else{
if(n <= q.back()){
q.emplace_back(n);
return q.size();
}else if(n > q.back() && n <= q.front()){
q.pop_back();
q.emplace_back(n);
return q.size();
}else{
return q.size();
}
}
}
}
}
};
int solve(vector<int> arr){
if(arr.size() == 0) return 0;
if(arr.size() == 1) return 1;
if(arr.size() == 2) return 3;
// init
int pleft = 0, pright = 1;
map<int, int> cnt;
myQueue incq(true);
myQueue decq(false);
myQueue incq2(true);
myQueue decq2(false);
incq.init(arr[0], arr[1]);
decq.init(arr[0], arr[1]);
pright++;
while(pright < arr.size()){
bool inc = false, dec = false;
if(incq.emplace(arr[pright]) >= 3){
inc = true;
incq.pop();
}else{
if(incq2.size() == 0 && arr[pright] <= incq.front()){
incq2.emplace(arr[pright]);
}else if(incq2.size() == 1 && arr[pright] < incq.back()){
if(incq2.emplace(arr[pright]) == 2){
incq.swap(incq2);
incq2.clear();
}
}
}
if(decq.emplace(arr[pright]) >= 3){
dec = true;
decq.pop();
}else{
if(decq2.size() == 0 && arr[pright] >= decq.front()){
decq2.emplace(arr[pright]);
}else if(decq2.size() == 1 && arr[pright] > decq.back()){
if(decq2.emplace(arr[pright]) == 2){
decq.swap(decq2);
decq2.clear();
}
}
}
// cout<< pleft << " " << pright << " " << (inc || dec) << endl;
if(inc || dec){
// if 1 to 5 is good and 1 to 6 is bad,
// 1 2 3 4 5 6
// now pointer l r
// nex pointer l r
// so that in the next loop
// pright will ++
if(pright - pleft == 2)
pleft++;
else{
pleft = pright - 2;
pright--;
}
incq.init(arr[pleft], arr[pright]);
decq.init(arr[pleft], arr[pright]);
incq2.clear();
decq2.clear();
}else{
cnt[pright - pleft + 1]++;
}
//prepare for next loop and to check while condition
pright++;
}
int result = 0;
// calc result
for(auto m : cnt){
int key = m.first;
int value = m.second;
result += value * (1 + (key - 3) * (1 + key - 3) / 2);
}
result += arr.size() * 2 - 1;
return result;
}
int main(){
int cases = 0;
cin>>cases;
while(cases --){
int n = 0;
scanf("%d", &n);
vector<int> arr(n, 0);
for(int i=0; i<n; i++){
scanf("%d", &arr[i]);
}
cout<<solve(arr)<<endl;
}
return 0;
}
/*
1
4
1 4 3 2
1
5
4 3 6 5 4
1
5
3 5 3 7 4
**/
网友评论