双指针
头文件
floyd算法
组合模板2
暴力打表
链式向前星
线段树
二分
gcd
最短路
//========================== 双指针===========================
int sum=0,ans=0;
int l=0,r=0;
while(1)//当r到n的时候退出。
{
while(l<=r&&r<n&& XXX)// 条件：左指针不超过右指针+右指针不超出边界+其他条件。
{
r++;// 右指针移动
ans=max(ans,r-l);//更新答案。
}
if(r>=n) break;
l++;//左指针移动
}
//========================== 头文件===========================
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=1e9+5;
const int maxn=1e5+10;
const int MOD=998244353;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int main(){
return 0;
}
//========================== floyd算法===========================
void floyd()
{
for (int k = 1; k <= n; k++)
{
for (int i = 1; i <= n; i++)
{
if(g[i][k]==INF) continue;//---剪枝对于1000内的。
for (int j = 1; j <= n; j++)
{
if (g[i][j] > g[i][k] + g[k][j])
{
g[i][j] = g[i][k] + g[k][j];
}
}
}
}
}
void init()//初始化
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i == j)
g[i][j] = 0;
else
g[i][j] = INF;
}
}
}
int path[maxn];
void print(int s,int t){
if(s==t){
printf("Path: %lld",t);
return ;
}
print(s,p[t]);
printf(" %lld",t);
}
//========================== 组合模板2===========================
ll ksm(ll a,ll k){
ll ans=1;
while(k)
{
if(k&1) ans=ans*a%MOD;
a=a*a%MOD;
k>>=1;
}
return ans;
}
ll fact[maxn];
ll infact[maxn];
void CC(){//预处理型 O(1e8)
fact[0]=1,infact[0]=1;//初始化0的情况。
for(int i=1;i<maxn;i++) fact[i]=fact[i-1]*i%MOD;
for(int i=1;i<maxn;i++) infact[i]=infact[i-1]*ksm(i,MOD-2)%MOD;
}
ll C(ll b,ll a){
return fact[b]*infact[a]%MOD*infact[b-a]%MOD;
}
//=======================暴力打表===================================
freopen("input.txt", "w", stdout);
//=======================链式向前星===================================
ll e[maxn<<1],w[maxn<<1],ne[maxn<<1],h[maxn<<1],idx=0;
void add(ll u,ll v,ll val){
e[idx]=v,w[idx]=val,ne[idx]=h[u],h[u]=idx++;
}
//=======================线段树===================================
//1.节点属性值的确定。左边界，右边界。及其包裹内部的最大值
struct node{
ll l,r;
ll v,tag; // 区间[l,r]中的值。
ll lazy;
}tr[maxn<<2];
//3.pushup--由子节点信息推出父节点信息。 ---如果要给某点赋值，可以在写个重载 pushup(&u,&l,&r);
void pushup(node &root,node &left,node &right){
root.v=left.v+right.v;
root.tag=left.tag+right.tag;
}
void pushup(ll u){
pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void pushdown(ll u){
node &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
if(root.lazy){//简单优化一下 只有在有懒标记的时候才下放
left.lazy+=root.lazy ,left.v+=root.lazy*(left.tag);
right.lazy+=root.lazy ,right.v+=root.lazy*(right.tag);
root.lazy=0;
}
}
//2.建立线段树
void build(ll u,ll l, ll r){
tr[u]={l,r};
if(l==r) {//如果是叶子节点则结束。--否则
tr[u]={l,r,w[l],b[l],0};
return ;
}
ll mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);//分裂成两部分。
pushup(u);
}
//4.修改操作 modify1(int u,int x,int value)单点修改 modify2(int u,int l,int r, int value) 区间修改
//意识：单点修改一点是修改叶子节点。上层节点都是由pushup来更新
//区间修改，则是任何位置都可以修改，并且在查询和修改的时候，做下放操作。
void modify1(ll u,ll x,ll tag){
if(tr[u].l==x&&tr[u].r==x) {tr[u].tag=tag;}//tr[u].l==x&&tr[u].r==x表示当前是叶节点。
else{//否则要判断是往左边递归还是右边递归
pushdown(u);
ll mid=tr[u].l+tr[u].r>>1;
if(x<=mid) modify1(u<<1,x,tag);
else modify1(u<<1|1,x,tag);
pushup(u);//底层完成修改后，上面也得更新。
}
}
void modify2(ll u,ll l,ll r,ll v){
if(tr[u].l>=l&&tr[u].r<=r) {//将这个节点的sum和lazy改一下即可
tr[u].v+=(tr[u].tag)*v; //细节：在pushdown中 本身节点是没有进行累加。因为在这里已经累加了。
tr[u].lazy+=v;
}else{
pushdown(u);
ll mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify2(u<<1,l,r,v);//误区：如果l<=mid说明， 它的左边界在左子树，我进左边
if(r>mid) modify2(u<<1|1,l,r,v);
//即我们要查询的那个区间是不能动的。所以一定是[l,r]
pushup(u);
}
}
//5.查询函数 query(int u,int l,int r) ---就是考虑三种情况 ---1.ll型 2.node型
node query(int u,int l,int r){
if(tr[u].l>=l&&tr[u].r<=r){ //树中节点，已经被完全包含在[l,r]中。
return tr[u];
}
pushdown(u);
int mid= tr[u].l+tr[u].r>>1;
//否则 如何判断有没有交集呢？ 就是l<=mid r>mid 说明他们要分裂开来。---什么时候用node呢？
if(r<=mid) return query(u<<1,l,r);//只横跨左子树
else if(l>mid) return query(u<<1|1,l,r);//只横跨右子树
else{//横跨中间
auto left=query(u<<1,l,r);
auto right=query(u<<1|1,l,r);
node res;
res.v=left.v+right.v;
res.tag=left.tag+right.tag;
return res;
}
}
void out(int u){
if(u==4*n){
return;
}
out(u+1);
cout<<"fa:"<<u<<" "<<tr[u].v<<endl;
}
//=======================二分===================================
int l=0,r=1e9;
while(l<r)
{
int mid=l+r+1>>1;//为啥还要+1？
//答：---因为我们用的左开右闭。(0,1]这样的形式。如果不+1：0+1>>1就会=0.而我们知道应该可以取到1.所以0+1+1>>1就可以取到1了。
if(check(mid)) l=mid;//---答案想要往左边缩时，r=mid-1，mid要+1.答案想要往右缩时，l=mid+1. mid不用+1
else r=mid-1;
}
//=======================gcd===================================
ll gcd (ll a,ll b){
return b ? gcd( b , a % b ) : a;
}
//=======================最短路===================================
ll G[maxn][maxn],dis[maxn],st[maxn];//*st是锁定不动。
void dijiestr(ll s){
//1:初始化一下。2：总共遍历n-1遍，每次找到dis中最小的没访问的点。确定并且更新。
memset(dis,INF,sizeof dis);
memset(st,0,sizeof st);
dis[s]=0;
for(int i=0;i<n-1;i++){//总共遍历n-1遍
ll pos=-1;//找到每次dis中最小的还没被锁的位置
for(int j=0;j<n;j++){
if(!st[j]&&(pos==-1||dis[pos]>dis[j])) pos=j;//还没被确定，且找到dis中最短的那个。
}
st[pos]=1;
for(int j=0;j<n;j++) {//确定后进行更新。
if(dis[pos]+G[pos][j]<dis[j]){
dis[j]=dis[pos]+G[pos][j];
}
}
}
}
- 不进位加减法
- 线段树
- 离散化
- 区间合并
- 位运算----懂得liwbit的实现过程。
- 分解质因数-----根号n的做法—约数
- 埃氏筛法
- 几何—点乘和叉乘
- 几何—直线
- sg暴力模拟代码—打表，找规律
- 卡特兰数
- 从大到小覆盖染色问题
- 树状数组实现逆序对(二位偏序)----顺便复习树状数组
树状数组实现逆序对(二位偏序)
为什么要离散化呢，我认为是，数字很大，爬的就很高，而我们只需看他们的前后顺序，与大小无关，所以离散化可以优化爬树的过程。
vector<int> bk;
int a[maxn],tree[maxn],n;
int lowbit(int i) {return i &-i;}
void updata(int i,int val)
{
while(i<=n)
{
tree[i]+=val;
i+=lowbit(i);
}
}
long long query(int i)
{
long long sum=0;
while(i>0)
{
sum+=tree[i];
i-=lowbit(i);
}
return sum;
}
int main()
{
cin>>n;
long long sum=0;
for(int i=1;i<=n;i++) cin>>a[i],bk.push_back(a[i]);
sort(bk.begin(),bk.end());
bk.erase(unique(bk.begin(),bk.end()),bk.end());
for(int i=1;i<=n;i++)
{
int pos=lower_bound(bk.begin(),bk.end(),a[i])-bk.begin()+1;//使用bk映射得到离散化结果。
sum+=i-1-query(pos);
updata(pos,1);
}
cout<<sum<<endl;
return 0;
}
从大到小覆盖染色问题
aaddaa 2-5 小于c的变成c—>acddca---->O(n)的复杂度
来源题目： https://ac.nowcoder.com/acm/contest/11181/C
for(int k=find(rr);ll<=k;k=find(k))
{
s[k]=max(s[k],(char)i);
fa[k]=find(k-1);
}
卡特兰数
1, 1, 2, 5, 14, 42, 132, 429, 1430
1.递归写法-->直接卡特兰数的，不需要拐弯抹角的：头尾相乘
h[0]=1;
h[1]=1;
for(int i=2;i<40;i++)//长度。
{
for(int j=0;j<i;j++)
h[i]+=h[j]*h[i-j-1];
}
2.预处理组合数，直接相减法。C(m,n+m)-C(m+1,n+m)
An=Cn*m!*n!----->(m+n)!*[(m+1-n)/m+1];//组合变排列。
组合可以由杨辉三角累加得到。---网格
sg暴力模拟代码—打表，找规律
0代表必败。1代表必胜。
if(符合这一条件)
{
int a=g(y,m+1,d) , b=g(y,m+1,1);//dfs出所有情况。---记忆化搜索。
if(a==0 || b==0) return sg[y][m][d]=1;// 如果我能让对方站在0上，我一定会让它站在0上。所以只要有0就是1.
else if(a && b) return sg[y][m][d]=0;// 如果全是1，才是0.
}
几何—直线
//=============================直线与直线模块=============================
struct line//第一种表示方法：用直线上的两个点来表示
{
node p1,p2;//这条线有两个点。
line(){};
line(node a,node b){p1=a,p2=b;}
}e1,e2;
int p_l_relation(node a,line b) //-----------------点与线的关系
{
int c=sgn(cross(a-b.p1,b.p2-b.p1));
if(c==0)return 0;//直线上
if(c<0) return 1;//左边
if(c>0) return 2;//右边
}
int l_relation(line a,line b)//line_relation--------线与线的关系
{
if(sgn(cross(a.p2-a.p1,b.p2-b.p1))==0)//叉乘为0，说明要么平行要么重合 ---a.p2-a.p1,两个点构成了线/向量。
{
if(p_l_relation(a.p1,b)) return 1;//重合
return 0; //平行
}
return 2;//否则就是相交
}
node getnode(node a,node b,node c,node d)//----------求直线之间的交点
{
double ABD=cross(d-a,b-a);
double ABC=cross(b-a,c-a);
//if(ABC==0||ABD==0) return node(0,0);---如果面积相等
return node((ABD*c.x+ABC*d.x)/(ABD+ABC),(ABD*c.y+ABC*d.y)/(ABD+ABC));
}
bool s_s_relation(Line ab,Line cd)//------------------线段与线段交点，判断是否有交点，如果有调用getnode即可。
{
double f1=cross(cd.p2-ab.p1,ab.p2-ab.p1),f2=cross(cd.p1-ab.p1,ab.p2-ab.p1);
double f3=cross(ab.p2-cd.p1,cd.p2-cd.p1),f4=cross(ab.p1-cd.p1,cd.p2-cd.p1);
if(f1*f2<=0&&f3*f4<=0) return true;//注意要等于0.考虑一个线段的端点在另一个线段上。
return false;
}
//=============================直线与直线模块=============================
几何—点乘和叉乘
求面积用叉乘
//=====================================点与向量的最基本模板==================================
const double eps=1e-8;//偏差值
double sgn(double x)
{
if(fabs(x)<eps) return 0;//他的绝对值比偏差值eps还小，那就是真的0.
return x>0?1:-1;
}
struct node//-----向量
{
double x,y;
node(){}
node (double a,double b){x=a;y=b;} //一定要的。
friend node operator+(node a,node b){return node(a.x+b.x,a.y+b.y);}
friend node operator-(node a,node b){return node(a.x-b.x,a.y-b.y);}
friend node operator*(int a,node b){return node(a*b.x,a*b.y);}
friend node operator/(int a,node b){return node(a/b.x,a/b.y);}//p[i]=node(10*node(x,y));
friend bool operator==(node a,node b){return sgn(a.x-b.x)==0&&sgn(a.y-b.y)==0;}
}p[maxn];//point---点
typedef node Vector;//点和向量其实是一样的结构体。
double cross(Vector a,Vector b) {return a.x*b.y-a.y*b.x;}//叉乘。
double dot(Vector a,Vector b) {return a.x*b.x+a.y*b.y;}//点乘。
//=====================================点与向量的最基本模板==================================
埃氏筛法
可以得到前n个数有多少个质数，且是什么质数prime。也可以得到一张质数表vis，用于判断是否是质数。
埃筛可求欧拉函数。
//这些只能在数组放的下的情况下。否则埃筛也没用。
int prime[maxn];
int vis[maxn];
int phi[maxn];
int ss(int n)
{
vis[0]=1,vis[1]=1;
int pos=0;
for(int i=2;i<=n;i++)
{
if(!vis[i]) {prime[pos++]=i;}//phi[i]=i-1;
for(int j=0;j<pos&&i*prime[j]<=n;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)
{
//phi[i*prime[j]]=phi[i]*prime[j];
break;
}
//phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
return pos;
}
分解质因数
约数就不写了，注意i=n/i即可
约数的个数和约数的和，也可以通过分解质因数+定理求得
struct node
{
int a;
int b;
}e[maxn];
int divide(int n)
{
int pos=0;
for(int i=2;i<=n/i;i++)
{
if(n%i==0)//如果n%i==0 那么i一定是质数。
{
int cnt=0;
while(n%i==0)
{
n=n/i;cnt++;
}
e[pos].a=i;
e[pos++].b=cnt;
}
}
if(n>1) e[pos].a=n,e[pos++].b=1;
return pos;
}
位运算
lowbit 可以获得数的最右边的1所所代表的数.
所以每次-lowbit相当于每次拿掉最右边的一个1，拿的次数就是1的个数。
void lowbit(x) {return x&-x;}
确定x的第K位是0还是1 x>>k&1;
区间合并
首先排好序，按左边从小到大排序，如果左边相等看右边。
然后就是遍历一遍，O(N)的复杂度完成。
具体判断是总结了三个性质：
1.如果左端点在前一个区间的外部，那么前一个端点就是完整的区间。放入ans
2.如果左端点在前一个区间的内部，
2.1如果右端点在外部，则前一个区间的右端点更新成当前区间的右端点。
2.2如果右端点在内部，则无变化。
vector<pair<int ,int> >v;
int cmp(pair<int,int>a,pair<int ,int>b)
{
if(a.first==b.first) return a.second<b.second;
return a.first<b.first;
}
vector<pair<int,int> >ans;//真正剩下的区间。
void merge(vector<pair<int ,int> >v)
{
sort(v.begin(),v.end(),cmp);
int l=v[0].first,r=v[0].second;
for(int i=1;i<v.size();i++)
{
if(v[i].first<=r)//内部
{
if(v[i].second>r) r=v[i].second;//右端点在外部
//右端点在内部无变化
}
else
{
ans.push_back({l,r});
l=v[i].first,r=v[i].second;
}
}
ans.push_back({l,r});//最后一个
}
离散化
vector<int> bk;
bk.push_back(x);//全部放入bk数组中。
sort(bk.begin(),bk.end());//排序
bk.erase(unique(bk.begin(),bk.end()),bk.end());//去重
x=lower_bound(bk.begin(),bk.end(),x)-bk.begin();//二分获得离散化后下标
线段树
node_merge根据题目进行编写
#define lc (u<<1)
#define rc (u<<1|1)
void build(int u,int l,int r)
{
tr[u].l=l;tr[u].r=r;
if(l==r)//----都为一个时，结束。
{
//tr[u].sub_num=tr[u].llen=tr[u].rlen=1;//各种初始化
return ;
}
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
//tr[u] = node_merge(tr[lc],tr[rc]);//对于包含信息的更新：如求和sum、长度len、最大值max等
}
void update(int u,int index,int val)//单点修改。index就是要修改的点
{
if(tr[u].l==tr[u].r) {a[index]=val;return ;}
int mid=(tr[u].l + tr[u].r)>>1;
if(index<=mid) update(lc,index,val);
else update(rc,index,val);
tr[u] = node_merge(tr[lc],tr[rc]);
}
node getsum(int u,int l,int r)//区间求和
{
if(l<=tr[u].l&&tr[u].r<=r) return tr[u];//如果在这个范围里面，那么我只需要它信息就够了。否则
int mid = (tr[u].l+tr[u].r) >> 1;
if(r<=mid) return getsum(lc,l,r);//如果都在左边。---注意：左边有等号
else if(l>mid) return getsum(rc,l,r);//如果都在右边------右边没等号
else return node_merge(getsum(lc,l,mid),getsum(rc,mid+1,r));//否则两边都找。----这里就又需要合并。
}
不进位加减法
int addk(int a,int b,int k)//k是进制
{
int base,aw,bw,ret=0;
for(base=1;base<=max(a,b);base*=k)
{
aw=a/base%k;
bw=b/base%k;
ret+=(aw+bw)%k*base;//addk
//ret+=(aw-bw+k)%k*base;//subk
}
return ret;
}
