基础算法

Falling_Sakura
  2023-07-02 20:06:57 2023-07-02 20:06:57 Created   2025-09-24 10:25:01 2025-09-24 10:25:01 Updated   8.6k Words  46 Mins  

尺取法

其实就是双指针法。

给一道例题找找感觉吧：

HDU2029判断回文串

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
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        string s;
        cin>>s;
        bool ans=true;
        int i=0,j=s.size()-1;
        while(i<j)
        {
            if(s[i]!=s[j])
            {
                ans=false;
                break;
            }
            i++,j--;
        }
        if(ans) cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
    return 0;
}

尺取法可以解决滑动窗口问题，也可以进行数组去重。

指针不够的时候可以加；

二分法

这是一种非常考验边界处理细节的一种算法。

STL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
const int INF=2*int(1e9)+10;
#define LL long long
int cmd(int a,int b){
	return a>b;
}
int main(){
	int num[6]={1,2,4,7,15,34}; 
	sort(num,num+6);                           //按从小到大排序 
	int pos1=lower_bound(num,num+6,7)-num;    //返回数组中第一个大于或等于被查数的值 
	int pos2=upper_bound(num,num+6,7)-num;    //返回数组中第一个大于被查数的值
	cout<<pos1<<" "<<num[pos1]<<endl;
	cout<<pos2<<" "<<num[pos2]<<endl;
	sort(num,num+6,cmd);                      //按从大到小排序
	int pos3=lower_bound(num,num+6,7,greater<int>())-num;  //返回数组中第一个小于或等于被查数的值 
	int pos4=upper_bound(num,num+6,7,greater<int>())-num;  //返回数组中第一个小于被查数的值 
	cout<<pos3<<" "<<num[pos3]<<endl;
	cout<<pos4<<" "<<num[pos4]<<endl;
	return 0;	
}

其实也有一种可以不用 greater<int>() 仿函数的方法：

  • 小于等于：查找最小的大于某数的下标(upper_bound) - 1
  • 小于：查找最小的大于等于某数的下标(lower_bound) - 1

在这里不多赘述，只可意会不可言传。

练习：

P1462通往奥格瑞玛的道路

二分+最短路

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<bits/stdc++.h>
using namespace std;
const int N=50005,M=1000005;
int n,m,b;
int f[N],fir[N],cnt,dist[N],righ[N];
struct edge{
    int next,to,w;
}e[M];
const int MAX=1e9;
void add(int u,int v,int w)
{
    e[++cnt].next=fir[u];
    e[cnt].to=v;
    e[cnt].w=w;
    fir[u]=cnt;
}
struct node{
    int p,d;
    node(){}
    node(int a,int b){p=a;d=b;}
};
bool operator<(const node &a,const node &b)
{
    return a.d>b.d;
}
priority_queue<node>q;
int dijksta(int x)
{
    if(x<f[1]) return 0;
    for(int i=1;i<=n;i++)
        dist[i]=1e9;
    memset(righ,0,sizeof(righ));
    dist[1]=0;
    for(int i=1;i<=n;i++)
    {
        q.push(node(i,dist[i]));
    }
    for(int i=1;i<=n;i++)
    {
        while(righ[q.top().p]) q.pop();
        node now=q.top();
        int p=now.p;
        righ[p]=1;
        q.pop();
        for(int j=fir[p];j;j=e[j].next)
        {  
            int v=e[j].to;
            if(f[v]>x) continue;
            int d=e[j].w+dist[p];
            if(d<dist[v])
            {
                dist[v]=d;
                
                q.push(node(v,d));
            }
        }
    }
    if(dist[n]<=b) return 1;
    return 0;
}
int erfen()
{
    int l=1,r=MAX,mid=(l+r)>>1;
    int c;
    while(l<=r)
    {
        c=dijksta(mid);
        if(c!=0)
        {
            r=mid-1;
            mid=(l+r)>>1;
        }
        else
        {
            l=mid+1;
            mid=(l+r)>>1;
        }
    }
    return l;
}
int main()
{
    scanf("%d%d%d",&n,&m,&b);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&f[i]);
    }
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    if(dijksta(MAX)==0)
    {
        cout<<"AFK"<<endl;
        return 0;
    }
    cout<<erfen()<<endl;
}

P1824进击的奶牛

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 maxn=1e9;
int a[1000010],n,c;
bool P(int d)
{
    int k=0,last=-maxn;
    for(int i=1;i<=n;i++)
    {
        if(a[i]-last>=d)
        {
            last=a[i];
            k++;
        }
    }
    return k>=c;
}
int main()
{
    scanf("%d%d",&n,&c);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
    int l=0,r=1e9,ans,mid;
    while(l<=r)
    {
        if(P(mid=l + r >> 1))
            ans=mid,l=mid+1;
        else
            r=mid-1;
    }
    printf("%d",ans);
}

