闲话
和等差数列过不去了。碰上等差数列就要调 1h。
题目翻译
为了方便描述，我们约定数值相同的数为同一颜色的数。
有 $n$ 个数，我们定义一次操作为：选择若干个同颜色数，使得他们在序列中的位置为一个等差数列。删除它们。
操作完之后可以重排整个序列。
有 $q$ 个询问，每次询问给定 $[l,r]$，求至少几次操作能全部删除 $[l,r]$。
询问互不影响。
$1\leq n,q,a_i\leq 10^5$
题目思路
与翻译类似，约定数值相同的数为同一颜色的数。
看起来就长了一眼莫队样子。
分析一下，发现操作一次之后，通过重排是可以调整使得之后每次都能删除某一种相同数。
但是，如果我们第一次操作就可以删除某一种相同数，换言之，如果原区间本身就包含一个颜色使得位置为等差数列，答案即为区间颜色数。反之，答案为区间颜色数 $+1$。
区间颜色数是很好维护的，我们用一个桶记录每个数出现几次即可。
另外介绍一种小常数写法，我们记录 $pre_i$ 与 $nxt_i$ 表示与 $a_i$ 颜色相同的数上一次或下一次出现在什么位置，这能做到访址连续跑得更快。
// while(L>Query[i].L)ANS+=(++h[a[--L]]==1);
// while(R<Query[i].R)ANS+=(++h[a[++R]]==1);
// while(L<Query[i].L)ANS-=(--h[a[L++]]==0);
// while(R>Query[i].R)ANS-=(--h[a[R--]]==0);
while(L>Query[i].L)ANS+=(nxt[--L]>R);
while(R<Query[i].R)ANS+=(pre[++R]<L);
while(L<Query[i].L)ANS-=(nxt[L++]>R);
while(R>Query[i].R)ANS-=(pre[R--]<L);注释即为正常桶记录写法，非注释即为这种访址连续的写法。
然后我们考虑如何判断『原区间本身就包含一个颜色使得位置为等差数列』，为了莫队方便把信息传递到下个区间，我们改成『维护区间内有多少颜色使得位置为等差数列』。
这个有一个很显然的单次修改查询 $\mathcal O(\log n)$ 的做法为，维护若干 multiset，每次暴力插入删除当前点的贡献，然后判断最大值与最小值是否相等。附一个到此步 TLE on 23 的码：CF submission 243942020。
然后考虑优化，我们现在把要维护的问题转化为：
有 $n$ 个类别，每次操作在一个类别里加入或删除一个数，每次判断这个类别是否只有 $1$ 种数。
然后，我们考虑一个人类智慧做法：
维护 $3$ 个信息，类别中数的个数 $cnt_i$，类别中数的和 $sum_{0,i}$，类别中数的平方和 $sum_{1,i}$。
有这三个信息我们就可以判断是否类别中均为一个数了。
你怎么知道这是我深夜在 U 群问怎么做这个问题然后 skip2004 告诉我的解法。
然后我们把之前 TLE on 23 的码改一改就可以了！
完整代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++
char buf[1000000], *p1 = buf, *p2 = buf;
template <typename T>
void read(T &x)
{
x = 0;
int f = 1;
char c = getchar();
for (; c < '0' || c > '9'; c = getchar())
if (c == '-')
f = -f;
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
x *= f;
}
template <typename T, typename... Args>
void read(T &x, Args &...y)
{
read(x);
read(y...);
}
int fa[100020];
int a[100020];
int ans[100020];
int pre[100020];
int nxt[100020];
int p[100020];
ll sum[2][100020];
int cnt[100020];
multiset<int> s[100020];
int n, len, ANS, q, tot;
struct node
{
int L, R, id;
} Query[1000020];
bool cmp(node a, node b)
{
if (fa[a.L] != fa[b.L])
return a.L < b.L;
if (fa[a.L] & 1)
return a.R > b.R;
return a.R < b.R;
}
ll sq(int x) { return 1LL * x * x; }
bool same(int x) { return !cnt[x] ? 1 : !(sum[0][x] % cnt[x]) && !(sum[1][x] % cnt[x]) && sq(sum[0][x] / cnt[x]) * cnt[x] == sum[1][x]; }
void add(int x, bool ff)
{
bool f = 0;
if (ff & 1)
{
if (same(a[x]))
f = 1;
cnt[a[x]]++;
sum[0][a[x]] += x - pre[x];
sum[1][a[x]] += sq(x - pre[x]);
if (!same(a[x]) && f)
tot--;
}
else
{
if (same(a[x]))
f = 1;
cnt[a[x]]++;
sum[0][a[x]] += nxt[x] - x;
sum[1][a[x]] += sq(nxt[x] - x);
if (!same(a[x]) && f)
tot--;
}
}
void del(int x, bool ff)
{
bool f = 0;
if (ff & 1)
{
if (!same(a[x]))
f = 1;
cnt[a[x]]--;
sum[0][a[x]] -= x - pre[x];
sum[1][a[x]] -= sq(x - pre[x]);
if (same(a[x]) && f)
tot++;
}
else
{
if (!same(a[x]))
f = 1;
cnt[a[x]]--;
sum[0][a[x]] -= nxt[x] - x;
sum[1][a[x]] -= sq(nxt[x] - x);
if (same(a[x]) && f)
tot++;
}
}
int main()
{
read(n);
len = sqrt(n);
for (int i = 1; i <= n; i++)
{
read(a[i]);
fa[i] = (i + len - 1) / len;
nxt[i] = n + 1;
pre[i] = p[a[i]];
nxt[pre[i]] = i;
p[a[i]] = i;
}
read(q);
for (int i = 1; i <= q; i++)
{
int L, R;
read(L, R);
Query[i] = {L, R, i};
}
sort(Query + 1, Query + q + 1, cmp);
int L = 1, R = 0;
for (int i = 1; i <= q; i++)
{
while (L > Query[i].L)
{
L--;
if (nxt[L] > R)
ANS++, tot++;
else
add(L, 0);
}
while (R < Query[i].R)
{
R++;
if (pre[R] < L)
ANS++, tot++;
else
add(R, 1);
}
while (L < Query[i].L)
{
if (nxt[L] > R)
ANS--, tot--;
else
del(L, 0);
L++;
}
while (R > Query[i].R)
{
if (pre[R] < L)
ANS--, tot--;
else
del(R, 1);
R--;
}
ans[Query[i].id] = ANS + 1 - (tot > 0);
}
for (int i = 1; i <= q; i++)
printf("%d\n", ans[i]);
return 0;
}
1 条评论
[...]http://blog.cyx2009.top/archives/250/ 查看。[...]