【省选模拟】complex（启发式分裂）

本文主要是介绍【省选模拟】complex（启发式分裂），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$3.14$
题解：如果一个大区间不合法那么必存在一种颜色使得它在这个区间的出现次数 $< b [l e n]$ ，注意到 $l e n$ 缩短 $b [l e n]$ 将增大，于是我们选出的子区间必定不包含这种颜色
这种颜色会将区间分成若干段，但是没必要分裂完，我们找到左右第一个不满足的颜色往下分，复杂度就是启发式分裂的 $O(n\log n)$

#include<bits/stdc++.h>
#define cs const
using namespace std;
int read(){int cnt=0, f=1; char ch=0;while(!isdigit(ch)){ ch=getchar(); if(ch=='-') f=-1; }while(isdigit(ch)) cnt=cnt*10+(ch-'0'), ch=getchar();return cnt*f;
}
cs int N = 1e6 + 50;
int n, a[N], b[N], bin[N];
int work(int l, int r);
int work_l(int l, int mid, int r){int as = 0;for(int i=l; i<=mid; i++) --bin[a[i]];if(mid+1<=r) as=max(as,work(mid+1,r));for(int i=l; i<mid; i++) bin[a[i]]=0;for(int i=l; i<mid; i++) ++bin[a[i]];if(l<=mid-1) as=max(as,work(l,mid-1));return as;
}
int work_r(int l, int mid, int r){int as = 0;for(int i=mid; i<=r; i++) --bin[a[i]];if(l<=mid-1) as=max(as,work(l,mid-1));for(int i=mid+1; i<=r; i++) bin[a[i]]=0;for(int i=mid+1; i<=r; i++) ++bin[a[i]];if(mid+1<=r) as=max(as,work(mid+1,r));return as;
}
int work(int l, int r){int len=r-l+1,i=l,j=r;while(i<=j){if(bin[a[i]]<b[len]) return work_l(l,i,r);if(bin[a[j]]<b[len]) return work_r(l,j,r);i++; j--;} return len;
}
int main(){freopen("complex.in","r",stdin);freopen("complex.out","w",stdout);n=read();for(int i=1; i<=n; i++) a[i]=read(),++bin[a[i]];for(int i=1; i<=n; i++) b[i]=read();cout<<work(1,n); return 0;
}