DDOSvoid's Blog

CF 5E Bindian Signalizing

发表于 分类于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/contest/5/problem/E

Solution

首先我们考虑序列的情况

对于每一对数 $(x,y)$，我们从 $y$ 的位置计算这一贡献

那么对于每一个 $i$，前面符合条件的 $j$，一定是 $pre[i-1]$ 的后缀最大值

这个东西可以拿单调栈维护，值相同的情况需要特殊处理

对于环，我们把最大值放到第一个位置，那么就可以当成序列做，最后在统计一下第一个位置和哪些位置还能造成贡献

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <cstdio>
#include <cctype>
#define maxn 1000010
#define ll long long
#define gc getchar
using namespace std;

int read() {
    int x = 0; char c = gc();
    while (!isdigit(c)) c = gc();
    while (isdigit(c)) x = x * 10 + c - '0', c = gc();
    return x;
}

int n, a[maxn], b[maxn];

struct node {
    int v, s;

    node() {}
    node(int _v, int _s) { v = _v; s = _s; } 
} st[maxn]; int top; 


bool vis[maxn];

ll ans;
int main() {
    n = read();
    for (int i = 1; i <= n; ++i) a[i] = b[i] = read(); 
    int mx = 0, p; 
    for (int i = 1; i <= n; ++i) if (a[i] > mx) mx = a[i], p = i;
    for (int i = 1; i <= n - p + 1; ++i) a[i] = b[p + i - 1];
    for (int i = n - p + 2; i <= n; ++i) a[i] = b[i - n + p - 1];
    for (int i = 1; i <= n; ++i) {
        while (top && a[i] > st[top].v) ans += st[top--].s;
        if (a[i] != st[top].v) ans += top > 0, st[++top] = node(a[i], 1);
        else ans += (top > 1) + st[top].s++;
    }
    mx = 0;
    for (int i = 2; i <= n; ++i)
        if (a[i] >= mx) mx = a[i], vis[i] = 1; 
    mx = 0; 
    for (int i = n; i > 1; --i) 
        if (a[i] >= mx) mx = a[i], ans += !vis[i]; 
    cout << ans << endl; 
    return 0;
}