题目链接

传送门

题意

要你找一个最长的区间使得区间内每一个数出现次数都大于等于\(K\)。

思路

我们通过固定右端点考虑每个左端点的情况。

首先对于每个位置,我们用线段树来维护它作为\(C\)种元素的左端点的可行性。

对于每个元素我们用\(vector\)存下它出现的所有下标。

枚举右端点\(i\),对于\([i,i]\)这区间除去\(a_i\)这个数外其他元素都没有出现过,那么它作为左端点的可行性为\(C-1\);对于\(a_i\)上一次出现的位置\(pos\),则\([pos+1,i-1]\)这一段区间做左端点,由于\(a_i\)在\(i\)出现过了,那么\([pos+1,i-1]\)在线段树内的结点均存了\(a_i\)没有出现的情况,因此需要减去。假设从\(y\)是\(a_i\)从\(i\)往左数恰好出现\(K\)次的位置,\(x\)是恰好出现\(K+1\)次的位置,那么\([x+1,y]\)在线段树内的结点没有存\(a_i\)出现\(K\)次的情况,因此需要加上。

查询:对于\(i\),我们考虑最左边作为左端点可行性为\(C\)的位置加一的\(x\)(因为\(x\)在线段树的信息表示的是以\(i\)为右端点,\(x\)为左端点有多少个数满足题目给定的要求,因此找到最小的可行性为\(C\)的下标),那么此时可以选择的区间长度为\(i-x+1\),然后对于所有情况取\(max\)即可。

代码实现如下

#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL; #define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
#define FIN freopen("/home/dillonh/CLionProjects/Dillonh/in.txt","r",stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0) const double eps = 1e-8;
const int mod = 1000000007;
const int maxn = 100000 + 7;
const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL; int N, C, K, x;
vector<int> vec[maxn]; struct node {
int l, r, mx, lazy, ans;
}segtree[maxn<<2]; void push_up(int rt) {
segtree[rt].mx = max(segtree[lson].mx, segtree[rson].mx);
//预存从i为右端点,可行性为C下表最小的左端点
if(segtree[rt].mx == segtree[lson].mx) segtree[rt].ans = segtree[lson].ans;
else segtree[rt].ans = segtree[rson].ans;
} void push_down(int rt) {
int x = segtree[rt].lazy;
segtree[rt].lazy = 0;
segtree[lson].lazy += x;
segtree[rson].lazy += x;
segtree[lson].mx += x;
segtree[rson].mx += x;
} void build(int rt, int l, int r) {
segtree[rt].l = segtree[rt].ans = l, segtree[rt].r = r;
segtree[rt].mx = segtree[rt].lazy = 0;
if(l == r) return;
int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
} void update(int rt, int l, int r, int val) {
if(segtree[rt].l == l && segtree[rt].r == r) {
segtree[rt].mx += val;
segtree[rt].lazy += val;
return;
}
push_down(rt);
int mid = (segtree[rt].l + segtree[rt].r) >> 1;
if(r <= mid) update(lson, l, r, val);
else if(l > mid) update(rson, l, r, val);
else {
update(lson, l, mid, val);
update(rson, mid + 1, r, val);
}
push_up(rt);
} int query(int rt, int l, int r) {
if(segtree[rt].mx != C) return -1;
if(segtree[rt].l >= l && segtree[rt].r <= r) return segtree[rt].ans;
push_down(rt);
int mid = (segtree[rt].l + segtree[rt].r) >> 1;
if(r <= mid) return query(lson, l, r);
else if(l > mid) return query(rson, l, r);
else {
int tmp = query(lson, l, mid);
if(tmp != -1) return tmp;
return query(rson, mid + 1, r);
}
} int main() {
while(~scanf("%d%d%d", &N, &C, &K)) {
for(int i = 1; i <= C; ++i) vec[i].clear(),vec[i].push_back(0);
build(1, 1, N);
int ans = 0;
for(int i = 1; i <= N; ++i) {
scanf("%d", &x);
update(1, i, i, C - 1); //单独只考虑[i,i]这个区间,此时其他i-1个元素均没有出现,因此i的作为左端点可行性为C-1
if(vec[x].back() < i - 1) update(1, vec[x].back() + 1, i - 1, -1); //将前面考虑过ai没有出现的情况减去
vec[x].push_back(i);
if(vec[x].size() >= K + 1) {
int pos = vec[x].size() - K - 1;
update(1, vec[x][pos] + 1, vec[x][pos+1], 1); //把前面没有考虑ai出现k次的情况加上
}
int tmp = query(1, 1, i);
if(tmp == -1) continue;
ans = max(ans, i - tmp + 1);
}
printf("%d\n", ans);
}
return 0;
}

最新文章

  1. UDP及其组播,接收发送封装
  2. Python--命令行参数解析Demo
  3. JAVA 设计模式 适配器模式
  4. gfortran编译Fortran数组问题
  5. C语言第5天
  6. Oracle-11g-R2(11.2.0.3.x)RAC Oracle Grid &amp; Database 零宕机方式回滚 PSU(自动模式)
  7. &lt;s:if&gt;标签与ActionContext.getContext().getSession()
  8. HYSBZ 2243 染色 (树链拆分)
  9. PHP中使用正则表达式详解 preg_match() preg_replace() preg_mat
  10. bzoj4514 [Sdoi2016]数字配对
  11. c/c++ 通用的(泛型)算法 generic algorithm 总览
  12. net core体系-web应用程序-4net core2.0大白话带你入门-3asp.net core项目架构和配置文件解读
  13. 【iOS】ARC-MRC下的单例及其应用
  14. kolla-ansible源码分析
  15. 06 python下
  16. Linux安装配置JDK1.7
  17. SQL Server性能优化(11)非聚集索引的覆盖索引存储结构
  18. if-else和while循环
  19. node模块加载机制。
  20. 《转载》Linux服务之搭建FTP服务器&amp;&amp;分布式文件服务器的比较

热门文章

  1. 热点Key问题的发现与解决
  2. 转 史上最详细的Hadoop环境搭建
  3. 第9课 C++异常处理机制
  4. window 运行spark报错
  5. ubuntu docker 搭建 mongodb,开启授权访问 redis,mysql mssql 备份还原
  6. mybatis插入数据后返回自增主键ID详解
  7. Tomcat 配置文件解析工具 Digester
  8. C#简单构架之EF进行读写分离+多数据库Mysql/SqlServer
  9. AQS原理解析 AbstractQueuedSynchronizer
  10. CXF 教程 (二)