P1419

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
#include<bits/stdc++.h>
const int N=100005;
using namespace std;
int n,s,t;
int a[100050];
double sum[N];
int q[N];
bool check(double k)
{
    int l=1,r=0;
    for(int i=1;i<=n;i++)//预处理前缀和（-k）
    {
        sum[i]=sum[i-1]+a[i]*1.0-k;
    }
    for(int i=s,p=0;i<=n;i++,p++)//单调队列
    {
        while(r>=l&&sum[q[r]]>sum[p]) r--;
        q[++r]=p;
        while(i-q[l]>t)++l;
        if(sum[i]-sum[q[l]]>=0) return 1;
    }
    return 0;
}
int main()
{
    cin>>n;
    cin>>s>>t;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    double l=-1e4,r=1e4,mid;
    while(r-l>1e-5)//实数二分
    {
        mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    printf("%.3f\n",l);
    return 0;
}

POJ3122

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
#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
double PI=acos(-1.0);
double a[100000];
int n,m;
bool check(double mid)
{
    int sum=0;//能切的PIE总数
    for(int i=1;i<=n;i++)
    {
        sum+=(int)(a[i]/mid);
    }
    if(sum>=m) return true;
    else return false;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        m++;
        double maxp=0;
        for(int i=1;i<=n;i++)
        {
            int r;
            scanf("%d",&r);
            a[i]=PI*r*r;
            if(maxp<a[i]) maxp=a[i];
        }
        double l=0,r=maxp;
        for(int i=1;i<=100;i++)
        {
            double mid=l+(r-l)/2;
            if(check(mid)) l=mid;
            else r=mid;
        }
        printf("%.4f\n",l);
    }
    return 0;
}

P1083

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;
#define int long long
const int N=1e6+117;
int r[N],d[N],s[N],t[N],pre[N],ne[N];
int n,m;
bool check(int mid)
{
    memset(pre,0,sizeof(pre));
    for(int i=1;i<=mid;i++)
    {
        pre[s[i]]+=d[i];
        pre[t[i]+1]-=d[i];
    }
    for(int i=1;i<=n;i++)
    {
        ne[i]=ne[i-1]+pre[i];//利用差分数组求当天要租的教室
        if(ne[i]>r[i]) return false;
    }
    return true;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%lld",&r[i]);
    for(int i=1;i<=m;i++)
        scanf("%lld%lld%lld",&d[i],&s[i],&t[i]);
    if(check(m))
    {
        cout<<"0";
        return 0;
    }
    int l=1,r=m;
    while(l<r)//等于后不用判断
    {
        int mid=(l+r)>>1;
        if(check(mid)) l=mid+1;
        else r=mid;//注意细节
    }
    printf("-1\n%lld",l);
    return 0;
}

P2678

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
#include<bits/stdc++.h>

using namespace std;

int L,N,M;
int ans;
int stone[500005];
int s[100000005]={0};

int f(int x)
{
	
	int size=0,take=0;
	s[0]=0;
	for(int i=1;i<=N;++i)
	{
		if(stone[i]-s[size]<x)
		{
			take++;
			continue;//去掉 
		}
		s[++size]=stone[i];	
	}
	if(L-s[size]<x)
	{
		size--;
		take++;        
	}
	return take<=M;
}
int main ()
{
	scanf("%d%d%d",&L,&N,&M);
	for(int i=1;i<=N;++i)
		scanf("%d",&stone[i]);
	int left=0,right=L+1;
	while(left+1<right)
	{
		int mid=(left+right)/2;
		if(f(mid)==1)
			left=mid;
		else
			right=mid;
	}
	ans=left;//***
	cout<<ans;
	return 0;
}

P1314

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+7;
long long ans=1e12+7;
int n,m,s,maxn=-1,sum;
int w[N],v[N],l[N],r[N];
int ren[N],rev[N],y;//数量前缀和，价值前缀和，y
bool check(int mid)
{
    y=0,sum=0;
    memset(ren,0,sizeof(ren));
    memset(rev,0,sizeof(rev));
    for(int i=1;i<=n;i++)
    {
        if(w[i]>=mid) ren[i]=ren[i-1]+1,rev[i]=rev[i-1]+v[i];
        else ren[i]=ren[i-1],rev[i]=rev[i-1];
    }
    for(int i=1;i<=m;i++)
        y+=(ren[r[i]]-ren[l[i]-1])*(rev[r[i]]-rev[l[i]-1]);
    sum=llabs(y-s);
    if(y>s) return true;
    else return false;
}
signed main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&w[i],&v[i]);
        maxn=max(maxn,w[i]);
    }
    for(int i=1;i<=m;i++)
        scanf("%lld%lld",&l[i],&r[i]);
    int l=0,r=maxn;
    while(l<=r)
    {
        int m=l+(r-l)/2;
        if(check(m)) l=m+1;
        else r=m-1;
        if(sum<ans) ans=sum;
    }
    printf("%lld",ans);
    return 0;
}

三分法

练习

P3382

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 double eps=1e-6;
int n;
double a[20];
double f(double x)
{
    double s=0;
    for(int i=n;i>=0;i--)
        s=s*x+a[i];
    return s;
}
int main()
{
    double l,r;
    scanf("%d%lf%lf",&n,&l,&r);
    for(int i=n;i>=0;i--) scanf("%lf",&a[i]);
    while(r-l>eps)
    {
        double k=(r-l)/3.0;
        double m1=l+k;
        double m2=r-k;
        if(f(m1)>f(m2)) r=m2;
        else l=m1;
    }
    printf("%.5f\n",l);
    return 0;
}

