Blackops

初心易得，始终难守

0%

2017年浙江工业大学大学生程序设计迎新赛热身赛 G 方块 II（离散化+线段树+尺取）

发表于 分类于 ， ，

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述
有 N 个方块排成一排，每个方块都染有颜色，第 i 个的颜色为 Ci。现在你可以最多移除 K 个方块，把剩下的方块按照原来的顺序重新排好，找出最长的颜色相同的连续方块。
输入描述:
T组数据。
每组数据第一行，包含两个整数 N 和 K
接下来一行包含 N 个整数 Ci，代表每个方块的颜色
T <= 300
1 <= N <= 105，0 <= K <= N，1 <= Ci <= 109
输出描述:
每组数据一个整数，表示答案。
示例1
输入

10 1
1 1 1 1 1 1 1 1 1 1
10 5
3 2 3 5 1 2 5 3 2 2
输出

10
4

题目链接：G.方块 II
看样例感觉尺取可行，实际上对于任何区间，最优的方案肯定是留下这个区间里的众数，去掉其余的数，设区间为$[L,R]$，众数为$x$，众数的个数为$c$，那么去掉的数就是$R-L+1-c$，那么直接把颜色离散化到$10^5$范围内，然后以权值建立线段树，加入数的时候就把颜色的位置$+1$，去掉的时候就$-1$，因此需要单点更新区间查询最大值的线段树，用来维护尺取时区间内的最大值，每一次都找到一个最大的区间使得其范围合法且最少去掉的数小于等于$k$。注意题目是多组数据，每一次都要初始化，难怪一开始只通过了$0.8\%$的case………
代码：

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e5 + 7;
struct seg
{
    int l, mid, r;
    int id, v;
} T[N << 2];
int arr[N];
vector<int>vec;

void init()
{
    vec.clear();
}
inline void pushup(int k)
{
    int ls = LC(k), rs = RC(k);
    if (T[ls].v > T[rs].v)
    {
        T[k].v = T[ls].v;
        T[k].id = T[ls].id;
    }
    else
    {
        T[k].v = T[rs].v;
        T[k].id = T[rs].id;
    }
}
void build(int k, int l, int r)
{
    T[k].l = l;
    T[k].r = r;
    T[k].mid = MID(l, r);
    if (l == r)
    {
        T[k].v = 0;
        T[k].id = l;
    }
    else
    {
        build(LC(k), l, T[k].mid);
        build(RC(k), T[k].mid + 1, r);
        pushup(k);
    }
}
void update(int k, int x, int v)
{
    if (x == T[k].l && T[k].r == x)
        T[k].v += v;
    else
    {
        if (x <= T[k].mid)
            update(LC(k), x, v);
        else
            update(RC(k), x, v);
        pushup(k);
    }
}
int main(void)
{
    int n, k, i;
    while (~scanf("%d%d", &n, &k))
    {
        init();
        for (i = 0; i < n; ++i)
        {
            scanf("%d", &arr[i]);
            vec.push_back(arr[i]);
        }
        sort(vec.begin(), vec.end());
        vec.erase(unique(vec.begin(), vec.end()), vec.end());
        for (i = 0; i < n; ++i)
            arr[i] = lower_bound(vec.begin(), vec.end(), arr[i]) - vec.begin() + 1;
        int ans = 0, L = 0, R = 0;
        build(1, 1, n);
        while (L < n)
        {
            while (R < n)
            {
                update(1, arr[R], 1);
                ++R;
                if (R - L - T[1].v > k)
                {
                    update(1, arr[--R], -1);
                    break;
                }
            }
            ans = max(ans, T[1].v);
            update(1, arr[L], -1);
            ++L;
        }
        printf("%d\n", ans);
    }
    return 0;
}