本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-12 13:08:06

[AGC020D] Min Max Repetition

题目考察：贪心，数学，二分。
题目简述：
$q$ 次询问，给你 $a,b,c,d$，有一字符串 $s$：

• $\displaystyle|s|=a+b$，$s$ 由 $a$ 个 A 和 $b$ 个 B 组成。
• 同时，最大连续相同字符数最小。
• 同时，字典序最小。

求该字符串的第 $c$ 位到第 $d$ 位。
数据范围：

• $1\le q\le 10^3$
• $1\le a,b\le 5\times 10^8$
• $1\le c\le d\le a+b$
• $1\le d-c+1\le 100$

首先我们肯定可以得出最小的最大连续相同字符数是 $\displaystyle k=\max(\lceil\frac{a}{b+1}\rceil,\lceil\frac{b}{a+1}\rceil)$。
我们让 B 尽可能靠后，那么这个字符串长成这样： $$\text{AAA\dots ABAAA\dots ABAAA\dots ABAAA\dots ABB\dots BABB\dots BABB\dots BB}$$ 那么我们可以二分找出其分界点，那么我们还需要一个判断条件。
设分界点为 $x$，则 A 在前面使用了 $\displaystyle\lfloor\frac{x}{k+1}\rfloor\times k+x\bmod (k+1)$ 个，那么 A 在后面就要使用 $\displaystyle a-\lfloor\frac{x}{k+1}\rfloor\times k-x\bmod (k+1)$ 个；B 在前面使用了 $\displaystyle\lfloor\frac{x}{k+1}\rfloor$ 个，那么 B 在后面使用了 $\displaystyle b-\lfloor\frac{x}{k+1}\rfloor$ 个。
则我们得到判断条件： $$(a-\lfloor\frac{x}{k+1}\rfloor\times k-x\bmod (k+1))\times k<b-\lfloor\frac{x}{k+1}\rfloor$$ 然后我们发现在前半部分当 $i\bmod (k+1)=0$ 时 $s_i$ 是 B，A 反之；在后半部分当 $(a+b-k+1)\bmod (k+1)=0$ 时是 B，A 反之。

单次询问时间复杂度为 $\Theta(\log_2(a+b)+(d-c))$。
代码：

#include<bits\/stdc++.h>
#define inl inline
#define reg register
#define int long long
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(reg int i=x;i<=(y);++i) 
#define per(i,x,y) for(reg int i=x;i>=(y);--i)
#define rpr(i,x,y,z) for(reg int i=x;i<=(y);i+=z)
#define epe(i,x,y,z) for(reg int i=x;i>=(y);i-=z)
#define endl '\n'
#define INF (int)1e16
#define pb push_back
#define fi first
#define se second
#define lcm(x,y) x\/__gcd(x,y)*y
#define ull unsigned long long
#define prr make_pair
#define pii pair<int,int> 
#define gt(s) getline(cin,s)
#define at(x,y) for(reg auto x:y)
#define ff fflush(stdout)
#define mt(x,y) memset(x,y,sizeof(x))
#define idg isdigit
#define fp(s) string ssss=s;freopen((ssss+".in").c_str(),"r",stdin);freopen((ssss+".out").c_str(),"w",stdout);
#define sstr stringstream 
using namespace std;
inl bool check(int x,int k,int a,int b){
\/\/	cout<<(a-x\/(k+1)*k-x%(k+1))<<' '<<b-x\/(k+1)<<endl;
	return (a-x\/(k+1)*k-x%(k+1))*k<b-x\/(k+1);
}
inl int lower(int l,int r,int k,int a,int b){
	reg int mid=0,ans=-1,fl=l,fr=r;
	while(l<=r){
		mid=l+r>>1;
\/\/		cout<<mid<<endl;
		if(check(mid,k,a,b)){
			r=mid-1;
			ans=mid;
		}else l=mid+1;
	}
	if(ans!=-1) return ans;
	else if(fl==l) return -1;
	else return r+1;
}
inl void solve(){
	reg int a,b,c,d,k,x;
	cin>>a>>b>>c>>d;
	k=max(max((int)ceil(a\/(b+1.0)),(int)ceil(b\/(a+1.0))),1ll);
	x=lower(0,a+b,k,a,b);
\/\/	cout<<k<<' '<<x<<endl;
	rep(i,c,d)
		if(i<=x)
			if(i%(k+1)) cout<<'A';
			else cout<<'B';
		else if((a+b-i+1)%(k+1)) cout<<'B';
		else cout<<'A';
	cout<<endl;
}
signed main(){
	fst;
	reg int t;
	cin>>t;
	while(t--) solve();
	return 0;
}