P3745

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+7;
int n,m,t[N],b[N];
ll A,B,C,ans;
ll calc1(int p)//将最晚公布成绩的时间调整到p所产生的不愉快度
{
    ll x=0,y=0;//x代表能提前改完卷子的[总提前天数和]但是由于不愉快度只由最后改完卷子的那一天决定，所以可以将提前改完的天数延后而使推迟改完的天数提前
    //y代表推迟改完卷子的[总推迟天数和]，意味着可以选择用x来填补y，使整体平均，使最晚那一天尽可能靠前
    for(int i=1;i<=m;i++)
    {
        if(b[i]<p) x+=p-b[i];
        else y+=b[i]-p;
    }
    if(A<B)//如果操作A（交换互补）的代价更低，那就能交换即交换，不能交换再新添人手
        return min(x,y)*A+(y-min(x,y))*B;
    else return y*B;//不如直接添人手代价更低
}
ll calc2(int p)//所有同学的在最后一天产生的不愉快总和
{
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        if(t[i]<p) sum+=(p-t[i])*C;//推迟的天数*C
    }
    return sum;
}
int main()
{
    cin>>A>>B>>C>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&t[i]);
    for(int i=1;i<=m;i++) scanf("%d",&b[i]);
    sort(b+1,b+m+1);
    sort(t+1,t+n+1);
    if(C>=1e16)//全部补充老师也比让学生不满意更优，那就调老师让学生满意
    {
        printf("%lld\n",calc1(t[1]));
        return 0;
    }
    ans=1e16;
    int l=1,r=N;
    while(r-l>2)//三分得到最小值所在的天的序号的区间
    {
        int m1=l+(r-l)/3;
        int m2=r-(r-l)/3;
        ll c1=calc1(m1)+calc2(m1);
        ll c2=calc1(m2)+calc2(m2);
        if(c1<=c2) r=m2;
        else l=m1;
    }
    for(int i=l;i<=r;i++)//枚举
    {
        ll x=calc1(i)+calc2(i);
        ans=min(ans,x);
    }
    printf("%lld",ans);
}

P1883

咕咕咕

倍增与ST

超级快的速度：O(log2n)O(log_2n)

原理与二分法相对，不多赘述。

倍增

利用二进制的“特性”，可以将一个数展开得到我们想要的“倍增形式”。

习题

P4155

这道题有道思路相仿的题目可以先做一下：P1803

对于本题：

  1. 断环为链。
  2. 贪心：选择一个区间，下一个区间的左端点必须小于等于这个区间的右端点，其中满足条件的下一个区间的右端点最大为最优。
  3. 倍增：快速查询走2i2^i步所能到达的最优的区间，避免暴力枚举。

定义go[s][i] 表示从第s个区间出发，走2i2^i个最优区间所到达的区间（战士的范围）。

所以首先需要预处理出go[][]。

复杂度：nlog2nnlog_2n

递推式：go[s][i]=go[go[s][i-1]][i-1]

总复杂度：2nlog2n2nlog_2n

code：

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
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=4e5+1;
struct yum{
    int id,l,r;
    bool operator<(const yum x) const{
        return l<x.l;//以左端点最小的为第一个
    }
}w[N*2];
int n2;//断环为链后的链长
int go[N][20],res[N];
void init()
{
    int nxt=1;
    for(int i=1;i<=n2;i++)//贪心求每个区间的下一个区间
    {
        while(nxt<=n2&&w[nxt].l<=w[i].r)
            nxt++;
        go[i][0]=nxt-1;//因为结束循环时多加了1
    }
    for(int i=1;(1<<i)<=n;i++)
        for(int j=1;j<=n2;j++)
            go[j][i]=go[go[j][i-1]][i-1];
}
void get(int x)//从x出发
{
    int len=w[x].l+m,cur=x,ans=1;//len为以x为起点最远能走到的位置，ans为初始的起点战士
    for(int i=log2(N);i>=0;i--)
    {
        int pos=go[cur][i];
        if(pos&&w[pos].r<len)
        {
            ans+=1<<i;//区间数（即战士数）
            cur=pos;//跳到这个区间
        }
        res[w[x].id]=ans+1;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        w[i].id=i;
        scanf("%d%d",&w[i].l,&w[i].r);
        if(w[i].r<w[i].l) w[i].r+=m;//若右端点比左端点小，则说明这段区间包含需要断环的点，那就断，使得这段区间在链上可以正常表示
    }
    sort(w+1,w+1+n);
    n2=n;
    for(int i=1;i<=n;i++)
    {
        n2++;
        w[n2]=w[i];
        w[n2].l=w[i].l+m;//复制一份
        w[n2].r=w[i].r+m;//复制是为了对于8~2-->8~12的这种超出区间的递推的正确性
    }
    init();
    for(int i=1;i<=n;i++)
        get(i);//计算以每名战士为起点的最少人数
    for(int i=1;i<=n;i++)
        printf("%d ",res[i]);
    return 0;
}

ST

ST算法基于倍增原理，适用于求解静态空间的区间最值查询（RMQ）。

RMQ问题：给定长度为n的静态数列，做m次查询，每次给定一段区间[L,R]，求这段区间中的最值。

