本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-24 12:07:37

赛时过 ABCDEF，同时想出了 G 题正解但没时间写了。

A

模拟。

B

注意 $W,B$ 很小，所以实际合法区间的 $l,r$ 也不会很大。
把 S 设置为暴力重复 500 次 wbwbwwbwbwbw 差不多肯定可以了。

然后暴力枚举合法区间。

C

先算出 $1$ 到 $K$ 的和，然后依次减去里面出现过的就可以了。

D

我是比较麻烦的分类讨论做法。
先思考下 dp 有哪些需要关注哪些状态？

• 目前枚举到了第 $i$ 个字符，计算前 $i$ 个字符组成的字符串的答案。
• 另外，转移的时候发现，我们似乎不知道第 $i-1$ 个字符是什么，没法转移。所以加入状态：第 $i$ 个字符是什么？
• 另外还要注意一点：正好有一对相邻值相等，那么我们还需要考虑另一个状态：前 $i$ 个字符是否已经存在一对相临值相等？
• 我们还需要求出最小代价，这个加入 dp 值就可以了。

综上，设置 $dp_{1 \le i \le n,a \in (0,1),b \in (0,1)}$ ，注意 $a$ 代表真，$b$ 代表假，那么这个 dp 代表前 i 个字符，且第 $i$ 个字符发生变化的真假为 $a$，前 $i$ 个字符存在一对相邻值相等的真假为 $b$，此时最小操作代价。

转移：

#define FOR(i,a,b) for(int i=a;i<=b;i++)
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
dp[1][0][0] = 0;
dp[1][1][0] = c[1];
FOR(i, 2, n)
{
    \/\/ case1: 上一个不变
    if (s[i - 1] == s[i])
    { \/\/ 和上一个相同
        \/\/ ca1: 这次变，不会影响相同数量变化
        ckmn(dp[i][1][1], dp[i - 1][0][1] + c[i]);
        ckmn(dp[i][1][0], dp[i - 1][0][0] + c[i]);
        \/\/ ca2 这次不变
        ckmn(dp[i][0][1], dp[i - 1][0][0]);
    }
    else
    {
        \/\/ ca1：这次不变，不影响相同数量变化
        ckmn(dp[i][0][1], dp[i - 1][0][1]);
        ckmn(dp[i][0][0], dp[i - 1][0][0]);
        \/\/ ca2: 这次便
        ckmn(dp[i][1][1], dp[i - 1][0][0] + c[i]);
    }

    \/\/ case2：上一个变
    if (s[i - 1] == s[i])
    {
        \/\/ ca1：这次不变，不会影响相同数量变化
        ckmn(dp[i][0][1], dp[i - 1][1][1]);
        ckmn(dp[i][0][0], dp[i - 1][1][0]);
        \/\/ ca2: changed now
        ckmn(dp[i][1][1], dp[i - 1][1][0] + c[i]);
    }
    else
    {
        \/\/ ca1: 这次变，不会影响相同数量
        ckmn(dp[i][1][1], dp[i - 1][1][1] + c[i]);
        ckmn(dp[i][1][0], dp[i - 1][1][0] + c[i]);
        \/\/ ca2:  not change
        ckmn(dp[i][0][1], dp[i - 1][1][0]);
    }
}
printf("%lld\n", min(dp[n][1][1], dp[n][0][1]));

E

以下，可能会用括号代表一个整体。

考虑每次操作实际会有多少影响。

