qbxt7月笔记

二分

int l,r;
while(l<=r){
	
	int mid=(l+r)/2;//>>1
	
	if(ok(mid))l=mid+1;
	
	else r=mid-1;

}

ans=l;

lower_bound()和upper_bound()

二分查找

二分查找需要排序

右端点开区间（right需要+1）

greater()的用法

#include<bits/stdc++.h>
using namespace std;
int main(){
  int a[4];
  
  for(int i=1;i<=4;i++)
  cin>>a[i]; 
  
  sort(a+1,a+5,greater<int>());
  
  for(int i=1;i<=4;i++)
  cout<<a[i]<<" "; 
  
  
  
  return 0; 
}

二分答案

上下取整

求最大值最小最小值最大

快速幂

搜索

DFS

BFS

贪心

STL堆

优先队列

STL priorty_queueu:

#inclde<queue>
priority_queue<int> q;
q.push();
q.top();
q.pop();

LCA

RMQ & ST表

树状数组

设树状数组为C，x的末尾有k个0，则C[x]表示A数组中A[x-2^k+1,x]的和。

使用lowbit( x ) = x & -x可以得到2^k的值，这里不讲解为什么这个位运算是对的。

#include<iostream>
#include<cstdio>
#define lowbit(i) ((i)&-(i))
#define int long long
using namespace std;
int c[1008600]; 
int n,m;
int find(int x){
int ans=0;
for(int i=x;i>0;i-=lowbit(i))
	ans+=c[i];

	return ans;
}

void modify(int x,int y)
{
	for(int i=x;i<=n;i+=lowbit(i))
		c[i]+=y;
}


signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
{
	int x;
	cin>>x;
	modify(i,x);
}

while(m--)
{
int opt,x,y;
cin>>opt>>x>>y;
if(opt==1)modify(x,y);
else cout<<find(y)-find(x-1)<<"
";
}


return 0;
}

逆序对

线段树

DP

图论

前置知识

图的存储

邻接矩阵

G[i][j]表示点i和点j之间的关系
G[i][i]=0
优：快速查询
缺：稀疏图浪费空间

邻接表

缺：单次查询慢
稠密图遍历常数大
优：节省空间，处理重边和自环