以最小值为例：

若一个大区间能被两个小区间覆盖，那么大区间的最值等于两个小区间的最值的最值（重合不影响）。

于是得到基本思路：

  1. 将序列拆分为若干个小区间，并预处理小区间的最值。
  2. 对任意区间进行最值查询，只需要找到覆盖它的两个小区间，由两个小区间的最值得出。

定义dp[s][k]=min(dp[s][k-1],dp[s+(1<<(k-1))][k-1])，

代表从ss开始的2k2^k的区间最值为从s开始的2k−12^{k-1}区间和从s+2k−1s+2^{k-1}开始的2k−12^{k-1}区间的最值。

递推关系实际是一个DP的过程，复杂度nlognnlogn。

区间[L,R]的长度为len=R-l+1，两个小区间的长度都为x，使得x≤lenx\le{len}并且2x≥len2x\ge{len}，这样可以保证覆盖。

于是令x=2kx=2^k，k=log2(x)k=log_2(x)，由于k是向下取整的，于是能满足x≤lenx\le{len}并且2x≥len2x\ge{len}的条件。

当然也可以写作k=(int)(log(double(R−L+1))/log(2.0))k=(int)(log(double(R-L+1))/log(2.0))（利用换底公式）。

如果嫌库函数慢的话也可以自己写log函数。

ST:

nlogn−(∑i=1logn2i)nlogn-(\sum^{logn}_{i=1}2^i)

P2251

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
/*Set*/
/*
#include<bits/stdc++.h>
using namespace std;
set<pair<int,int> > S;
int n ,m,a[100005]; 
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++)
	{
		S.insert(make_pair(a[i],i));
		if(i>=m) 
		{
			if(i>m)
				S.erase(make_pair(a[i-m],i-m));
			printf("%d\n",(*S.begin()).first);
		}
 	}
 	return 0;
}
*/
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100005];
int st[100005][23];
int LOG2[100005];
void init()
{
    LOG2[0]=-1;
    for(int i=1;i<=n;i++) LOG2[i]=LOG2[i>>1]+1;
    for(int i=1;i<=n;i++)
        st[i][0]=a[i];
    for(int i=1;(1<<i)<=n;i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
            st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
int qe(int l,int r)
{
    int k=LOG2[r-l+1];
    return min(st[l][k],st[r-(1<<k)+1][k]);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    init();
    for(int i=1;i<=n-m+1;i++)
    {
        printf("%d\n",qe(i,i+m-1));
    }
    return 0;
}

上面注释的做法是用set维护了一个长度为m的序列，利用set自动排序的机制和定值删除的功能实现，pair是为了防止重复。

然后删头去尾，每次输出第一个就是最小的。

st做法没啥好说的。

P1816

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=1e5+7;
int a[N],st[N][23];
int n,m;
void init()
{
    for(int i=1;i<=m;i++)
        st[i][0]=a[i];
    for(int i=1;(1<<i)<=m;i++)
        for(int j=1;j+(1<<i)-1<=m;j++)
            st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);

}
int qe(int l,int r)
{
    int k=(int)log2(r-l+1);
    return min(st[l][k],st[r-(1<<k)+1][k]);
}
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
        scanf("%d",&a[i]);
    init();
    for(int i=1;i<=n;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d ",qe(l,r));
    }
    return 0;
}

板子题，没啥好说的。

关于ST的一些理解：

st[i][j]代表以ii为起点，长度为2j2^j的区间中的最值大小（包含ii这个端点）

st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);

所以预处理的时候这个是直接加上区间长度。

min(st[l][k],st[r-(1<<k)+1][k]);

而访问的时候要减去长度再加一。

前缀和

sum[i]=sum[i-1]+a[i]

sum[i]即元素a在[0,i][0,i]的区间和，这样就可以快速进行区间求和了。

sum[l~r]=sum[r]-sum[l-1]

二阶前缀和

设：

  • AA 是原数组
  • BB 是 AA 的前缀和，即 Bx=∑i=1xAiB_x=\sum_{i=1}^xA_i
  • CC 是 BB 的前缀和，即 Cx=∑i=1xBiC_x=\sum_{i=1}^xB_i

对于 Ai←Ai+1A_i\leftarrow A_i+1 这一操作，Bi∼BxB_i\sim B_{x} 都会加一，即 Cx←Cx+(x−i+1)×1C_{x}\leftarrow C_{x}+(x - i + 1)\times1

练习

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 <iostream>
#include <cstring>
#include <cstdio>
#define lowbit(x) (x & (-x))
using namespace std;
const int N = 1e5 + 7;
typedef long long LL;

int n, m;
LL a[N];
LL B[N], C[N];

void addB(int x, LL v)
{
    for (int i = x; i <= n; i += lowbit(i))
        B[i] += v;
}
void addC(int x, LL v)
{
    for (int i = x; i <= n; i += lowbit(i))
        C[i] += v;
}
LL queryB(int x)
{
    LL res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += B[i];
    return res;
}
LL queryC(int x)
{
    LL res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += C[i];
    return res;
}
void update(int x, int v)
{
    addB(x, v);
    addC(x, 1ll * x * v);
}
LL query(int x)
{
    return queryB(x) * (x + 1) - queryC(x);
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
        update(i, a[i]);
    }
    while (m--)
    {
        string s;
        cin >> s;
        if (s == "Query")
        {
            int x;
            scanf("%d", &x);
            printf("%lld\n", query(x));
        }
        else if (s == "Modify")
        {
            int x, v;
            scanf("%d%d", &x, &v);
            update(x, v - a[x]);
            a[x] = v;
        }
    }
    return 0;
}