显然，第 $i$ 次操作的影响为：第 $i$ 次覆盖的点数 - （($\cup_{j=i+1}^M$ 第 $j$ 次操作覆盖的点集）$\cap$ (第 $i$ 次覆盖的点集)）的大小

而这个怎么处理呢？

• 如果存在 $j \gt i$，使得第 $i,j$ 次操作相同，那么第 $i$ 次操作可以忽略。

• 否则，第 $i$ 次操作实际贡献为第 $i$ 次覆盖点数 - 第 $j \gt i$ 次操作中与第 $i$ 次覆盖方向不同的操作数量。
  倒着算就可以了。

F

单调性是显然的，可以二分 $k$。

然后，其实没啥技术含量的，判定是否合法，只需要枚举每一位模拟就行。

细节不少，但是没啥记录的意义，唯一要注意的是 check 过程可能会爆 long long。

G

直接做不好做，那么反过来考虑每个元素对哪些 $[l,r]$ 有贡献。

假设目前是第 $i$ 个元素，$p$ 是最小的 $p$ 满足区间 $[p,i]$ 只存在一个 $a_i$，$q$ 是最大的 $q$ 满足区间 $[i,q]$ 只存在一个 $a_i$。那么显然，对于所有的 $p \le l \le i,i \le r \le q$，区间 $[l,r]$ 合法。

注意到这里的贡献对 $l$ 和 $r$ 各进行了一个区间范围的限制，而上面实际上可以抽象成一个二维平面，所有满足 $p \le l \le i,i \le r \le q$ 的点 $(p,q)$ 都可以计入最终贡献，也就是说它实际上将一个矩形内的所有整点加入了最终贡献。

最终答案可以转换成，有多少点 $(p,q)$ 满足 $1 \le p \le q \le n$，且被任意一个矩阵覆盖过。

这个东西扫描线搞定。

#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back()
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int maxn=2e5+5;
int n;
int a[maxn];
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
\/*
对于每个 i，设有效区间 [a,b]

那么对于区域 [a<=l<=i][i<=r<=b] 所有点都有解
加入矩阵即可。
然后扫描线求出矩阵面积并，然后就是答案。
*\/
vector<int> pos[maxn];
struct Matrix{
	int x_l,x_r,y_l,y_r;
}matrix[maxn];
Matrix mkmt(int a,int b,int c,int d){
	Matrix res;
	res.x_l=a,res.x_r=b,res.y_l=c,res.y_r=d;
	return res;
}
int cntmat;
struct Seg_Tree{
	int cov[maxn<<2];
	int len[maxn<<2];
	int L[maxn<<2],R[maxn<<2];
	void build(int pos,int l,int r){
		L[pos]=l,R[pos]=r;
		if(l==r){
			return;
		}
		int mid=(l+r)\/2;
		build(pos*2,l,mid);
		build(pos*2+1,mid+1,r);
	}
	void pushup(int pos){
		if(cov[pos]){
			len[pos]=(R[pos]-L[pos]+1);
		}else{
			if(pos*2<maxn*4){
				len[pos]=len[pos*2]+len[pos*2+1];
			}else{
				len[pos]=0;
			}
		}
	}
	void chg(int pos,int l,int r,int add){
		if(L[pos]>=l&&R[pos]<=r){
			cov[pos]+=add;
			pushup(pos);
			return;
		}
		if(R[pos]<l||L[pos]>r)return;
		int mid=(L[pos]+R[pos])\/2;
		if(mid>=l)chg(pos*2,l,r,add);
		if(mid<r)chg(pos*2+1,l,r,add);
		pushup(pos);
	}
	int getsum(){
		return len[1];
	}
}sgt;
struct Line{
	int y_up,y_dw,x;
	int add;
}line[maxn*2];
void solve(){
	scanf("%d",&n);
	FOR(i,1,n){
		scanf("%d",&a[i]);
		pos[a[i]].emplace_back(i);
	}
	FOR(i,1,n){
		for(int j=0;j<pos[i].size();j++){
			int l=1,r=n;
			if(j!=0){
				l=pos[i][j-1]+1;
			}
			if(j+1!=pos[i].size()){
				r=pos[i][j+1]-1;
			}
			matrix[++cntmat]=mkmt(l,pos[i][j],pos[i][j],r);
	\/\/		printf("add  = %d %d %d %d\n",l,i,i,r);
		}
	}
	assert(cntmat==n);
	FOR(i,1,cntmat){
		line[(i-1)*2+1].y_up=matrix[i].y_r;
		line[(i-1)*2+1].y_dw=matrix[i].y_l;
		line[(i-1)*2+1].x=matrix[i].x_l;
		line[(i-1)*2+1].add=1;
		
		line[(i-1)*2+2].y_up=matrix[i].y_r;
		line[(i-1)*2+2].y_dw=matrix[i].y_l;
		line[(i-1)*2+2].x=matrix[i].x_r+1;
		line[(i-1)*2+2].add=-1;
	}
	sort(line+1,line+cntmat*2+1,[&](Line& a,Line& b){
		return a.x<b.x;
	});
	sgt.build(1,1,n);
	ll s1=0;
	line[cntmat*2+1].x=n+1;\/\/占位
	\/\/ 注意到，有些线段可能会到达 x=n 位置，此时贡献
	FOR(i,1,cntmat*2){
		ll len=line[i+1].x-1-line[i].x+1;\/\/ 当前纵线的有效长度
		sgt.chg(1,line[i].y_dw,line[i].y_up,line[i].add);
		s1+=(ll)sgt.getsum()*len;
	}
	printf("%lld\n",s1);
}
int main()
{
    int T=1;
	while(T--){
		solve();
	}
	return 0;
}