基础算法

快速排序

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 <iostream>

using namespace std;
const int N=100002;
int n;
int q[N];
void quick_sort(int q[],int l,int r)
{
    if(l>=r)return;
    int x=q[l];
    int i=l-1;
    int j=r+1;
    while(i<j)
    {
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j)swap(q[i],q[j]);
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&q[i]);
    }
    quick_sort(q,0,n-1);
    for(int i=0;i<n;i++)
    {
        printf("%d",q[i]);
    }
    return 0;
}

找两个指针，拟定一个数x，这两个指针从头开始，如果指针所指的数大于x，则将他放在x右边，如果指针所指的数小于x，则将它放在x左边并分别递归两边（继续进行上述操作）。

快速选择

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<iostream>
using namespace std;
const int N=100010;
int n,k;
int q[N];
int quick_sort(int l,int r,int k)
{
    if(l==r)
    {
        return q[l];
    }
    int x=q[l],i=l-1,j=r+1;
    while(i<j)
    {
        while(q[++i]<x);
        while(q[--j]>x);
        if(i<j)
        {
            swap(q[i],q[j]);
        }
    }
    int sl=j-l+1;
    if(k<=sl)
    {
        return quick_sort(l,j,k);
    }
    else
    {
        return quick_sort(j+1,r,k-sl);
    }
}
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>q[i];
    }
    cout<<quick_sort(0,n-1,k)<<endl;

    return 0;
}

在快速排序的基础上，仅仅进行一次分组，即将数组分成2部分，若所求的数的位次小于分界的那个数，就仅仅队左边那个数进行递归，若是所求的那个数大于分界的那个数，则仅仅对右边那个数组进行递归，求出所求数减去中间数的差，这个差代表所求的右边那个数组的第几个数。

归并排序

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
#include<iostream>
using namespace std;
const int N=100010;
int n;
int a[N];
int b[N];
void mergesort(int a[],int l,int r)
{
	if(l>=r)
	{
		return ;
	}
	int mid=l+r>>1;
	mergesort(a,l,mid);
	mergesort(a,mid+1,r);
	int k=0;
	int i=l;
	int j=mid+1;

	while(i<=mid&&j<=r)
	{
		if(a[i]<=a[j])
		{
			b[k++]=a[i++];
		}
		else
		{
			b[k++]=a[j++];
		}
	}
	while(i<=mid)
	{
		b[k++]=a[i++];
	}
	while(j<=r)
	{
		b[k++]=a[j++];
	}
	for(i=l,j=0;i<=r;i++,j++)
	{
		a[i]=b[j];
	}
//	for(i=0;i<n;i++)
//	{
//		a[i]=b[i];
//	}
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	mergesort(a,0,n-1);
	for(int i=0;i<n;i++)
	{
		if(i!=0)
		{
			printf(" ");
		}
		printf("%d",a[i]);
	}
	printf("\n");
	return 0;
}

中间有一点，就是为什么在返回值的时候不能用
// for(i=0;i<n;i++)
// {
// a[i]=b[i];
// }
而要用
for(i=l,j=0;i<=r;i++,j++)
{
a[i]=b[j];
}

  1. 局部合并：在归并排序中，我们首先将数组分成两半，然后对每一半递归地进行排序。当两半都排序完成后，我们需要将它们合并成一个有序的数组。合并操作是局部的，只涉及到数组的某一部分，而不是整个数组。l 和 r 就是用来定义这个需要合并的局部范围的。

  2. 避免数据覆盖：在合并的过程中，如果使用 for(i=0;i<n;i++) 这样的循环，那么在合并第一个元素时，就会覆盖掉 b 数组中剩余的元素，因为 j 没有相应地增加。这样会导致只有数组 a 的前 n 个元素被复制到了 b，而后面的元素则丢失了。

  3. 正确的索引映射：使用 for(i=l,j=0;i<=r;i++,j++) 这样的循环可以确保 b 数组中的元素被正确地复制回 a 数组的相应位置。i 从 l 开始，j 从 0 开始，这样保证了 b 数组中的元素按照它们在 b 中的顺序被复制到 a 数组的 l 到 r 范围内。

  4. 避免不必要的操作：使用 for(i=0;i<n;i++) 这样的循环会尝试复制整个 b 数组，而实际上我们只需要复制 b 数组中的一部分。这样做不仅效率低下，而且会导致数据错误。