三阶前缀和

设：

  • AA 是原数组
  • BB 是 AA 的前缀和，即 Bx=∑i=1xAiB_x=\sum_{i=1}^xA_i
  • CC 是 BB 的前缀和，即 Cx=∑i=1xBiC_x=\sum_{i=1}^xB_i
  • DD 是 CC 的前缀和，即 Dx=∑i=1xCiD_x=\sum_{i=1}^xC_i

对于 Ai←Ai+1A_i\leftarrow A_i+1 这一操作，CjC_{j} 会变成 Cj+(j−i+1)×1C_{j}+(j - i + 1)\times1

即 DxD_x 会变成 Dx+1+2+⋯+(x−i+1)D_x+1+2+\dots+(x-i+1)，即 Dx+(x−i+1)×(x−i+2)2D_x+\frac{(x-i+1)\times(x-i+2)}{2}

Cx=∑i=1xBi=∑i=1x(x−i+1)×AiC_x=\sum_{i=1}^xB_i=\sum_{i=1}^x(x-i+1)\times{A_i}

Dx=∑i=1x(i2−3i)Ai−2xiAi+(x2+3x+2)Ai2D_x=\sum_{i=1}^{x} \dfrac{(i^2-3i)A_i-2xiA_i+(x^2+3x+2)A_i}{2}

也可以这样写：

Dx=∑i=1xi2Ai−(2x+3i)Ai+(x2+3x+2)Ai2D_x=\sum_{i = 1}^{x}\dfrac{i^2A_i-(2x+3i)A_i+(x^2+3x+2)A_i}{2}

维护 i2Ai,iAi,Aii^2A_i,iA_i,Ai 即可。

练习

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <cstdio>
#define lowbit(x) (x & (-x))
using namespace std;
const int N = 2e5 + 7;
const int MOD = 998244353;
typedef long long LL;
const int inv = 499122177;

int n, q;
LL A[N];
LL B[N], C[N], D[N];

void addB(int x, LL v)
{
    for (int i = x; i <= n; i += lowbit(i))
        B[i] = (B[i] + v) % MOD;
}
void addC(int x, LL v)
{
    for (int i = x; i <= n; i += lowbit(i))
        C[i] = (C[i] + v) % MOD;
}
void addD(int x, LL v)
{
    for (int i = x; i <= n; i += lowbit(i))
        D[i] = (D[i] + v) % MOD;
}
void update(LL x, LL v)
{
    addB(x, v);
    addC(x, 1ll * v * x % MOD);
    addD(x, ((1ll * x * x - 3ll * x) % MOD + MOD % MOD) * 1ll * v % MOD);
}
LL queryB(int x)
{
    LL res = 0;
    for (int i = x; i; i -= lowbit(i))
        res = (res + B[i]) % MOD;
    return res;
}
LL queryC(int x)
{
    LL res = 0;
    for (int i = x; i; i -= lowbit(i))
        res = (res + C[i]) % MOD;
    return res;
}
LL queryD(int x)
{
    LL res = 0;
    for (int i = x; i; i -= lowbit(i))
        res = (res + D[i]) % MOD;
    return res;
}
LL query(LL x)
{
    return ((queryD(x) - 1ll * x * 2 % MOD * queryC(x) % MOD + 
           (1ll * x * x + 1ll * 3 * x + 2) % MOD * queryB(x) % MOD) % MOD + MOD) % MOD;
}

signed main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &A[i]);
        update(i, A[i]);
    }
    while (q--)
    {
        int op;
        LL x, y;
        scanf("%d", &op);
        if (op == 1)
        {
            scanf("%lld%lld", &x, &y);
            update(x, (y - A[x] + MOD) % MOD);
            A[x] = y;
        }
        else if (op == 2)
        {
            scanf("%lld", &x);
            printf("%lld\n", (1ll * query(x) * inv) % MOD);
        }
    }
    return 0;
}

与此类似的还有一题~

P8313

题解

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <vector>
#include <algorithm>
#define lowbit(x) (x & (-x))
using namespace std;
const int N = 2e5 + 7;
typedef long long LL;

int n;
LL ans;
int a[N], S[N];
LL C[N << 1], D[N << 1], E[N << 1];
vector<int> num;
vector<int> loc[N];

