A – Aggressive cows
双·放·送：
【主站】《ZJUT2022入门题单Week3 程序简注》 – O
B – Friends and Subsequences
印象深刻的一道题，因为调的时候又出现玄学了，只是一条cout之差可以调半天，把人都调崩了（
要求有多少个相同位置区间满足：A区间最大值=B区间最小值
注意到区间左端点固定时，右端点变化，区间的最大/最小值是单调的，故可以用二分解决。同时不幸的是，区间内所有点都要满足这个条件，在仅二分右端点左/右界的时候会有问题，所以最终需要把满足条件的右端点的左界和右界都二分出来。
由于 $2 \times 10^5$ 的数据规模可以把 $O(n \cdot \sqrt{n})$ 卡掉，并且不涉及到修改操作，所以这里用st表储存区间最大/小值。
namespace lovelive{
typedef long long VAL;
//我日你先人
VAL mab[2][20][200005];
VAL abi[2][200005];
int n,SZ;
VAL ans;
VAL nico(bool isB,VAL a,VAL b){
if(isB)return min(a,b);
else return max(a,b);
}
VAL fenkuai(bool isB,int l,int r){
VAL lg=log2(r-l+1);
return nico(isB,mab[isB][lg][l],mab[isB][lg][r-(1<<lg)+1]);
}
void main(){
cin>>n;ans = 0;
for(int i=1;i<=n;i++){
cin>>abi[0][i];
mab[0][0][i] = abi[0][i];
}
for(int i=1;i<=n;i++){
cin>>abi[1][i];
mab[1][0][i] = abi[1][i];
}
for(int j=1;(1<<j)<n;j++){
for(int i=1;i<=n-(1<<j)+1;i++){
for(int maki=0;maki<2;maki++){
mab[maki][j][i] =
nico(maki,
mab[maki][j-1][i],
mab[maki][j-1][i+(1<<(j-1))]);
}
}
}
for(int i=1;i<=n;i++){
int l,r,mid,rr=-1,ll;
l = i;r = n;
while(l<=r){
mid = (l + r + 1) >> 1;
if(fenkuai(0,i,mid)<=fenkuai(1,i,mid)){
if(fenkuai(0,i,mid)==fenkuai(1,i,mid)) rr = mid;
l = mid + 1;
}else{
r = mid - 1;
}
}
if(rr==-1)continue;
l = i;r = rr;
while(l<=r){
mid = (l + r + 1) >> 1;
if(fenkuai(0,i,mid)>=fenkuai(1,i,mid)){
if(fenkuai(0,i,mid)==fenkuai(1,i,mid)) ll = mid;
r = mid - 1;
}else{
l = mid + 1;
}
}
ans += rr - ll + 1;
}
cout<<ans<<endl;
return;
}
}C – Enduring Exodus
N(1e5)个房间，k头牛和1个人，有的房间已经被占了，要求选择k+1个房间，使得人住的房间离最远的牛距离最短。
贪心得约翰与所有牛都要挤在一堆（在去掉中间的被占用房间后）的连续房间内，于是仅记录未被占用的房间编号，约翰和牛占用其中连续的一串房间。
确定了这一行人（牛）所要占据的房间之后，就需要确定约翰的位置了。然后就要用到三分了——由于即将被占领的房间可能实际上并不连续，所以这时候脑海里就有了一个类似于$\sum_{\mathclap{l\le i\le r}} |ai-x|$的函数图像，这个凸函数是个可以三分的经典样例。
namespace lovelive{
int ai[300005],n,m,cnt;
int ans;string s;
inline int calc(int l,int r,int cur){
return max(ai[cur]-ai[l],ai[r]-ai[cur]);
}
void main(){
cin>>n>>m>>s;cnt=0;
for(int i=1;i<=n;i++){
if(s[i-1]-'0'==0)ai[++cnt]=i;
}
ans = INT32_MAX;
for(int l=1,r=m+1;l<=cnt-m;l++,r++){
int ll=l,rr=r;
while(rr-ll>2){
int mid1=(ll+rr)/2;
int mid2=mid1+1;
if(calc(l,r,mid1)<calc(l,r,mid2)){
rr=mid2;
}else{
ll=mid1;
}
}//当范围内仅有三个约翰可选位置时，一个个判断过去
for(int i=ll;i<=rr;i++){
ans = min(ans,calc(l,r,i));
}
}
cout<<ans<<endl;
}
}D – Maximize!
有一个可重集合，初始为空。共Q(5e5)次操作，添加一个不小于集合中任一数的数，或者询问子集中max(最大值-平均值)。
由于添加数的时候是按照非递减的顺序加的，所以当前加进来的数可以作为当前数集的最大值，那么压力就来到了当前数集的最小平均值上了。
非递减顺序添加数字带来的另一个好处是选取数字的时候可以按照从小到大的顺序选，在子集中已经有一个最大值的情况下从小到大加数字，会使平均值先减小再变大，从而形成一个可以三分的凸函数（像极了往杯子里加水的重心变化）。
由于该题的精度要求十分离谱，于是采用了long double和cout<< fixed << setprecision(8) <<组合（
namespace lovelive{
typedef LL VAL;
VAL ai[500005],sumi[500005],b;
int n,q,a,l,r,mid;
long double ans,nico = 1;
long double calc(int r,int rr){
return (sumi[r]+ai[rr])/(r+nico);
}
void main(){
cin>>q;n=0;sumi[n]=0;
while(q--){
cin>>a;
if(a==1){
cin>>ai[++n];
sumi[n] = sumi[n-1] + ai[n];
}else{
l = 0 ; r = n - 1;
while(r-l>2){
mid = (l + r) >> 1;
if(calc(mid,n)>calc(mid+1,n)){
l = mid;
}else{
r = mid + 1;
}
}
ans = 0;
for(int i=l;i<=r;i++){
ans = max(ans,ai[n] - calc(i,n));
}
cout<< fixed << setprecision(8) << ans<<endl;
}
}
}
}E – Array Splitting
差分，前缀和的取反操作：
a[i] 是 b[i] 的前缀和数组，b[i] 是 a[i] 的差分数组。
差分不仅可以用在例如“欲将数组a的[2~7]这一区间内加上一个数6，只需将其差分数组b的b[2]+6，b[8]-6即可”的地方，还有不少应用。本题就是其中一种。
注意到数组已经被排序，选取其中连续子数组的最大/最小值就变成了取其的两个端点。然后意识到两端点之差等于两端点之间所有的gap（两数之差）之和；如果子数组只有一个点，自然就没有gap，最大最小值之差也等于0。再者，将$n$个数连续分割成$m$块等效于插入$n-m-1$个隔板，自然作用于差分数组而言就是删掉了$n-m-1$个数。分开求切割后所有“最大值-最小值”之和，就很容易被等效于直接把全部有效gap加起来（迎 新 赛.jpg）。为了使结果最小，那么就把最大的几个gap删掉！
namespace lovelive{
int ai[300005],bi[300005],n,m;
LL ans;
void main(){
cin>>n>>m>>ai[1];
for(int i=1;i<n;i++){
cin>>ai[i+1];
bi[i] = ai[i+1] - ai[i];
}
ans=0;
sort(bi+1,bi+n);
for(int i=1;i<=n-m;i++){
ans += bi[i];
}
cout<<ans<<endl;
}
}F – Cinema
n(2e5)个人，m(2e5)部电影，每个人会一门语言ai(1e9)，每部电影有两个权值bi,ci(1e9)且二者不相等。要你安排每个人去看一部电影，可以多个人看同一部，你要在最大化ai==bj的前提下，最大化ai==cj。
过于简单的离散化很容易会被直接排序冲淡其离散化的色彩（不过用map好像也是log级别的复杂度），就像【主站】《《ZJUT2022入门题单Week3 程序简注》 – H – 数数》一样。注意电影数据需要离线处理。
namespace lovelive{
map<int,int> mp;
int n,m,ai[200005],ia[200005],ib[200005],cnta,cntb,ansa=0,ansb=0,ansi=1;
void main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>ai[i];
}
sort(ai+1,ai+n+1);
cin>>m;
for(int i=1;i<=m;i++){
cin>>ia[i];
}
for(int i=1;i<=m;i++){
cin>>ib[i];
cnta = upper_bound(ai+1,ai+n+1,ia[i])-lower_bound(ai+1,ai+n+1,ia[i]);
cntb = upper_bound(ai+1,ai+n+1,ib[i])-lower_bound(ai+1,ai+n+1,ib[i]);
if(cnta>ansa || (cnta==ansa&&cntb>ansb)){
ansi = i;
ansa = cnta;
ansb = cntb;
}
}
cout<<ansi<<endl;
}
}G – Covered Points Count
在数轴上有n(2e5)条线段，每条线段li,ri(1e18)，对于k=1到n，输出恰好被k条线段覆盖的整数点的数量
一开始SAT佬兴冲冲地说这是线段树，但我线段树模板（发现模板文中的“花哨版”本来写成了一个头文件测试通过，但复制到主代码里就老出问题）调到一半发现 $4 \times 10^5$ 的端点再加上插点法会有 $8 \times 10^5$ 的点数和 $3.2 \times 10^6$ 的线段树数组大小，线段树很容易爆，于是就中止了（后面SAT佬也发现问题了）。
很明显我把差分忘掉了（
差分不仅可以用在例如“欲将数组a的[2~7]这一区间内加上一个数6，只需将其差分数组b的b[2]+6，b[8]-6即可”的地方，还有……
namespace lovelive{
LL pnts[800005],cnts[800005],cnt,pm[800005];
map<LL,int> mp;
LL n,maxcnt,nico[800005];
pair<LL,LL> segs[200005];
void main(){
memset(cnts,0,sizeof(cnts));
memset(nico,0,sizeof(nico));
cin>>n;cnt = 0;
for(int i=1;i<=n;i++){
cin>>segs[i].first>>segs[i].second;
pnts[i*2-1] = segs[i].first;
pnts[i*2] = segs[i].second;
}
sort(pnts+1,pnts+2*n+1);
pnts[2*n+1]=INT64_MAX;
for(int i=1;i<=2*n;i++){
mp[pnts[i]] = ++cnt;
pm[cnt] = pnts[i];
while(pnts[i+1]==pnts[i]&&i<=2*n)i++;
if(pnts[i+1]-pnts[i]>1){
pm[++cnt] = pnts[i]+1;
}
}
for(int i=1;i<=n;i++){
nico[mp[segs[i].first]] ++;
nico[mp[segs[i].second]+1] --;
}
for(int i=1;i<=cnt;i++){
nico[i] += nico[i-1];
cnts[nico[i]] += pm[i+1] - pm[i];
}
for(int i=1;i<=n;i++){
cout<<cnts[i]<<" ";
}
cout<<endl;
}
}H – Frets On Fire
长度为n(1e5)的数组s，构造一个n*1e18的矩阵，第i行j列的数字是s[i]+j。共有q(1e5)次询问，每次询问第l到r列有多少个不同的数字。
经典题目中出现了一堆生词就头大，即使这些只是一些昆虫的名字（
注意到最终的结果和s[i]怎么排的没有任何关系，所以先给s[i]排个序再进行进一步分析。
然后在这个重排过的s[i]中可以发现，s[i]和s[i+1]会重复的充要条件是s[i] + r >= s[i+1] + l，移一下项就会变成s[i+1] - s[i] <= r - l，这，就是差分。
然而事情还没有结束，朴素的差分还是会TLE。还是“最终的结果和s[i]怎么排的没有任何关系”，这也就意味着 最终的结果和差分数组怎么排的没有任何关系 。于是，将差分数组重新排序之后进行二分可以大幅减少计算s[i+1] - s[i] <= r - l的时间复杂度，从 $O(N)$ 砍到了 $O(log(N))$ 。最后把差分数组重新加起来，事情就变回了前缀和，顺便把求s[i+1] - s[i]之和从 $O(N)$ 砍到了 $O(1)$ 。
由于代码中对于点-点的间隔做了一些处理，所以看起来有些怪。
namespace lovelive{
//s[l]+r>=s[r]-l
//s[r]-s[l]<=l+r
LL ai[100005],bi[100005];
int n,m,mid;LL a,b,ans,cnt;
void main(){
cin>>n;cnt = 0;
for(int i=1;i<=n;i++){
cin>>ai[i];
}
sort(ai+1,ai+n+1);
bi[1] = ai[1];
for(int i=1;i<n;i++){
bi[i] = max(0ll,ai[i+1]-ai[i]-1);
if(ai[i+1]-ai[i])cnt++;
}
sort(bi+1,bi+n);
for(int i=1;i<n;i++){
ai[i+1] = ai[i] + bi[i];
}
sort(ai+1,ai+n+1);
cin>>m;
for(int i=1;i<=m;i++){
cin>>a>>b;ans = cnt + 1;
/*会超时的写法
for(int i=1;i<n;i++){
ans += bi[i] - max(0ll,bi[i]-(b-a));
}*/
mid = upper_bound(bi+1,bi+n,(b-a)) - bi;
ans += ai[mid] - ai[1];
ans += (n-mid) * (b-a);
ans += (b-a);
cout<<ans<<endl;
}
}
}J – Hardcore Hangman
交互体验题，回想起了比赛时交互题调半天的恐惧（
注意到 $2^5 = 32 \ge 26$ ，也就是说每一个字母可以被表示成一个五位二进制，正好可以用五次查询查出该二进制位为1的所有字母位置的集合，再对这些集合根据字母的二进制位进行集合操作（将所有该字母不该出现的字母位置做个并集，然后相对所有字母位置的全集做个补集），就可以得到单个字母的位置集合。
如果不放心的话可以单独做一次包含了所有字母的查询，获得上文中的全集，加上这次查询也就只有六次查询，没问题！
也算是一种二分思想？
namespace lovelive{
string que[]={
"11111111111110000000000000",
"11111110000001111111000000",
"11110001110001111000111000",
"11001101101101100110110110",
"10101011011011010101101101",
},tmp;
set<int> res[5],tmps,remov;
char ans[10005];
int maxn,ansn,ansi;
void query(int time){
if(time==-1){
cout<<"? abcdefghijklmnopqrstuvwxyz"<<endl;
cin>>ansn;
for(int i=1;i<=ansn;i++){
cin>>ansi;
maxn = max(maxn,ansi);
}
}else{
tmp = "";
for(int i=0;i<26;i++){
if(que[time][i] == '1')
tmp += ('a'+i);
}
cout<<"? "<<tmp<<endl;
cin>>ansn;
for(int i=1;i<=ansn;i++){
cin>>ansi;
res[time].insert(ansi);
}
}
}
void main(){
maxn = 0;
query(-1);
ans[maxn] = '\0';
for(int i=0;i<5;i++){
res[i].clear();
query(i);
}
for(int i=0;i<26;i++){
tmps.clear();
remov.clear();
for(int j=0;j<5;j++){
for(int k=1;k<=maxn;k++){
if(que[j][i]=='1'){
if(!(res[j].count(k))){
remov.insert(k);
}
}else{
if(res[j].count(k)){
remov.insert(k);
}
}
}
}
for(int k=1;k<=maxn;k++){
if(!remov.count(k)){
ans[k-1] = i + 'a';
}
}
}
cout<<"! "<<ans<<endl;
return;
}
}
