分治专题

分治初步

归并排序求逆序对

Sol：在归并排序过程中，本身就是分治思想，递归的对左区间排序，右区间同理。对于已经有序两段进行合并只需要$O(n)$的时间，递归共$log_{2}{n}$层，时间复杂度为$O(nlog_{2}{n})$

debug:1.对于没有到达边界的一段也需要放入临时数组，并且继续统计答案

2，先审核一遍代码，出现了没有调用函数，只打个括号的情况，没有报错，需要注意

int solve(int l,int r){
	if(l==r)return 0;
	int mid=(l+r)>>1;
	int res=solve(l,mid)+solve(mid+1,r);
	int pl=l,pr=mid+1;
	int cnt=0;
	while(pl<=mid&&pr<=r){
		if(a[pl]<=a[pr]){
			c[++cnt]=a[pl++];
			res+=pr-1-(mid+1)+1;
			}
		else {
			c[++cnt]=a[pr++];
		}
	}
	//还需要处理没到边界的一侧
	while(pl<=mid){c[++cnt]=a[pl++];res+=pr-(mid+1);}
	while(pr<=r)c[++cnt]=a[pr++];
	int k=1;
	for(int i=l;i<=r;i++)a[i]=c[k++];
	return res;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	int ans=solve(1,n);
	//for(int i=1;i<=n;i++)cerr<<a[i]<<" ";
	cout<<ans<<endl;
}

Codeforces Round 656 (Div. 3) D

a-Good String

定义：字符串s 为一个c-好串（c 为一个字符）时，必须满足：

  1. 当$|s| = 1$ ，$s = c$

  2. 当$|s| > 1$, $s$ 的左半部分为全为 $c$，右半部分为一个 (c+1)-好串 或者 $s$ 的右半部分为全为 $c$，左半部分为一个 (c+1)-好串

其中 $|s|$ 代表 字符串 $s$ 的长度。

举个例子：当 $s=“cdbbaaaa”$时，$s$ 是一个 a-好串

现在，给你一个字符串 $s$ ( $|s| = 2^k$ ),问最少替换多少个字符，使其为一个 a-好串。

Sol:注意题目给出的字符串长度是特殊的，结合题目意思是非常明显的递归求解暗示。每轮中我们只需要决策是选择前半段作为当前轮字母对应段还是后半段。选择以后，另一段的代码递归求解即可，注意递归边界处理。

string s;
int cal(int l,int r,int lev){
	int res=0;
	char c=lev+'a';
	if(l==r){
		if(s[l]==c)return 0;
		return 1;
	}
	int mid=(l+r)>>1;
	int c1=0,c2=0;
	
	for(int i=l;i<=mid;i++)if(s[i]!=c)c1++;
	for(int i=mid+1;i<=r;i++)if(s[i]!=c)c2++;
	res=min(c1+cal(mid+1,r,lev+1),c2+cal(l,mid,lev+1));
	return res;
}
void solve(){
	cin>>n;
    cin>>s;
	s=" "+s;
	int ans=cal(1,n,0);
	cout<<ans<<endl;
}

平面最近点对https://www.luogu.com.cn/problem/P1429

P7883 平面最近点对（加强加强版）
给定平面上 $n$ 个点，找出其中的一对点的距离，使得在这 $n$ 个点的所有点对中，该距离为所有点对中最小的
数据保证 $0\le x,y\le 10^9$

Sol:本题存在$O(nlogn)$的解法，对于排序的复杂度采用归并y来降低https://www.luogu.com.cn/article/aihyptbk，这里先给出朴素的$O(n(log_{}{n})^2)$做法

整体思路：以x大小为分界线进行分治，左边内部的最近点对递归解决，右边同理。对于左右交界的贡献，首先考虑横坐标距离分界线大于d无法更新答案，对于这些点按y排序，对于其中一个点，纵坐标距离大于d也不可能更新，可以证明一个点可以用来更新答案的点不超过6个(只考虑中坐标比自己大的点，偏序不重复）。

struct node{
	db x,y;
	bool operator<(const node &A)const{
		return x<A.x;
	}
}a[N],c[N];
db dis(node c,node d){
    db c1=c.x-d.x,c2=c.y-d.y;
    return sqrt(c1*c1+c2*c2);
}
db cal(int l,int r){
	if(l==r)return 1e12;
	int cnt=0;int mid=(l+r)>>1;
	db d=min(cal(l,mid),cal(mid+1,r));
	for(int i=l;i<=r;i++){
		if(fabs(a[i].x-a[mid].x)<d){
			c[++cnt].y=a[i].x;
			c[cnt].x=a[i].y;
		}
	}
	sort(c+1,c+1+cnt);
	for(int i=1;i<=cnt;i++){
		for(int j=i+1;j<=cnt&&fabs(c[j].y-c[i].y)<d;j++){
			d=min(d,dis(c[i],c[j]));
		}
	}
	return d;
}
void solve(){
	//cerr<<18*18*N<<endl;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
	sort(a+1,a+1+n);
	db  ans=cal(1,n);
	baoliu(ans,4);
}

序列分治系列

1.给一个数组，求数组的所有的子区间的最大公约数的和。保证 $1\le N\le 3\times 10^5$，$0\le a_i\le 10^6$。https://www.luogu.com.cn/problem/SP32079

Sol:考虑序列分治，每次只算跨过mid的答案，不跨过mid的答案递归下去。考虑每一层的复杂度。在当前区间我们统计的区间一定是由mid向左的后缀，和mid向右的前缀组成。由logtrick我们知道，gcd端点固定，另一边最多logW种取值且这样固定mid拓展两端，gcd取值一定单调递减。我们可以开两个桶记录出现次数。最后以2个log的代价统计这段的答案。

$O(n)=O(n/2)+O(log^2n+n) \to O(nlogn)$

开桶实测:选择map

(时间损耗：$customhash > pbds > unordered_map > map$

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
void solve() {
    int n;
    cin >> n;
    ll ans = 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    auto cdq = [&](auto self, int l, int r) {
        int mid = (l + r) >> 1;
        if (r == l) {
            ans += a[l];
            return;
        }
        self(self, l, mid);
        self(self, mid + 1, r);
        map<int, int> suf, pre;
        int tmp = 0;
        for (int i = mid; i >= l; i--) {
            tmp = gcd(a[i], tmp);
            suf[tmp]++;
        }//算mid左的gcd取值
        tmp = 0;
        for (int i = mid + 1; i <= r; i++) {
            tmp = gcd(a[i], tmp);
            pre[tmp]++;
        }//算mid向右的gcd取值
        for (auto [x1, y1] : pre) {O(log)*O(log)
            for (auto [x2, y2] : suf) {
                ans += (ll)gcd(x1, x2) * (ll)y1 * y2;
            }
        }
    };
    cdq(cdq, 1, n);
    cout << ans << endl;
}