void add(int x, LL v)
{
	for (int i = x; i <= 2 * n + 1; i += lowbit(i))
	{
		C[i] += v;
		D[i] += 1ll * v * x;
		E[i] += 1ll * v * x * x;
	}
}
LL query(int x)
{
	LL res = 0;
	for (int i = x; i; i -= lowbit(i))
		res += 1ll * C[i] * (1ll * x * x + 3ll * x + 2) - 1ll * D[i] * (2 * x + 3) + E[i];
	res >>= 1;
	return res;
}
int find(int x)
{
	return lower_bound(num.begin(), num.end(), x) - num.begin() + 1;
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		num.push_back(a[i]);
	}
	sort(num.begin(), num.end());
	num.erase(unique(num.begin(), num.end()), num.end());
	int cnt = (int)num.size();
	for (int i = 1; i <= n; i++) // 离散化
		a[i] = find(a[i]);
	for (int i = 1; i <= n; i++)
		loc[a[i]].emplace_back(i); // 记录每种菜品出现的位置
	
	// for (int i = 1; i <= cnt; i++)
	// {
	// 	for (int j = 1; j <= n; j++)
	// 		S[j] = S[j - 1] + (a[j] == i);
	// 	add(n + 1, 1); // l = 0 时，B = 0 出现了 1 次
	// 	for (int j = 1; j <= n; j++)
	// 	{
	// 		ans += query(S[j] * 2 - j + n + 1 - 1);
	// 		add(S[j] * 2 - j + n + 1, 1);
	// 	}
	// 	add(n + 1, -1);
	// 	for (int j = 1; j <= n; j++)
	// 		add(S[j] * 2 - j + n + 1, -1);
	// }

	for (int i = 1; i <= cnt; i++)
	{
		loc[i].push_back(n + 1); // 处理最后一段区间
		int last = 0;
		for (int j = 0; j < (int)loc[i].size(); j++)
		{
			int s = 2 * j - last + n + 1; // 等差序列的开头
			int t = 2 * j - loc[i][j] + 1 + n + 1; // 等差序列的末尾
			ans += query(s - 1) - (t >= 2 ? query(t - 2) : 0); // 查询三阶前缀和
			add(t, 1);
			add(s + 1, -1); // 公差为一的等差序列下标连续，[s,t] 区间加
			last = loc[i][j];
		}
		last = 0;
		for (int j = 0; j < (int)loc[i].size(); j++) // 重置树状数组
		{
			int s = 2 * j - last + n + 1;
			int t = 2 * j - loc[i][j] + 1 + n + 1;
			add(t, -1);
			add(s + 1, 1);
			last = loc[i][j];
		}
	}
	printf("%lld\n", ans);
	return 0;
}

差分

差分是前缀和的逆运算，它将区间修改转化为端点修改。

一维差分

定义差分数组D[]，D[i]=a[i]-a[i-1]。

查询：

a[k]=∑i=1kD[i]a[k]=\sum^{k}_{i=1}D[i]

也就是对差分数组求前缀和。

区间修改：

将区间[l,r][l,r]的每个元素都加dd，

只需要：

D[l]+=d,D[r+1]-=d

这样就可以保证：

  1. 1≤x<l1\le{x}<l，a[x]a[x]不变。
  2. l≤x≤rl\le{x}\le{r}，a[x]a[x]增加dd。
  3. r<x≤nr<x\le{n}，a[x]a[x]不变。

nn个数mm次区间修改+一次查询复杂度：O(mn)→O(m+n)O(mn)\to{O(m+n)}

差分对于单点查询不是很高效，这时候就需要线段树或者树状数组了。

习题：

HDU1556

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
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int D[N];
int n;
int main()
{
    while(~scanf("%d",&n))
    {
        memset(D,0,sizeof(D));
        for(int i=1;i<=n;i++)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            D[l]++,D[r+1]--;
        }
        for(int i=1;i<=n;i++)
        {
            D[i]=D[i-1]+D[i];
            if(i!=n) printf("%d ",D[i]);
            else printf("%d\n",D[i]);
        }
    }
    return 0;
}

二维差分

点扩展为面

差分数组的前缀和：

a[i][j]a[i][j]代表点(1,1)(1,1)到点(i,j)(i,j)的矩形的面积（所有元素之和）；

差分：

D[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]

a就是大矩形，D就是大矩形中的小矩形。

区间修改

将点(x1,y1),(x2,y2)(x_1,y_1),(x_2,y_2)围成的一段区间中每个元素都加上dd，需要：

  • D[x1][y1]+=d
  • D[x1][y2+1]-=d
  • D[x2+1][y1]-=d
  • D[x2+1][y2+1]+=d//被减了两次的地方需要加回来一次

处理的时候可以直接把DD数组当成aa来更新，以此节省空间，因为是从前往后更新，后面的值需要前面的值，前面的值不需要后面的值，所以互不影响。

习题：

P3397

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;
int n,m;
int D[5005][5005];
int main()
{
    scanf("%d%d",&n,&m);
    while(m--)
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        D[x1][y1]+=1;
        D[x1][y2+1]-=1;
        D[x2+1][y1]-=1;
        D[x2+1][y2+1]+=1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            D[i][j]+=D[i-1][j]+D[i][j-1]-D[i-1][j-1];
            printf("%d ",D[i][j]);
        }
        puts("");
    }
    return 0;
}

其中，计算前缀和可以这样替换：

1
2
3
4
5
6
for(int i=1;i<=n;i++)
    for(int j=1;j<n;j++)
        D[i][j+1]+=D[i][j];
for(int i=1;i<n;i++)
    for(int j=1;j<=n;j++)
        D[i+1][j]+=D[i][j];

即横向纵向分别处理前缀和。

