题面描述
一个颜色序列删去颜色的方案使得最后剩下来的序列非空且连续
题解
首先一个序列非空且连续就是原颜色序列的一段连续区间，这段颜色区间的每个颜色仅在该区间里出现，对于每个颜色都有一个左端点和右端点，我们枚举合法区间的左端点就可以通过某些数据结构来后面的位置找有多少个合法右端点即可
然而分析到这就结束了，因为认为对于合法区间有可能会算重合法方案
我真傻，真的
让我们复读看一下这句话
这段颜色区间的每个颜色仅在该区间里出现
若存在两个区间的颜色集合相同又怎么可以合法呢
但是就直接去看了题解
同时在看题解时看到了一个神奇的解法
对于每种颜色的每个位置随机赋值，最后一个位置赋值为前面位置的和的相反数，合法区间的权值为
\(0\)
所以说我们维护前缀和，扫描数组前缀和相同累积答案
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
| #include <cstdio>
#include <cctype>
#include <cstring>
#include <map>
#include <vector>
#include <cstdlib>
#include <cstdint>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
return f*x;
}
const int N = 3e5+5;
const int64_t P = 1e12;
int n, t, a[N];
int64_t f[N];
int64_t sum, ans;
vector<int> p[N];
map<int64_t, int> h;
int main()
{
t = read();
while(t--)
{
n = read(); ans = 0; h.clear();
for(int i = 1; i <= n; ++i) f[i] = 0, p[i].clear();
for(int i = 1; i <= n; ++i) a[i] = read(), p[a[i]].push_back(i);
for(int i = 1; i <= n; ++i)
{
if(p[i].size() < 2) continue;
sum = 0;
for(int j = 0; j < p[i].size()-1; ++j)
{
int q = p[i][j];
int64_t d = 1ll*rand()*rand()%P*rand()%P*rand()%P;
if(rand()&1) d = -d;
sum += d; f[q] = d;
}
f[p[i][p[i].size()-1]] = -sum;
}
sum = 0; h[0] = 1;
for(int i = 1; i <= n; ++i)
sum += f[i], ans += h[sum], ++h[sum];
printf("%lld\n", ans);
}
return 0;
}
|