整体的思路就是先将数组分成两组，然后分别对两个数组进行递归排序，得到两个已经排好序的数组，然后定义两个指针，分别位于两组的第一个数，然后进行比大小，重新定义一个新数组来存储排好序的数，将小的数放入这个数组，然后移动该指针，并继续进行比大小，以此类推，直至一边的数全部已经放入新数组，则另外一个数组剩下的数均为已经排好序的且大于第一个数组的所有数，所以直接将这里面的数全部放入该数组，最后再将这个数组的数返回之前的那个数组。

高精度

高精度加法

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<iostream>
#include<vector>
using namespace std;
const int N=1000010;
vector<int> add(vector<int> &A,vector<int> &B)
{
	vector<int> c;
	int t=0;
	for(int i=0;i<A.size()||i<B.size();i++)
	{
		if(i<A.size())
		{
			t+=A[i];
		}
		if(i<B.size())
		{
			t+=B[i];
		}
		c.push_back(t%10);
		t/=10;
	}
	if(t)c.push_back(1);
	return c;
}
int main()

{
	string a, b;
	vector<int> A,B;
	cin>>a>>b;
	for(int i=a.size()-1;i>=0;i--)
	{
		A.push_back(a[i]-'0'); 
	}
	for(int i=b.size()-1;i>=0;i--)
	{
		B.push_back(b[i]-'0'); 
	}
	auto c=add(A,B);
	for(int i=c.size()-1;i>=0;i--)
	{
		printf("%d",c[i]);
	}
	return 0;	
}

整体思路就是把两个数，定义为两个数组，从低位开始，因此需要倒序，让每一位相加，如果加起来大于10，再进一，依次类推，直至加完每一位数！！
这里唯一需要注意的一点就是vector动态数组的正确使用与相关知识，具体关于vector动态数组的内容我单另写了一点。这里就不过多细说。
这里补充一点，用vector动态数组相关的东西不一定要用头文件

1
#include<bits/stdc++.h>

也可以像这道题一样用

1
2
3
#include<iostream>
#include<vector>
using namespace std;

高精度减法

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
#include<iostream>
#include<vector>
using namespace std;
const int N=100010;
bool cmp(vector<int> &A,vector<int> &B)
{
	if(A.size()!=B.size())
	{
		return A.size()>B.size();
	}
	for(int i=A.size()-1;i>=0;i--)
	{
		if(A[i]!=B[i])
		{
			return A[i]>B[i];
		}
	}
	return true;
}
vector<int> sub(vector<int> &A,vector<int> &B)
{
	vector<int> c;
	int t=0;
	for(int i=0;i<A.size();i++)
	{
		t=A[i]-t;
		if(i<B.size())
		{
			t=t-B[i];
		}
		c.push_back((t+10)%10);
		if(t<0)t=1;
		else t=0; 
	}
	while(c.size()>1&&c.back() ==0)
	{
		c.pop_back() ;
	}
	return c;
}
int main()
{
	string a,b;
	vector<int> A,B;
	cin>>a>>b;
	for(int i=a.size()-1;i>=0;i--)
	{
		A.push_back(a[i]-'0'); 
	}
	for(int i=b.size()-1;i>=0;i--)
	{
		B.push_back(b[i]-'0'); 
	}
	if(cmp(A,B))
	{
		auto c=sub(A,B);
		for(int i=c.size()-1;i>=0;i--)
		{
			printf("%d",c[i]);
		}
	}
	else
	{
		printf("-");
			auto c=sub(B,A);
		for(int i=c.size()-1;i>=0;i--)
		{
			printf("%d",c[i]);
		}
	}
	return 0;
}

与高精度加法相比较，高精度减法多了更多的判断条件，整体思路如下：
为了避免刚复杂的讨论，在导入函数的时候我们就可以先进行一波判断，判断a与b的大小，如果a大于b就直接导入函数，如果a小于b就导入-(b,a)。这样就避免了函数内出现小的数减大的数，永远都是大的数减小的数。

判断条件就是如果位数一样就从最高位开始比较，依次往矮的的位数比较。

然后进行减法的函数内部就是需要考虑借位，如果是最后一位则不考虑，就是说，超出b的长度的位数就不用考虑借位。因此有一个判断条件，

最后因为我们写的是字符串，所以就会有以一个问题，如果最高位出现0，则会输出0。这是我们不愿看到的，因此要除去最高位的0。这里用了一个新的东西。

  • back() == 0 检查容器c`的最后一个元素是否等于0。
  • pop_back() 是一个成员函数，用于移除容器c`的最后一个元素。
    这样就能达成目的。