也可以这样写：

1
2
3
4
5
6
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        D[i][j]+=D[i][j-1];
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        D[i][j]+=D[i-1][j];

二维前缀和的应用：

P2280

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
#include<bits/stdc++.h>
using namespace std;
const int N=5001;//坐标范围：1~5001
int n,m,ans=-1;
int sum[5007][5007];//防越界
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x,y,v;
        scanf("%d%d%d",&x,&y,&v);
        sum[++x][++y]+=v;//将坐标范围由0~5000改为1~5001
    }
    for(int i=1;i<=N;i++)//二位前缀和，坐标范围内都需要处理
        for(int j=1;j<N;j++)
            sum[i][j+1]+=sum[i][j];
    for(int j=1;j<=N;j++)
        for(int i=1;i<N;i++)
            sum[i+1][j]+=sum[i][j];
    for(int i=m;i<=N;i++)//对于坐标范围内地毯式搜索
        for(int j=m;j<=N;j++)
        {
            int p=sum[i][j]-sum[i-m][j]-sum[i][j-m]+sum[i-m][j-m];
            ans=max(ans,p);
        }
    printf("%d",ans);
    return 0;
}

二阶差分

这是一个链接

离散化

很多时候我们并不关心元素的绝对大小，我们关心它们的相对大小，那么就可以对它们进行离散化处理。

离散化的具体步骤：

  1. 排序
  2. 编号
  3. 归位

代码：

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=500;
struct data{
    int val,id;
}olda[N];
int newa[N];
bool cmp(data x,data y)
{
    return x.val<y.val;
}
int n;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&olda[i].val);
        olda[i].id=i;
    }
    sort(olda+1,olda+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        newa[olda[i].id]=i;
        if(olda[i].val==olda[i-1].val)
            newa[olda[i].id]=newa[olda[i-1].id];
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d ",newa[i]);
    }
    return 0;
}

也可以不预处理出来，通过库函数排序、判重，用的时候二分查找即可。

这是保序的写法，也就是映射后元素之间大小关系不变。

若是不需要保序，那么 map 或者哈希表就都可以做，好写很多。

排序

常见排序算法：

  • 选择
  • 插入
  • 冒泡
  • 归并
  • 快排
  • 堆排
  • 计数
  • 基数
  • 桶排
  • sort()

桶排

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
75
76
77
78
79
80
#include<bits/stdc++.h>
using namespace std;

int* arr_sort(int *arr,int n) // 数组地址，长度
{
    int maxValue = arr[0];
    for(int i = 1; i < n; ++i)
    {
        if(arr[i] > maxValue)
        {
            maxValue = arr[i];
        }
    }
    const int bucketCnt = 10;
    vector<int> buckets[bucketCnt];
    int bucketSize = 1;
    while(maxValue)
    {
        maxValue /= 10;
        bucketSize *= 10;
    }
    bucketSize /= 10;
    for(int i = 0; i < n; ++i)
    {
        int idx = arr[i] / bucketSize;
        buckets[idx].push_back(arr[i]);
        for(int j = int(buckets[idx].size())-1; j > 0; --j)
        {
            if(buckets[idx][j] < buckets[idx][j-1])
                swap(buckets[idx][j], buckets[idx][j-1]);
        }
    }
    for(int i = 0, k = 0; i < bucketCnt; ++i)
        for(int j = 0; j < int(buckets[i].size()); ++j)
            arr[k++] = buckets[i][j];
    return arr;
}
int* ArrSort(int *arr, int n)
{
    int maxv;
    for(int i = 1; i <= n; ++i)
        maxv = max(maxv,arr[i]);
    const int bcnt = 10;
    vector<int> buc[bcnt];
    int bsize = 1;
    while(maxv)
    {
        maxv /= 10;
        bsize *= 10;
    }
    bsize /= 10; // 按照最大值的值域分为十份
    for(int i = 1; i <= n; ++i)
    {
        int idx = arr[i] / bsize; // 先把元素丢到桶里
        buc[idx].emplace_back(arr[i]);
        for(int j = int(buc[idx].size())-1; j > 0; --j) // 从新加入的位置开始遍历
            if(buc[idx][j] < buc[idx][j-1]) swap(buc[idx][j], buc[idx][j-1]);
    }
    for(int i = 0, k = 1; i < bcnt; ++i)
        for(int j = 0; j < int(buc[i].size()); ++j)
            arr[k++] = buc[i][j];
    return arr;
}

int main()
{
    int n;
    int* a;
    scanf("%d",&n);
    a = (int*)malloc(sizeof(int)*n+4);
    for(int i = 1; i <= n; ++i)
        scanf("%d",&a[i]);
    a = ArrSort(a,n);
    for(int i = 1; i <= n; ++i)
        printf("%d ", a[i]);
    free(a);
    return 0;
}
// 5
// 10 2093 293 281 3940

先分桶，这里按照十个来分。

然后把元素丢到它对应的桶内，然后对桶内进行排序，这里使用插入排序。

然后按顺序合并即可。

排列

STL

next_permutation()函数，该函数内前两个参数为左开右闭的一个排列区间的指针（如s.begin(),s.end()），返回值为bool类型，表示有无下一个排列，排列后的结果会返回原序列中并覆盖。

