\(A. Chemistry\)
https://codeforces.com/contest/1888/submission/233505834
\(B. Raspberries\)
https://codeforces.com/contest/1888/submission/233506474
\(C. You Are So Beautiful\)
题意：给定一个长 \(n\) 的序列 \(a\) 。对于区间 \([l,r]\) ，如果 \(a\) 没有其它子序列（不一定连续）和这个区间完全相同，则这个区间合法。求出合法区间数量。
vp的时候一直没懂题意，样例都没数出来。然后看题解的时候才知道是子序列与选择的区间不同。放个subsquence在这警示一下。
解法：选择一个区间，只要左端点左端无自己，右端点右端无自己，就能保证一个区间作为子序列也是唯一的。感性证明一下的话就是，如果区间有其他子序列那么就是分散这个区间，而左右端点必须向外扩展，如果扩展不了显然不存在，而能扩展也一定能与原区间的中间段组合成新子序列。所以对每个如上的左端点寻找如上的右端点。
void solve(){
int n=read(),ans=0;
vector<int>a(n);
for(int i=0;i<n;i++){
a[i]=read();
}
map<int,int>mp;
vector<int>l,r;
for(int i=0;i<n;i++){
if(!mp[a[i]]){
mp[a[i]]++;
l.push_back(i);
}
}
mp.clear();
for(int i=n-1;i>=0;i--){
if(!mp[a[i]]){
mp[a[i]]++;
r.push_back(i);
}
}
reverse(r.begin(),r.end());
for(auto x:l){
ans+=r.size()-(lower_bound(r.begin(),r.end(),x)-r.begin());
}
cout<<ans<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(D1. Dances (Easy version)+D2. Dances (Hard version)\)
题意：给两个长度为数组（除 \(a\) 数组的第一个数字），最少删掉个数字后可以使任意排序的两个数组满足 \(a_i<b_i,1 \le a,b\le n\) ，求 \(a\) 数组的第一个数字依次为 \(1-m\) 时最少删掉数字个数的和。easy时，\(m==1\) 。
因为hard包含了easy的代码，而且都不是很难就放一个hard的了
int a[N],b[N],c[N],n,m;
bool check(int x) {
for(int i=1;i<=n-x;i++){
// cout<<i<<" "<<i+x<<'\n';
if(a[i]>=b[i+x]){
return false;
}
}
return true;
}
int bs1(int l, int r){ //左偏二分
while (l < r){
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
int bs2(int l, int r){ //右偏二分
while (l < r){
int mid = (l + r + 1) >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
int solve(int a1){
for(int i=2;i<=n;i++){
a[i]=c[i];
}
a[1]=a1;
sort(a+1,a+n+1);
sort(b+1,b+n+1);
return bs1(0,n);
}
void SOLVE(){
n=read(),m=read();
for(int i=2;i<=n;i++){
c[i]=read();
}
for(int i=1;i<=n;i++){
b[i]=read();
}
int ans_1=solve(1),l=1,r=m+1;
while (l < r){
int mid = (l + r) >> 1;
if (solve(mid)>ans_1) r = mid;
else l = mid + 1;
}
// cout<<l<<" "<<r<<'\n';
cout<<ans_1*m+(m-l+1)<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}