高精度乘法

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<iostream>
#include<vector>
using namespace std;
vector<int> mul(vector<int> &A,int b)
{
	vector<int> c;
	int t=0;
	for(int i=0;i<A.size()||t;i++)
	{
		if(i<A.size())
		{
			t+=A[i]*b;
		}
		c.push_back(t%10);
		t/=10;
	}
	return c;
}
int main()
{
	string a;
	int b;
	vector<int> A;
	cin>>a>>b;
	for(int i=a.size()-1;i>=0;i--)
	{
		A.push_back(a[i]-'0'); 
	}
	auto c=mul(A,b);
	for(int i=c.size()-1;i>=0;i--)
	{
		printf("%d",c[i]);
	}
	return 0;
}

好奇怪，高精度乘法居然是一个高精度的数去乘以一个低精度的数，
具体的思路就是高精度数组没位数去乘以那个低精度数b。
如果大于10的话就存在进位，本位就是%10，进位的数就是/10。
注意这里的判断条件有点意思，还有一个||t，意思是进位没有进行完毕就是说如果t！=0，就会继续进位。

高精度乘以高精度

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<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
char a1[10001],b1[10001];
int a[10001],b[10001],i,x,len,j,c[10001];
int main ()
{
    cin>>a1>>b1;
    int lena=strlen(a1);
    int lenb=strlen(b1);
    for(i=1;i<=lena;i++)a[i]=a1[lena-i]-'0';
    for(i=1;i<=lenb;i++)b[i]=b1[lenb-i]-'0';
    for(i=1;i<=lenb;i++)
    for(j=1;j<=lena;j++)
    c[i+j-1]+=a[j]*b[i];
    for(i=1;i<lena+lenb;i++)
    if(c[i]>9)
    {
        c[i+1]+=c[i]/10;
        c[i]%=10;
    }
    len=lena+lenb;
    while(c[len]==0&&len>1)len--;
    for(i=len;i>=1;i--)cout<<c[i];
    return 0;
}

高精度除法

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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> div(vector<int> &A,int b,int &r)
{
	vector<int> c;
	r=0;
	for(int i=0;i<A.size() ;i++)
	{
		r=r*10+A[i];
		c.push_back(r/b);
		r=r%b; 
	}
	reverse(c.begin(),c.end());
	while(c.size()>1&&c.back()==0)
	c.pop_back() ;
	return c;
}
int main()
{
	string a;
	int b;
	cin>>a>>b;
	vector<int> A;
	int r;
	for(int i=0;i<a.size();i++)
	{
		A.push_back(a[i]-'0'); 
	}
	auto c=div(A,b,r);
	for(int i=c.size()-1;i>=0;i--)
	{
		printf("%d",c[i]);
	}
	printf("\n%d\n",r);
}

这道题需要正向读取，因为除法是从高位往低位去除的，思路就是：

每位数加上余数，然后除以除数，得出每一位的商，再得出这一位的余数，然后再进行下一步循环直至最后得出全部数。

最后别忘了去除前几位的0，这里要用一个新东西：

1
2
#include<algorithm>
reverse(c.begin(),c,end());

这个东西是将一个数组内的东西全部倒过来，因为正向读取的原因，因此我们得到的数是正序的，因此要除去末尾的0，必须要用这一步。

二分

整数二分

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
#include<iostream>
using namespace std;
const int N=100010;
int n,m;
int a[N];
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	while(m>0)
	{
		int x;
		cin>>x;
		int l=0;
		int r=n-1;
		while(l<r)
		{
			int mid=l+r>>1;
			if(a[mid]>=x)
			{
				r=mid;
			}
			else 
			{
				l=mid+1;
			}
		}
		if(a[l]!=x)
		{
			cout<<"-1 -1"<<endl;
		}
		else 
		{
			cout<<l<<' ';
			int l=0;
			int r=n-1;
			while(l<r)
			{
				int mid=l+r+1>>1;
				if(a[mid]<=x)
				{
					l=mid;
				}
				else 
				{
					r=mid-1;
				}
			}
			cout<<l<<endl;
		}
		m--;
	}
	return 0;
}

总结一句就是套模板，一共有两个模板

1
2
3
4
5
6
7
8
9
10
11
12
while(l<r)
		{
			int mid=l+r>>1;
			if(a[mid]>=x)
			{
				r=mid;
			}
			else 
			{
				l=mid+1;
			}
		}

这是模板1；

