acd - 1427 - Nice Sequence（線段樹）
來源：程序員人生 發(fā)布時間：2014-11-13 08:42:01 閱讀次數(shù)：3119次
題意：1個由n個數(shù)組成的序列(序列元素的范圍是[0, n])，求最長前綴 j ，使得在這個前綴 j 中對任意的數(shù) i1 < i2，都滿足任意的 m <= j，i1 在前 m 個數(shù)里出現(xiàn)的次數(shù) >= i2 在前 m 個數(shù)里出現(xiàn)的次數(shù) - k (1 ≤ n ≤ 200 000, 0 ≤ k ≤ 200 000)。
題目鏈接：http://acdream.info/problem?pid=1427
――>>第1個前綴 j 不滿足，那末后面的前綴1定不滿足（由于前綴 j 不滿足）。。所以，從左往右掃描，每次取所有數(shù)字 i 的最少出現(xiàn)次數(shù)與當前掃描到的數(shù)出現(xiàn)的次數(shù)比較看是不是滿足條件便可。。
所有數(shù)字 i 指的是哪些數(shù)字呢？是已出現(xiàn)過的數(shù)嗎？樣例2說明不是。。是不大于當前出現(xiàn)過的最大整數(shù)嗎？WA告知我不是。。而是 <= a[j] 的所有非負整數(shù)。。
所有數(shù)字 i 出現(xiàn)次數(shù)的最小值，我想到了RMQ和線段樹，最后選了線段樹來保護這個最小值。。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lc (o << 1)
#define rc ((o << 1) | 1)
using std::min;
using std::max;
const int MAXN = 200000 + 10;
const int INF = 0x3f3f3f3f;
int n, k, Max;
int minv[MAXN << 2], cnt[MAXN];
int a[MAXN];
void Read()
{
Max = ⑴;
for (int i = 1; i <= n; ++i)
{
scanf("%d", a + i);
++a[i];
if (a[i] > Max)
{
Max = a[i];
}
}
}
void Build(int o, int L, int R)
{
minv[o] = 0;
if (L == R) return;
int M = (L + R) >> 1;
Build(lc, L, M);
Build(rc, M + 1, R);
}
void Update(int o, int L, int R, int q)
{
if (L == R)
{
minv[o] = cnt[q];
return;
}
int M = (L + R) >> 1;
if (q <= M) Update(lc, L, M, q);
else Update(rc, M + 1, R, q);
minv[o] = min(minv[lc], minv[rc]);
}
int Query(int o, int L, int R, int ql, int qr)
{
if (ql <= L && R <= qr)
{
return minv[o];
}
int ret = INF;
int M = (L + R) >> 1;
if (ql <= M) ret = min(ret, Query(lc, L, M, ql, qr));
if (qr > M) ret= min(ret, Query(rc, M + 1, R, ql, qr));
return ret;
}
void Solve()
{
int i;
memset(cnt, 0, sizeof(cnt));
for (i = 1; i <= n; ++i)
{
++cnt[a[i]];
Update(1, 1, Max, a[i]);
if (Query(1, 1, Max, 1, a[i]) < cnt[a[i]] - k) break;
}
printf("%d
", i - 1);
}
int main()
{
while (scanf("%d%d", &n, &k) == 2)
{
Read();
Build(1, 1, Max);
Solve();
}
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進行捐贈
