离散化：用排名代表原数据关系
| sort(a+1,a+n+1);
int len=unique(a+1,a+n+1)-a;
for(int i=1;i<=n;i++)
a[i]=lower_bound(a+1,a+len+1,a[i])-a;
|
lower_bound基于二分查找，故总时间复杂度为\(O(n\log n)\)，使用前提是待施数组为非降的。参数为：某数组元素地址（一般是首地址）、某数组元素地址（一般是尾地址）、需要查询的数，函数将返回前两个参数之间的最小的大于等于待查询数的地址。
upper_bound为“大于”操作符。
如果需要查找最大的小于（小于等于）某数，可使用上述函数，多减去1即可（因相对应的数下标是相邻的）
unique函数可用于去除容器（数组）中相邻的、重复出现的元素（使用前需排序），参数为：集合起始地址，集合尾地址（最后一个元素的下一个元素地址），返回去重后尾地址（减集合名即得到元素数量）。
【前缀和】【分治】LuoguP1115 最大子段和
【题目大意】序列\(A=\left \{ a_1,a_2,\cdots,a_n\right \}\)，求序列\(a_L,a_{L+1},\cdots,a_R,1\le L<R\le n\)，使此子序列和最大。
\(O(n)\)做法：构造前缀和序列\(B=\left \{ b_1,b_2,\cdots,b_n\right \}\)，相当于求\(b_R-b_L,0\le L<R\le n\)的最大值。
\(O(1)\)维护\(1\sim i\)的前缀和最大值即可。
\(O(n\log n)\)做法：分治法。对于区间\((L,R),mid=(L+R)/2\)，当\(L=R\)时返回\(a_L\),否则有以下三种情况：
（1）最大子区间出现在\([L,mid]\)中；
（2）最大子区间出现在\([mid+1,R]\)中；
（3）最大子区间包括\(a_{mid},a_{mid+1}\)
对于（3），枚举得到\([mid+1,R],[L,mid]\)的最大值即可，时间复杂度为\(O(n)\)
时间复杂度满足：\(\displaystyle T(n)=2T(\frac{n}{2})+n\)
记\(n=2^k\)，有\(T(2^k)=2T(2^{k-1})+2^k\)，可得\(T(2^k)=k\cdot 2^k\)，时间复杂度为\(O(n\log n)\)
LuoguP1115 最大子段和前缀和做法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | #include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,minn,ans,a[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) a[i]+=a[i-1];
minn=0;ans=-2e9;
for(int i=1;i<=n;i++)
{
ans=max(ans,a[i]-minn);
minn=min(minn,a[i]);
}
cout<<ans;
return 0;
}
|
LuoguP1115 最大子段和分治做法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | #include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N],n;
int get(int l,int r)
{
if(l==r) return a[l];
else
{
int mid=l+r>>1;
int ans1=0,ans2=0,maxx=-2e9;
for(int i=mid+1;i<=r;i++)
ans1+=a[i],maxx=max(maxx,ans1);
ans1=maxx;
maxx=-2e9;
for(int i=mid;i>=l;i--)
ans2+=a[i],maxx=max(maxx,ans2);
ans2=maxx;
return max(max(get(l,mid),get(mid+1,r)),ans1+ans2);
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
cout<<get(1,n);
return 0;
}
|
【单调队列优化】LuoguU192528 最大子序和
【题目大意】同前，但有额外约束，序列长度不能超过\(m\)
作前缀和后，对于以\(i\)结尾的序列最大值，\(ans=b_i-\min\limits_{i-m-1\le j<i}b_j\)，使用单调队列优化即可。
【分治】【树状数组】LuoguP1908 逆序对
【题目大意】求解序列\(A=\left \{ a_1,a_2,\cdots,a_n\right \}\)的逆序对数量。
LuoguP1908 逆序对树状数组实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | #include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,a[N],h[N];
long long t[N*4],ans;
void add(int x,int k)
{while(x<=n) t[x]+=k,x+=x&(-x);}
long long query(int x)
{
long long res=0;
while(x){res+=t[x],x-=x&(-x);}
return res;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),h[i]=a[i];
sort(h+1,h+n+1);
int m=unique(h+1,h+n+1)-h;
for(int i=1;i<=n;i++)
a[i]=lower_bound(h+1,h+m+1,a[i])-h;
for(int i=1;i<=n;i++)
{
ans+=i-1-query(a[i]);
add(a[i],1);
}
cout<<ans;
return 0;
}
|
LuoguP1908 逆序对分治实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | #include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int a[N],b[N],n;
long long get(int l,int r)
{
if(l==r) return 0;
else
{
long long res=0;
int mid=l+r>>1;
res+=get(l,mid)+get(mid+1,r);
int L=l,R=mid+1,posi=l-1;
while(L<=mid&&R<=r)
{
if(a[L]<=a[R]) b[++posi]=a[L],L++;
else
b[++posi]=a[R],res+=mid-L+1,R++;
}
while(L<=mid)
b[++posi]=a[L],L++;
while(R<=r) b[++posi]=a[R],R++;
for(int i=l;i<=r;i++) a[i]=b[i];
return res;
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
cout<<get(1,n);
return 0;
}
|
【GCD】【ST表】【分治】【暴力】LuoguP5502 最大公约数
给定长度为\(N\)的序列\(A_i\).定义\(W(L,R)=\gcd(a_L,a_{L+1},\cdots,a_R)\cdot(R-L+1),1\le L<R\le n\)
求\(W_{max}\)
分治法：同上，关键是处理跨越\(mid\)的部分。
证明：对于序列\(a_1,a_2,\cdots,a_n\)，\(\gcd(a_L,a_{L+1},\cdots,a_{R})\)最多只有\(\log_2K\)种取值（\(K=\max\limits_{L\le i\le R}a_i\)）。
以右半段为基准，设当前的\(GCD=\gcd(a_{mid+1},\cdots,a_i)\)可能出现两种情况：
（1）\(\gcd(GCD,a_{i+1})=a_i\)，根据贪心，一定更优，直接加入；
（2）否则对此情况进行左半段扫描记录，时间复杂度\(O(R-L)\)
注意：在结束后仍要进行一边扫描。
左半段的处理同理。算法时间复杂度为\(O(n\log n\log K)\)
LuoguP5502 最大公约数分治实现一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74 | #include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
long long a[N];
int n;
long long gcd(long long x,long long y)
{
if(!y) return x;
return gcd(y,x%y);
}
long long get(int l,int r)
{
if(l==r) return a[l];
else
{
int mid=l+r>>1;
long long curgcd=a[mid+1],ans=a[mid+1];
long long temp;
for(int i=mid+2;i<=r;i++)
{
long long newgcd=gcd(curgcd,a[i]);
if(newgcd==curgcd)
continue;
else
{
temp=curgcd;
for(int j=mid;j>=l;j--)
{
temp=gcd(temp,a[j]);
ans=max(ans,(i-j)*temp);
}
curgcd=newgcd;
}
}
temp=curgcd;
for(int j=mid;j>=l;j--)
{
temp=gcd(temp,a[j]);
ans=max(ans,(r-j+1)*temp);
}
curgcd=a[mid];
for(int i=mid-1;i>=l;i--)
{
long long newgcd=gcd(curgcd,a[i]);
if(newgcd==curgcd)
continue;
else
{
long long temp=curgcd;
for(int j=mid+1;j<=r;j++)
{
temp=gcd(temp,a[j]);
ans=max(ans,(j-i)*temp);
}
curgcd=newgcd;
}
}
temp=curgcd;
for(int j=mid+1;j<=r;j++)
{
temp=gcd(temp,a[j]);
ans=max(ans,(j-l+1)*temp);
}
return max(max(get(l,mid),get(mid+1,r)),ans);
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
cout<<get(1,n);
return 0;
}
|
分治的第二种思路：由于左右的两段算出的\(\gcd\)是稀疏的，可使用双指针：
初始化\(L=R=mid\)，先以左半段为基准，\(cur=a_{mid}\)。
若\(a_{r+1}\text{ mod }cur=0\)，则不断将\(r\)向右移，消除此类重复情况。
若\(a_{l-1}\text{ mod }cur=0\)，则不断将\(l\)向左移。
计算当前权值，\(l\)递减。再以右半段为基准处理一遍。时间复杂度为\(O(n\log n\log K)\)
LuoguP5502 最大公约数分治实现二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 | #include<bits/stdc++.h>
using namespace std;
long long n,a[200005];
long long gcd(long long x,long long y)
{
if(!y) return x;
return gcd(y,x%y);
}
long long divide(int L,int R)
{
if(L==R) return a[L];
long long current,maxx=0;
int mid=L+R>>1,l,r;
l=r=mid,current=a[mid];
while(L<l&&r<=R)
{
current=gcd(current,a[--l]);
while(r<R&&!(a[r+1]%current)) r++;
while(L<l&&!(a[l-1]%current)) l--;
maxx=max(maxx,(r-l+1)*current);
}
l=r=mid,current=a[mid];
while(L<=l&&r<R)
{
current=gcd(current,a[++r]);
while(r<R&&!(a[r+1]%current)) r++;
while(L<l&&!(a[l-1]%current)) l--;
maxx=max(maxx,(r-l+1)*current);
}
return max(max(divide(L,mid),divide(mid+1,R)),maxx);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
printf("%lld\n",divide(1,n));
return 0;
}
|
ST表与倍增法：预处理\(\gcd\)的ST表，对左端点\(L\)进行普通枚举，对右端点\(R\),使用倍增法快速跳过相同\(\gcd\)的数段，对于单次左端点枚举，右端点循环的时间复杂度为\(O(\log A)\)，算法时间复杂度为\(O(n\log n\log K)\)
LuoguP5502 最大公约数倍增实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 | #include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,lg[N];
long long st[N][25],ans;
long long gcd(long long x,long long y)
{
if(!y) return x;
return gcd(y,x%y);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) scanf("%lld",&st[i][0]);
for(int i=2;i<=n;i++) lg[i]=lg[i/2]+1;
for(int i=1;i<=lg[n];i++)
for(int j=1;j+(1<<i)-1<=n;j++)
st[j][i]=gcd(st[j][i-1],st[j+(1<<(i-1))][i-1]);
for(int i=1;i<=n;i++)
{
int j=i;
long long curgcd=st[i][0];
while(j<=n)
{
curgcd=gcd(curgcd,st[j][0]);
for(int k=lg[n-i];k>=1;k--)
if(st[j][k]&&st[j][k]%curgcd==0)
j+=(1<<k)-1;
ans=max(ans,(j-i+1)*curgcd);
j++;
}
}
cout<<ans;
return 0;
}
|
暴力枚举与优化实现：由于\(\gcd\)的性质，可以枚举右端点\(i\)，左端点为\(L\)，\([L,i]\)区间不同的\(\gcd\)数量不超过\(\log A\)。对于相同的\(\gcd\)，仅保留\(L\)最小的。可以使算法时间复杂度降低到\(O(n\log A)\)
LuoguP5502 最大公约数暴力枚举与优化实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43 | #include<bits/stdc++.h>
using namespace std;
struct node{long long num;int posi;};
long long gcd(long long x,long long y)
{
if(!y) return x;
return gcd(y,x%y);
}
queue<node> q,lis;
long long x,ans;
int n;
int main()
{
cin>>n;cin>>x;
ans=x;
q.push((node){x,1});
for(int i=2;i<=n;i++)
{
scanf("%lld",&x);
while(!q.empty())
{
node temp=q.front();q.pop();
temp.num=gcd(temp.num,x);
lis.push(temp);
}
while(!lis.empty())
q.push(lis.front()),lis.pop();
q.push((node){x,i});
while(!q.empty())
{
node temp=q.front();
lis.push(temp);
q.pop();
while(!q.empty()&&temp.num==q.front().num)
q.pop();
ans=max(ans,(i-temp.posi+1)*temp.num);
}
while(!lis.empty())
q.push(lis.front()),lis.pop();
}
cout<<ans;
return 0;
}
|
【单调栈优化】【分治】LuoguP2422 良好的感觉
分治：时间复杂度\(O(n\log n)\)，步骤可参考上一题。
仅考虑横跨\(mid\)的部分。考虑以右半段为基准，设左右指针均指向\(mid\)，当前区间最小值\(MIN=a_{mid}\)，若\(a_{L-1}\ge MIN\)，根据贪心更优，\(L递减\)，\(R\)同理，无法移动后计算当前所求值，\(R\)右移一格。左半段同理。
LuoguP2422 良好的感觉分治实现
```
include
using namespace std;
const int N=1e5+5;
long long a[N];
int n;
long long get(int l,int r)
{
if(l==r) return a[l];
else
{
int mid=l+r>>1;
long long ans=0,minn=a[mid],num=0;
int L=mid,R=mid;
while(L>=l&&R<=r)
{
minn=min(a[L],minn);
num+=a[L];
while(a[R+1]>=minn&&R+1<=r) R++,num+=a[R];
while(a[L-1]>=minn&&L-1>=l) L--,num+=a[L];
ans=max(ans,(numminn));
L--;
}
num=0,minn=a[mid],L=R=mid;
while(L>=l&&R<=r)
{
minn=min(a[R],minn);
num+=a[R];
while(a[R+1]>=minn&&R+1<=r) R++,num+=a[R];
while(a[L-1]>=minn&&L-1>=l) L--,num+=a[L];
ans=max(ans,(numminn));
R++;
}
return max(max(get(l,mid),get(mid+1,r)),ans);
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
cout<<get(1,n);
return 0;
}```
单调栈优化：时间复杂度\(O(n)\)，考虑每个\(a_i\)，原所有区间的集合可划分为以\(a_i\)为最小值的\(i\)个集合，分别求出\(L_{min},R_{max},\min(a_L,a_{L+1},\cdots,a_R)=a_i\)即可。
设序列\(A\)的前缀和序列为\(B\)，最终答案为\(\max\limits_{1\le i\le n}a_i\cdot (b_R-b_{L-1})\)
LuoguP2422 良好的感觉单调栈优化实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | #include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int stk[N],stop,n,l[N],r[N];
long long a[N],ans,b[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n;i++) b[i]=b[i-1]+a[i];
for(int i=0;i<=n;i++)
{
while(stop&&a[stk[stop]]>=a[i]) stop--;
l[i]=stk[stop];
stk[++stop]=i;
}
stop=0;
for(int i=n+1;i>=1;i--)
{
while(stop&&a[stk[stop]]>=a[i]) stop--;
r[i]=stk[stop];
stk[++stop]=i;
}
for(int i=1;i<=n;i++)
ans=max(ans,a[i]*(b[r[i]-1]-b[l[i]]));
cout<<ans;
}
|
【前缀和】【计数】LuoguP1627 中位数
【题目大意】给出\(1,2\cdots ,n\)的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是 \(b\)。
本题可改为互不相同的\(n\)个数\(a_1,a_2,\cdots,a_n\)，将所有大于\(b\)的\(a_i\)置为1，小于\(b\)的置为-1，等于\(b\)的置为0，并记此数的下标为\(posi\)。考虑新序列\(B\)的前缀和，当\(\displaystyle \sum_{i=L}^{R}b_i=0\)时，区间\([L,R]\)内的中位数为\(b\)，不妨统计\(\displaystyle b_i=k,0\le i\le posi-1\)的个数,存到\(p_k\)中，\(b_i=k,posi\le i\le n\)的总情况数存到\(q_k\)中。答案为\(\displaystyle \sum_{i=0}^{\max(b_i)}p_kq_k\)，算法时间复杂度为\(O(n)\)