1
2
3
4
5
6
7
8
9
10
11
12
while(l<r)
			{
				int mid=l+r+1>>1;
				if(a[mid]<=x)
				{
					l=mid;
				}
				else 
				{
					r=mid-1;
				}
			}

这是模板2；
模板1是用来找左边界的，原理大概是：
模板2是用来找右边界的，原理：
特别注意，当临界为l=mid，r=mid-1时，求mid的时候要多加一个1。这个很重要！！

2二分答案

这个二分很好理解，但是这个二分答案有点过于逆天。
说实话我目前还没咋搞懂这个例题
进击的奶牛！！！！

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010;
int n, c, a[N];
int b;
bool check(int x)
{
    int num = 0;
    int l = a[1];
    for (int i = 2; i <= n;i++)
    {
        if(a[i]-l<x)
            num++;
        else
            l = a[i];
        if(num>b)
            return false;
    }
    return true;
}
int main()
{
    cin >> n >> c;
    for (int i = 1; i <= n;i++)
    {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    b = n - c;
    int l = a[1];
    int r = a[n] - a[1];
    while(l+1<r)
    {
        int mid = l + r >> 1;
        if(check(mid))
            l = mid;
        else
            r = mid;
    }
    if(check(r))
        printf("%d", r);
    else
        printf("%d", l);
    return 0;
}

附题：

3二分的一些情况

一、一些最大值的最小值，比如说什么要求一堆数中的最小长度的最大值，此时一般可以使用二分，二分方法为，优先保证数组单调，在此基础上去寻找满足左边全满足，右边全部不满足的条件。
例如：

一、这道题和奶牛那道题是一样的，也就是说，我们要满足求出最大值，那么我们就不允许出现比他小的值，也就是说我们现在二分的目的是看看我们找的mid是大了还是小了，如果大了，也就是说此时两个牛之间的距离无法使得空闲的牛棚足够，或者石头搬多了。那么就要让右区间变成mid。如果小了，也就是说，我们石头没搬够，或者剩的牛棚太多了，此时肯定不满足最大，所以要让左区间为mid。这是第一类二分的题。在check函数里面我们要去判断距离的大小来看是否需要跳过该栅栏或者搬掉该石头。

二、那么像借教室这类题，他涉及的知识范围又太广泛了，包括前缀和和差分。但是这类题的二分不会太难，因为本质是考综合思维，只需要想到，在时间复杂度不够的情况下，使用二分。二分的方法为，先找一个mid，看看在到达mid这个人之前是否剩余空教室

浮点数二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
using namespace std;
int main()
{
	double x;
	cin>>x;
	double l=-10000;
	double r=10000;
	while(r-l>0.00000001)
	{
		double mid=(l+r)/2;
		if(mid*mid*mid>=x) r=mid;
		else l=mid;
	}
	printf("%lf\n",l);
	return 0;
}

具体思路和整数的二分差不多，比整数的二分要更简单一点，不要考虑复杂的边界问题：

这里是保留了6位小数，我们用1e-8来表示。

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
#include<iostream>
using namespace std;
double a,b,c,d;
double f(double x)
{
	return a*x*x*x+b*x*x+c*x+d;
}
int main()
{
	scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
	int i;
	int cnt=0;
	double l,r,mid,x1,x2;
	for(i=-100;i<100;i++)
	{
		l=i;
		r=i+1;
		x1=f(l);
		x2=f(r);
		if(!x1)
		{
			printf("%.2lf ",l);
			cnt++;
		}
		
		if(x1*x2<0)
		{
		
			while(r-l>=0.001)
			{
				mid=(l+r)/2;
				if(f(r)*f(mid)<=0)
				{
					l=mid;
				}
				else 
				{
					r=mid;
				}
			}
//			if(cnt!=0)
//			printf(" ");
			printf("%.2lf ",r);
			cnt++;
		}
		if(cnt==3)
		break;
	}
	
	return 0;
	
}

这是一道二分答案的题，目的是解一元三次方程。

前缀和

一维前缀和

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<iostream>
using namespace std;
const int N=100010;
int a[N],s[N];
int m,n;
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++)
	{
		s[i]=s[i-1]+a[i];
	}
	while(m>0)
	{
		int l,r;
		scanf("%d %d",&l,&r);
		printf("%d",s[r]-s[l-1]);
		m--;
	}
	
	return 0;
}

前缀和就是从1到n的和，这个应该看得懂就是用来求第l到r的和，用r的前缀和减去l-1的前缀和就可以得到从l到r的和。

