做网站跟赚钱嘛,个人主页网址,楼盘网,企业seo蜘蛛屯传送门 文章目录目录#xff1a;题意#xff1a;思路#xff1a;目录#xff1a;
题意#xff1a;
给你一个长度为nnn的数组aaa以及kkk#xff0c;让你选择一个值域[x,y][x,y][x,y]#xff0c;满足能将该数组分成连续的kkk段并且每段中值域在[x,y][x,y][x,y]内的个数严…传送门 文章目录目录题意思路目录
题意
给你一个长度为nnn的数组aaa以及kkk让你选择一个值域[x,y][x,y][x,y]满足能将该数组分成连续的kkk段并且每段中值域在[x,y][x,y][x,y]内的个数严格大于不在其范围内的数的个数要求你给出[x,y][x,y][x,y]并且让y−xy-xy−x最小让后给出分段的方案。
1≤k≤n≤2e5,1≤ai≤n1\le k\le n\le 2e5,1\le a_i\le n1≤k≤n≤2e5,1≤ai≤n
思路
一开始想错了二分了xxx和yyy还感觉很对。。。
可以发现[x,y][x,y][x,y]这是一个连续的区间我们可以利用这个进行尺取现在问题就变成了如何检验给定[x,y][x,y][x,y]是否合法。
我们将值域在[x,y][x,y][x,y]内的数看成111不在值域内的数看成−1-1−1设新数组preprepre就是将aaa换成111和−1-1−1后的前缀和数组那么一个子区间合法的条件就是[l,r][l,r][l,r]满足pre[r]−pre[l−1]0pre[r]-pre[l-1]0pre[r]−pre[l−1]0顺着这个思路我们不难发现分段方案就是在preprepre数组中找一个从0开始的上升序列长度为k1k1k1那么最终pre[n]pre[n]pre[n]一定需要满足pre[n]kpre[n]kpre[n]k此时就比较好搞了我们先尺取求出来[x,y][x,y][x,y]判断条件就是pre[n]kpre[n]kpre[n]kpre[n]pre[n]pre[n]是所有数的和只需要存一下当前数有几个即可最后输出方案。
复杂度O(n)O(n)O(n)
#includebits/stdc.h
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define Mid (tr[u].ltr[u].r1)
#define pb push_back
using namespace std;const int N1000010,INF0x3f3f3f3f,mod1e97;
typedef long long LL;int n,k;
int a[N],cnt[N];void solve() {scanf(%d%d,n,k);for(int i1;in;i) scanf(%d,a[i]),cnt[a[i]];int x,y,sum-n;x0; yINF;for(int l1,r0;rn;) {while(r1nsumk) sumcnt[r]*2;if(sumk) break;if(r-l1y-x1) xl,yr;sum-cnt[l]*2;}printf(%d %d\n,x,y);sum0;int cntt1;int l1;for(int i1;in;i) {if(a[i]xa[i]y) sum;else sum--;if(sumcntt) {cntt;if(cnttk1) {printf(%d %d\n,l,n);break;}else printf(%d %d\n,l,i),li1;}}for(int i1;in;i) cnt[a[i]]0;
}int main() {int _; scanf(%d,_);while(_--) {solve();}}
