AGC037F

题目传送门

第一步，考虑判断序列是否合法。

通过对于属于等级 $k$ 的定义将定义反推：$s$ 中最小的元素 $x$，找到所有 $x$ 的连续段。设一个连续段的长度是 $len$，若 $len < l$ 则不合法，否则将这一段合并为 $\lfloor \frac {len}l \rfloor$ 个 $x + 1$，直到 $s$ 中只剩下一种元素，同时为了满足这个定义，这个元素一定是原 $s$ 最大值，且不再合并这个元素。

令 $s$ 最大值为 $m$，显然，合法情况有两种：

• 1. 若 $m$ 的数量为 $1$，这种情况当且仅当原序列的长度为 $1$，$s$ 属于等级 $m$，合法。
• 2. 若 $m$ 的数量不少于 $l$，$s$ 属于等级 $m + 1$，合法。

考虑将这个过程应用到个序列 $a$ 中。

从小到大考虑 $a$ 中出现过的值 $m$，当考虑到 $m$ 时，计算 $a$ 中所有最大值为 $w$ 的子段的中合法的数量，用栈维护。

现在，转化为问题：有一个序列 $s = s_0ms_1m \cdots $，其中 $s_i$ 为一个所有元素都 $<m$ 的序列，求这个序列中有多少个子段满足其属于等级 $m+1$。

设 $w$ 为 $s$ 中的最大值，对于一个序列 $s$ 维护信息：

• $f_{s,i}$ 表示 $s$ 中至多能合并出 $i$ 个 $w$ 的前缀个数。
• $g_{s,i}$ 表示 $s$ 中至多能合并出 $i$ 个 $w$ 的后缀个数。
• $h_{s}$ 表示 $s$ 至多能合并出的 $w$ 的个数（由 $f,g$ 求出）。

根据 $f_s,g_s,h_s$，可求出 $∀w^\prime > w$，$s$ 中至多能合并出 $i$ 个 $w^\prime$ 的前缀与后缀个数，$s$ 至多能合并出的 $w^\prime$ 的个数。

假设我们现在对于 $s = s_0ws_1w \cdots ws_m$ 中的所有 $s_i$ 都求出了 $f_{s_i},g_{s_i},h_{s_i}$，则我们首先可以求出 $s_i$ 中至多能合并出 $i$ 个 $w$ 的前/后缀个数，以及 $s$ 至多能合并出的 $w$ 的个数。之后就可以求出答案了。

时空复杂度 \(O(n\) \(logn)\)

#include <bits/stdc++.h>

#define rint register int
#define int long long
#define endl '\n'

using namespace std;

const int N = 2e5 + 5;

int n, l;
int s[N], f[N], g[N];
int sf[N], sg[N];
int ans;
int top;

void pop()
{
    int k = 1;
	int x = s[top];
	
    while (s[top - 1] == x) top--, k++; 
    top--;
    
    if (k < l)
    {
        while (top != 0) pop();
        return;
    }
    
    for (rint i = 1; i <= k; i++)
    {
        sf[i] = sf[i - 1] + f[i + top];
		sg[i] = sg[i - 1] + g[i + top];		
	}

    for (rint i = l; i <= k; i++)
    {
        ans += sf[i - l + 1] * g[i + top];		
	}

    int m = k / l;

    for (rint i = 1; i <= m; i++)
    {
        f[top + i] = sf[k - l * (m - i + 1) + 1] - sf[max(k - l * (m - i + 2) + 1, 0ll)];
        g[top + i] = sg[min(l * (i + 1) - 1, k)] - sg[l * i - 1];		
	}

    int p = 0;

    for (rint i = l; i <= m; i++)
    {
		p += f[top + i - l + 1];
		ans -= p * g[top + i];	
	}

    for (rint i = 1; i <= m; i++)
    {
        s[++top] = x + 1;		
	}
}

signed main()
{
    cin >> n >> l;
	ans = n;
    
	for (rint i = 1; i <= n; i++)
    {
        int a;
		cin >> a;
        while (top != 0 && s[top] < a) pop();
        s[++top] = a;
		f[top] = g[top] = 1;
    }
    
    while (top != 0) pop();
    
    cout << ans << endl;
    
    return 0;
}