二维前缀和

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
#include<iostream>
using namespace std;
const int N=1010;
int a[N][N],s[N][N];
int n,m,q;
int main()
{
	scanf("%d %d %d",&n,&m,&q);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
		}
	}
	while(q>0)
	{
		int x1,x2,y1,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		printf("%d\n",s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);
		q--;
	}
	
	return 0;
}

我要当背党，背公式就完事了，
1

1
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];

2

1
s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]

还有速记口诀：1：先分别减1，再一起减1，再加那个点。
2：1-1，2不-1，最后加上两个1-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
#include<iostream>
using namespace std;
const int N=100010;
int n,m;
int a[N],b[N];
void insert(int l,int r,int c)
{
	b[l]+=c;
	b[r+1]-=c;
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++)
	{
		insert(i,i,a[i]);
	}
	while(m>0)
	{
		int l,r,c;
		scanf("%d %d %d",&l,&r,&c);
		insert(l,r,c);
		m--;
	}
	for(int i=1;i<=n;i++)
	{
		a[i]=a[i-1]+b[i];
	}
	for(int i=1;i<=n;i++)
	{
		printf("%d ",a[i]);
	}
	return 0;
}

差分数组就是前缀和的逆数组，相当于，a[i]是b[i]的前缀和，那么b[i]就是a[i]的差分数组。
在这道题中我们存在一个较难的数学判断，那就是插入思想，
差分主要是用来求就是比如说让范围是l，r中间的数全部加上c，，其余数保持不变。
具体思路是让b[l]加上c，b[r+1]减去c。
这里还有一个更牛逼的思路，就是在确定b数组的值的时候，我们相当于把a中的每一个值都当作0，然后每一个b都相当于是在 i 到 i 这个区间里加上了a[i]，这样就能直接求出b的值。真是太智慧了。

最后在求改变后的a的值的时候就直接用前缀和的公式，就完成了！！！

二维差分

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
#include<iostream>
using namespace std;
const int N=1010;
int m,n,q;
int a[N][N],b[N][N];
void insert(int x1,int y1,int x2,int y2,int c)
{
	b[x1][y1]+=c;
	b[x2+1][y1]-=c;
	b[x1][y2+1]-=c;
	b[x2+1][y2+1]+=c;
}
int main()
{
	scanf("%d %d %d",&n,&m,&q);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			insert(i,j,i,j,a[i][j]);
		}
	}
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=1;j<=m;j++)
//		{
//			printf("%d ",b[i][j]);
//		}
//		printf("\n");
//	}
	while(q>0)
	{
		int x1,y1,x2,y2,c;
		cin>>x1>>y1>>x2>>y2>>c;
		insert(x1,y1,x2,y2,c); 
		q--;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			printf("%d ",a[i][j]);
		}
		printf("\n");
	}
	
	return 0;
}

在一维差分的基础上进行二维差分，其实就是把差分于子矩阵之和结合了一下，注意求二维前缀和的公式就好了。

1
a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];

也是一样的用插入的方法求差分二维数组。其他的没什么了，跟一维差分一样的。

递归逆序数组

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
#include<iostream>
using namespace std;
const int N=100010;
int n;
int a[N];
int b[N];
int mergesort(int l,int r)
{
	if(l>=r)
	{
		return 0;
	}
	int mid=(l+r)>>1;
	int i=l;
	int k=0;
	int j=mid+1;
	long long ret=mergesort(l,mid)+mergesort(mid+1,r);
	while(i<=mid&&j<=r)
	{
		if(a[i]<=a[j])
		{
			b[k++]=a[i++];
		}
		else 
		{
			b[k++]=a[j++];
			ret+=mid-i+1;
		}
	}
	while(i<=mid)
	{
		b[k++]=a[i++];
	}
	while(j<=r)
	{
		b[k++]=a[j++];
	}
	for(int i=l,j=0;i<=r;i++,j++)
	{
		a[i]=b[j];
	}
	return ret;
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	
	cout<<mergesort(0,n-1)<<endl;
	
	return 0;
}

这个暂时还没搞明白，大概是用归并排序的思路，先分别进行递归，然后直接找出位于两边的符合题意的逆序数组，然后在进行归并排序，

子序列

判断子序列

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<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int n,m;
int a[N],b[N];
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=0;i<n;i++)
	{
		scanf("%d",&b[i]);
	}
	int i=0,j=0;
	while(i<n&&j<m)
	{
		if(a[i]==b[j])
		{
			i++;
		}
		j++;
		
	}
	if(i==n)printf("Yes\n");
	else printf("No\n");
}