分块

分块是一种高效的思想，常用来处理区间问题。

1
2
3
4
5
6
int sq = sqrt(n);
for (int i = 1; i <= sq; ++i)
{
    st[i] = n / sq * (i - 1) + 1; // st[i]表示i号块的第一个元素的下标
    ed[i] = n / sq * i; // ed[i]表示i号块的最后一个元素的下标
}

sqrt 代表分的块的个数，每个块的长度不一定为 sqrt，例如n=12n=12。

但是序列长度不一定是完全平方数，所以我们把最后一小块归入到原来的最后一块中块。

1
ed[sq]=n;

然后就是为每个元素确定它所属于的块：

1
2
3
for (int i = 1; i <= sq; ++i)
    for (int j = st[i]; j <= ed[i]; ++j)
        bel[j] = i; // 表示j号元素归属于i块

处理每个块的大小：

1
2
for (int i = 1; i <= sq; ++i)
    size[i] = ed[i] - st[i] + 1;

例题

线段树能做的，为什么我分块不行？

P3372 【模板】线段树 1

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e5+8;
int a[N];
struct block
{
    int st,ed,sum,add;
}e[N>>1];
int n,m,bel[N];
void init()
{
    int sq=sqrt(n);
    for(int i=1;i<=sq;i++)
    {
        e[i].st=n/sq*(i-1)+1;
        e[i].ed=n/sq*i;
    }
    e[sq].ed=n;
    for(int i=1;i<=sq;i++)
    {
        for(int j=e[i].st;j<=e[i].ed;j++)
            bel[j]=i,e[i].sum+=a[j];
    }
}
void modify(int l,int r,int x)
{
    if(bel[l]==bel[r])
    {
        for(int i=l;i<=r;i++)
        {
            a[i]+=x;
            e[bel[l]].sum+=x;
        }
        return;
    }
    for(int i=l;i<=e[bel[l]].ed;i++)
    {
        a[i]+=x;
        e[bel[l]].sum+=x;
    }
    for(int i=e[bel[r]].st;i<=r;i++)
    {
        a[i]+=x;
        e[bel[r]].sum+=x;
    }
    for(int i=bel[l]+1;i<bel[r];i++)
        e[i].add+=x;
}
int query(int l,int r)
{
    int s=0;
    if(bel[l]==bel[r])
    {
        for(int i=l;i<=r;i++)
            s+=a[i]+e[bel[l]].add;
        return s;
    }
    for(int i=l;i<=e[bel[l]].ed;i++)
        s+=a[i]+e[bel[i]].add;
    for(int i=e[bel[r]].st;i<=r;i++)
        s+=a[i]+e[bel[r]].add;
    for(int i=bel[l]+1;i<bel[r];i++)
        s+=e[i].sum+e[i].add*(e[i].ed-e[i].st+1);
    return s;
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    init();
    while(m--)
    {
        int op,x,y,k;
        scanf("%lld%lld%lld",&op,&x,&y);
        if(op==1)
        {
            scanf("%lld",&k);
            modify(x,y,k);
        }
        else
        {
            printf("%lld\n",query(x,y));
        }
    }
    return 0;
}

嗯，比线段树好看不少，代码也简洁，思维难度也不高。

不过它们都有区间标记这个小技巧。

分块方式

第一种：

1
2
3
4
5
6
int sq = sqrt(n);
for (int i = 1; i <= sq; ++i)
{
    st[i] = n / sq * (i - 1) + 1; // st[i]表示i号块的第一个元素的下标
    ed[i] = n / sq * i; // ed[i]表示i号块的最后一个元素的下标
}

这里的 sq 为块的数量，根据块的数量来均摊块的长度，特别地，最后一个不完整的块将被归并到原来的最后的块中。

小优化：由于是 n\sqrt{n} 个块，因此可以开 n2\frac{n}{2} 空间就足够。

第二种：

1
2
3
4
5
for (int i = 1; i <= n; i++) {
    cin >> a[i];
    id[i] = (i - 1) / len + 1;
    s[id[i]] += a[i];
  }

这个的 len 为块的长度，根据长度来决定块的个数。

  • Title: 基础算法
  • Author: Falling_Sakura
  • Created at : 2023-07-02 20:06:57
  • Updated at : 2025-09-24 10:25:01
  • Link: https://vercel.fallingsakura.top/af411f31.html
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
基础算法
  1. 1. 尺取法
  2. 2. 二分法
    1. 2.1. 练习：
  3. 3. 三分法
    1. 3.1. 练习
  4. 4. 倍增与ST
    1. 4.1. 倍增
      1. 4.1.1. 习题
    2. 4.2. ST
  5. 5. 前缀和
    1. 5.1. 二阶前缀和
    2. 5.2. 三阶前缀和
  6. 6. 差分
    1. 6.1. 一维差分
      1. 6.1.1. 习题：
    2. 6.2. 二维差分
      1. 6.2.1. 习题：
    3. 6.3. 二阶差分
  7. 7. 离散化
  8. 8. 排序
    1. 8.1. 桶排
  9. 9. 排列
    1. 9.1. STL
  10. 10. 分块
    1. 10.1. 例题
    2. 10.2. 分块方式