ARC102F

题目传送门
题目大意为，给定长度为 \(n\) 的排列 \(p\), 可以进行无限次操作, 问最终能否将其排成升序. 其中, 一次操作定义为选择 \(i\) 使得 $ 2 \leq i \leq n-1$ 且 \(p_{i-1}>p_i>p_{i+1}\). 交换 \(p_{i-1},p_{i+1}\)

在上一道题的求解中，用到了逆向思维，这道题同样如此。

对于此题，假设 择 \(i\) 使得 $ 2 \leq i \leq n-1$ 且 \(p_{i-1}>p_i>p_{i+1}\). 交换 \(p_{i-1},p_{i+1}\) 中，\(i\) 为合法点。如果 \(p_i \ne i\) 且 \(i\) 为合法点，显然，无论怎样操作都会自相矛盾对吧，发现, 若 \(i\) 为合法点, 则在所有操作之前, \(p_i=i\)

通过这个性质我们可以先筛掉一些一定不合法的序列。

但是只通过这个性质并不全。

定义数组 bool a[i]=[i==p[i]]， 如果 \(a\) 中有连续的 \(3\) 个 \(0\) 出现, 无解. 考虑将 \(a\) 分成若干个区间, 使得同一个区间内没有两个连续的数相等. 易证区间与区间之间不存在数的交换。个区间的值域的范围和下标的范围应该要一样. 在一个区间内, 考虑把 \(a_i=0\) 的数单独拿出来, 如果其最长下降子序列的长度大于等于三则无解. 考虑有 \(3\) 个数 \(a>b>c\), 显然它们是无法交换过来的.

此做法时空复杂度 \(O(n)\)

#include <bits/stdc++.h>

#define rint register int
#define int long long
#define endl '\n'

using namespace std;

const int N = 5e5 + 5;

int n, p[N];
bool a[N];
int minn[N];
int s[N], top;

signed main()
{
    cin >> n;
    p[n + 1] = n + 1;   
	 
	for (rint i = 1; i <= n; i++)
	{
		cin >> p[i];
	}
    
    for (rint i = 1; i <= n; i++)
    {
        if (p[i - 1] != i - 1 && p[i] != i && p[i + 1] != i + 1)
        {
			puts("No");
			return 0;
		}
		else if (i == p[i])
		{
			a[i] = 1;
		}
    }

    rint j = 0;
    for (rint i = 1; i <= n; i = j + 1)
    {
        j = i;
        while (j < n && a[j] != a[j + 1]) j++;
        top = 0;
        for (rint k = i; k <= j; k++)
        {
            if (p[k] < i || j < p[k])
            {
				puts("No");
				return 0;
			}
            if (!a[k])
            {
                s[++top] = p[k];				
			}
        }
        minn[top] = s[top];
        for (rint k = top - 1; k >= 1; k--)
        {
            minn[k] = min(minn[k + 1], s[k]);			
		}
        int maxx = s[1];
        for (rint k = 2; k < top; k++)
        {
            maxx = max(maxx, s[k]);
            if (s[k] > minn[k] && s[k] < maxx)
            {
				puts("No");
				return 0;
			}			
        }
    }

    puts("Yes");
    
    return 0;
}

AGC039D

题目传送门

傻逼数学题平面几何

结论：对于任意 \(\triangle ABC\)，三段弧中点的坐标之和，就是 \(\triangle ABC\) 内心的坐标。

由垂心角平分线定理和欧拉线很容易就能整出来。代码不粘了。

AGC021E

题目传送门

很好的一道组合数学题：

我们可以先手搓几个样例玩玩，通过总结，发现最多能喂 \(k\) 只变色龙的都是这样的序列：先是一段 \(A\),然后一段一段 \(AB\) 相连的东西（严格来说是 \(BA\) 相连......）

然后最后一段先是 \(A\) 后是 \(B\)

如果最后喂给那只被钦定的变色龙的 \(A<B\) 时，最多只能弄出 \(x\) 只红变色龙，显然，手上的那个球只能是 \(A\)。否则要拯救那只变色龙，手上的球只能是 \(B\)

通过 $x-1 $个 \(B\) 的位置确定整个序列

方案数是 \(C^{k-1}_{x-1}\)