利用双指针，让指针i，j从0开始，如果有a[i]=b[j]那么i++，不管i是否与j配对，都j++。
注意，这个数组是已经排好序的，因此不考虑排序问题。

最长不连续子序列

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<iostream>

using namespace std;
const int N=100010;
int a[N],s[N];
int n;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		
	}
	int res=0;
	for(int i=0,j=0;i<n;i++)
	{
		s[a[i]]++;
		while(s[a[i]]>1)
		{
			s[a[j]]--;
			j++;
		}
		res=max(res,i-j+1);
	}
	cout<<res<<endl
	
	return 0;
}

具体思路为，在j一定小于等于i的前提下，运用双指针算法，定义一个s数组来表示出现的数的次数，如果没有出现重复数组就一直让i++，直到出现了重复数组后，利用j把s数组中j的出现此时减去，然后j++，来让数组不断地向右移。

位运算

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<iostream>
using namespace std;
int lowbit(int x)
{
	return x&(-x);
}
int main()
{
	int n;
	cin>>n;
	while(n>0)
	{
		int x;
		cin>>x;
		int ret=0;
		while(x>0)
		{
			x-=lowbit(x);
			ret++;
		}
		cout<<ret<<' ';
		n--;
	}
	cout<<endl;
	
	return 0;
}

这里引入一个新概念，就是&符号在c++中的使用。
他表示与，就是两个数的二进制中相同部分。
例如10的二进制表达式为1010，那么-10就是0101+1=0110.最后两位都是10，这个时候10&-10就是0010，然后再用1010-0010=1000，同理这个时候补码就是0111+1=1000.再减去就是0，这样就得到了10的二进制1表达式中1的个数为2。

4个常用的基本位运算：

1，按位与：就是&，两个二进制数中都为1时才为1，否者就是0。
例如：100010 & 111110=100010。
2，按位或：就是|，两个二进制数中只要有一个1就是1，否则就是0。
例如：111001 | 100010 = 111011。
3，按位异或：就是^，两个二进制数中，相同则为0，不同则为1。
例如：11100 ^ 10001 = 01101。
4，非：就是~，1全部变为0，0全部变为1。

离散化-区间和

离散化的定义就是说将很大的值转化为下标，前提时有序，整数。


去重代码就是

1
2
3
vector<int> all;
sort(all.begin(),all.end());
all.erase(unique(all.begin(),all.end()),all.end());

unique函数就是将有序数组中第一次出现的数放到数组前面，重复出现的数放到数组后面，erase函数之前提到过就是删除数组中一个区间内的值，注意unique函数返回的值是一个地址，这个地址所指的位置时所有第一个出现的数的下一个数，也就是重复出现的数。

去重后下一步就是利用二分进行离散化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int find(int x)
{
int l=1;
int r=all.size();
	while(l<r)
	{
	int mid=l+r>>1;
	if(all[mid]>x)
		r=mid;
	else
		l=mid;
	}
	return l+1;
}

这个就是找出第一个大于x的数的下标。
离散化在处理数组相对值的时候很好用，
但不能处理绝对的数组值。

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 300010;
int n, m;
int a[N], s[N];
typedef pair<int, int> pii;
vector<int> all;
vector<pii> add, q;
int find(int x)
{
    int l = 0;
    int r = all.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (all[mid] >= x)
            r = mid;
        else
            l = mid+1;
    }
    return r + 1;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        int x, c;
        cin >> x >> c;
        all.push_back(x);
        add.push_back({x, c});
    }
    for (int i = 0; i < m; i++)
    {
        int l, r;
        cin >> l >> r;
        q.push_back({l, r});
        all.push_back(l);
        all.push_back(r);
    }
    sort(all.begin(), all.end());
    all.erase(unique(all.begin(), all.end()), all.end());
    for (auto item : add)
    {
        int x = find(item.first);
        a[x] += item.second;
    }
    for (int i = 1; i <= all.size();i++)
    {
        s[i] = s[i - 1] + a[i];
    }
    for(auto item:q)
    {
        int l = find(item.first);
        int r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }
        return 0;
}

这个b万一真是把我难坏了。
前面讲了去重和二分的代码。
那么后面的代码就很清晰了，重点时掌握这个离散化的意思，也就是说包括边界在内，我们要把300000组数据全部进行离散化，先当与把提及的数据装在另一个容器中，这样就直接对这个容器做处理就好了。
大致就是这样，以后不懂了再回来看把。