「hdu6602」Longest Subarray【线段树】_hdu 6602　线段树

Longest Subarray

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 1060 Accepted Submission(s): 333

Problem Description

You are given two integers $C,K$ and an array of $N$ integers $a_1,a_2,...,a_N$. It is guaranteed that the value of ai is between $1$ to $C$.

We define that a continuous subsequence $a_l,a_{l+1},...,a_r(l\le r)$ of array a is a good subarray if and only if the following condition is met:

$\forall x\in [1,C],{\sum }_{i=l}^r[ai=x]=0or{\sum }_{i=l}^r[ai=x]\ge K$

It implies that if a number appears in the subarray, it will appear no less than $K$ times.

You should find the longest good subarray and output its length. Or you should print $0$ if you cannot find any.

Input

There are multiple test cases.

Each case starts with a line containing three positive integers $N,C,K(N,C,K\le 10^5)$.

The second line contains N integer $a_1,a_2,...,a_N(1\le a_i\le C)$.

We guarantee that the sum of $Ns$, the sum of $Cs$ and the sum of $Ks$ in all test cases are all no larger than $5\times 10^5$.

Output

For each test case, output one line containing an integer denoting the length of the longest good subarray.

Sample Input

7 4 2
2 1 4 1 4 3 2
1
2

Sample Output

4
1

Source

2019 Multi-University Training Contest 2

题意

• 给你一个数组，数的范围是$[1,C]$，给定$K$，让你找一个最长的区间使得区间内任意一个出现的数在该区间内的数量都大于$K$

题解

• 赛后补题，感觉这个题用线段树来做确实挺巧妙的
• 整体思想就是枚举右端点，找最左的左端点，然后取$max$，至于怎么找，考虑建一颗线段树，每个叶子节点记录一改位置为左节点，当前枚举的节点为右节点的合法颜色种类数量，显然如果等于$m$，那么以这个节点为左节点是合法的，由于线段树叶子节点最大权值为$m$，所以可以通过维护一个最大值，和最大值对应的最左边的那个位置，查询这个位置就是最优左区间位置
• 然后考虑怎么维护这颗线段树，假设当前枚举的右节点$r$，首先该节点权值得加上$m-1$，表示除$a[r]$的其他$[1,m]$的数以该节点为左端点是合法的，然后对于数$a[r]$，设前面出现的数的位置分别为$p_1,p_2,p_3...p_t$，如果$t==k$，则$[t_1+1,t_2]$区间内得加$1$，表示数$a[r]$当前以及以后能以这些点作为左端点，另外如果$k>1$,那么区间$[p_t,$当前位置$]$得减1，因为这个颜色已经不能作为左端点了，这里维护每个数的位置信息我用的$deque$，如果$t==k$，记得$pop\_front()$
• 还有这道题尺取是个假做法

代码

#include<bits/stdc++.h>

using namespace std;
const int maxn=1e5+10;

int n,m,k,a[maxn],mark[maxn<<2],val[maxn<<2],maxx[maxn<<2],pos[maxn<<2];
deque<int> que[maxn]; //que[i]维护数i的最多k个最新位置信息

void init()
{
    for(int i=1;i<=m;i++) que[i].clear();
    for(int i=1;i<=m;i++) que[i].push_back(0);//插入0，使后面代码整洁
}

void pushup(int id)
{
    if(maxx[id<<1]>=maxx[id<<1|1]) maxx[id]=maxx[id<<1],pos[id]=pos[id<<1];
    else maxx[id]=maxx[id<<1|1],pos[id]=pos[id<<1|1];
}

void down(int id)
{
    maxx[id<<1]+=mark[id];
    maxx[id<<1|1]+=mark[id];
    mark[id<<1]+=mark[id];
    mark[id<<1|1]+=mark[id];
    mark[id]=0;
}


void build(int id,int l,int r)
{
    int mid=(l+r)>>1;mark[id]=0,val[id]=0;maxx[id]=0;pos[id]=l;
    if(l==r) return;
    build(id<<1,l,mid);build(id<<1|1,mid+1,r);
}

void update(int id,int L,int R,int l,int r,int add)
{
    if(l<=L&&R<=r) {
        mark[id]+=add;maxx[id]+=add;
        return;
    }
    if(mark[id]) down(id);
    int mid=(L+R)>>1;
    if(l<=mid) update(id<<1,L,mid,l,r,add);
    if(r>mid) update(id<<1|1,mid+1,R,l,r,add);
    pushup(id);
}

pair<int,int> query(int id,int L,int R,int l,int r)
{
    pair<int,int> resl=make_pair(-1,-1),resr=make_pair(-1,-1);
    if(l<=L&&R<=r) return make_pair(maxx[id],pos[id]);

    if(mark[id]) down(id);
    int mid=(L+R)>>1;
    if(l<=mid) resl=query(id<<1,L,mid,l,r);
    if(r>mid) resr=query(id<<1|1,mid+1,R,l,r);

    if(resl.first>=resr.first) return resl;
    return resr;
}

int get(int l,int r)
{
    auto res=query(1,1,n,l,r);
    if(res.first!=m) return -1;
    return res.second;
}

int main()
{
    while(~scanf("%d %d %d",&n,&m,&k)) {
        init();int ans=0;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        if(k==1) {printf("%d\n",n);continue;}
        build(1,1,n);
        for(int i=1;i<=n;i++) {
            int last_pos=que[a[i]].back();
            if(k!=1&&last_pos+2<=i) update(1,1,n,last_pos+1,i-1,-1);
            if(que[a[i]].size()==k) {
                int fir_pos=que[a[i]].front();que[a[i]].pop_front();
                int nxt=que[a[i]].front();
                update(1,1,n,fir_pos+1,nxt,1);
            }
            que[a[i]].push_back(i);
            update(1,1,n,i,i,m-1);
            int q=get(1,i);
            if(q!=-1) ans=max(ans,i-q+1);
        }
        printf("%d\n",ans);
    }
}
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