- 快排模板
- 归并模板—重要。
- 整数二分算法模板—再好好分析一下
- 求分段的区间重合个数
- 二维差分模板-----------差分。前缀和都从1开始，因为必须要空一个位置是0防止它越界
- 唯一剩余定理-----专门解决约数的个数问题和总和问题。
7.转移
转移
因为线段树建树的原因，所以线段树可以存放在一维数组中，通过u<<1和u<<1|1来进行逻辑上的划分。
线段树分单点查询和区间查询。他们都有不同的应用场景。
唯一剩余定理
对于底数和指数，我们可以用结构体来做。但最好的还是用map来做。节省空间。且一定是有序的，方便增加指数(结构体不好找到正确位置。)。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int MOD=1e9+7;
/*
struct node
{
int a;
int b;
}e[maxn];
似乎用map更方便
*/
map<int,int> mp;
int main()
{
vector<int>v;
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
//=======求质因数模板==================
for(int i=2;i<=n/i;i++)
{
if(n%i==0)
{
int cnt=0;
while(n%i==0)
{
cnt++;
n=n/i;
}
mp[i]+=cnt;
}
}
if(n>1) mp[n]++;
//=======求质因数模板==================
}
long long ans=1;
for(auto it:mp)//返回的不是地址？
{
ans=ans*( it.second +1)%MOD;
}
printf("%lld\n",ans);
return 0;
}
二维差分模板
第一步：room为原始数据，把b看作0.把每一位的数，以差分的形式插入b。最终完整的b表的前缀和就是原始数据。
修改时也和原来的插入是一样的，所以直接调用函数即可。
最后输出的时候，先用前缀和还原数据，然后输出。
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, q;
int room[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", &room[i][j]);
insert(i, j, i, j, room[i][j]);
}
}
while(q--)
{
int x1,y1,x2,y2,c;
cin>>x1>>y1>>x2>>y2>>c;
insert(x1,y1,x2,y2,c);//已插入的方式进行差分。
}
int sum=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];//用前缀和还原
j==1?printf("%d",b[i][j]):printf(" %d",b[i][j]);
}
puts("");
}
system("pause");
return 0;
}
求两个分段的区间相交的长度
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e3+10;
int n,m,q;
struct node
{
int l,r;
int flag;//0为1号，1为2号.
}e;
int cmp(const node &a,const node &b)
{
if(a.l==b.l) return a.r<b.r;
return a.l<b.l;
}
vector<node>v1;//x的最大区间。
vector<node>v2;//y的最大区间。
int main()
{
//freopen("input.txt", "r", stdin);
int t;
int n,m,x,y;
scanf("%d",&t);
while(t--)
{
scanf("%d %d %d %d",&n,&m,&x,&y);
int k=0;
for(int i=0;i<x;i++)
{
scanf("%d %d",&e.l,&e.r),e.flag=0;
v1.push_back(e);
}
for(int i=0;i<y;i++)
{
scanf("%d %d",&e.l,&e.r),e.flag=1;
v2.push_back(e);
}
//======================区间：重合个数======================
int cnt=0;
for(int i=0;i<v1.size();i++)
{
if(v1[i].r-v1[i].l+1<m) continue;
for(int j=0;j<v2.size();j++)
{
if(v2[j].r-v2[j].l+1<m) continue;
int L,R;
L=max(v1[i].l,v2[j].l);
R=min(v1[i].r,v2[j].r);
cnt+=max(R-L+2-m,0);
}
}
cout<<cnt<<endl;
//======================区间：重合个数======================
v1.clear();
v2.clear();
}
return 0;
}
/*
2
100 10 2 1
1 50
51 100
1 100
82
100 10 1 1
1 100
1 100
91
*/
整数二分算法模板
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
/*
什么时候用：1.区间。2.有序，或者有一个性质可以将区间分成两部分。--[所以有时候关键要找性质。]
具体做法：1.找到中间值。2.分析性质，根据性质确定，l,r,是绿色还是红色。
二分整数模板-----整数二分唯一注意的就是边界问题。
|------------||-------| 二分就是确定边界问题的。左区间用红色模板来确定，右区间用绿色模板来确定。（）
<=x >x
<x >=x
*/
int n,m,x;
int q[maxn];
int check1(int n)//找最开始出现的x，所以设置性质是n>=x为一个区间，n<x为一个区间
{
if(n>=x) return 1;
return 0;
}
int check2(int n)//找最后出现的x，所以设置性质是n>x为一个区间，n<=x为一个区间
{
if(n>x) return 1;
return 0;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++ ) scanf("%d", &q[i]);
while (m -- )
{
scanf("%d", &x);
//整数模板红色
int l=0,r=n-1,mid=l+r>>1;
while(l<r)
{
mid=l+r>>1;
if(check1(q[mid])) r=mid; else l=mid+1;
}
if(q[l]!=x) cout<<"-1 -1"<<endl;
else
{
cout<<l<<" ";
//整数模板绿色---因为是绿色l=mid,所以要l+r+1>>1防止死循环
l=0,r=n-1,mid=l+r+1>>1;
while(l<r)
{
mid=l+r+1>>1;
if(check2(q[mid])) r =mid-1;else l=mid;
}
cout<<r<<endl;
}
}
system("pause");
return 0;
}
归并模板
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
/*
归并：
1.确定中点
2.递归排序。
3.|___________|____________| 合并到tmp数组中。
思想：总结，以后能一遍过。
写退出口---划分区间成两份----排序---合并----
*/
void merge_sort(int arr[],int l,int r)
{
int tmp[maxn];
if(l>=r) return;//当前没有数，时退出。
int mid=l+r>>1;
merge_sort(arr,l,mid);merge_sort(arr,mid+1,r);//递归排序左边，递归排序右边。
int i=l,j=mid+1,k=0;//j=mid+1 因为我的i是包含mid。
while(i<=mid&&j<=r)//mid为左边的边界。r为右边的边界。
{
if(arr[i]<=arr[j]) tmp[k++]=arr[i++]; else tmp[k++]=arr[j++];
}
while(i<=mid) tmp[k++]=arr[i++];//最后就是把剩下的都放进来。
while(j<=r) tmp[k++]=arr[j++];
for(int i=l,j=0;i<=r;i++,j++) arr[i]=tmp[j];
}
int a[maxn];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
merge_sort(a,1,n);
for(int i=1;i<=n;i++) i==1?printf("%d",a[i]):printf(" %d",a[i]);
return 0;
}
/*
int i=l,j=mid+1,k=0;:定义双指针也是i=l而不是i=1.----他是【分段】的。
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
因为我们要考虑到右边的数组排序。所以不是简单的for(int i=0;i<n;i++)
学习：i=l,从这里往后累加。
*/
快排模板
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
/*
快排：
1.确定分界点。(可以是左边值，可以是中间值，也可以是随机)
2，调整区间，使得左边区间保证<=x,右边区间>=x;
3.通过递归的方式进行处理。
思想：总结，以后能一遍过。
递归，所以要写退出口。然后就是i和j分别向内检测x，满足条件的进行swap，然后进行下一次的递归。---分而治之。
*/
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;//退出口。 ----一般都是l==r代表结束了。
int i = l - 1, j = r + 1, x = q[l + r >> 1];//l-1是由于do i++；r+1是由于j--.
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);//----这里是j不是i的原因，应该是只有j是可以确定j的左边一定都小于等于x，j的右边一定是大于等于x
}
int a[maxn];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
quick_sort(a,1,n);
for(int i=1;i<=n;i++) i==1?printf("%d",a[i]):printf(" %d",a[i]);
return 0;
}
/*
1.x是用来分界的。
2.当然是交换内容数据啊。
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
就是先走一步再看结果。
*/
