一，树状数组尾声
仅一个题目：树状数组求解最长上升子序列
思路：设置dp[i]维护以a[i]为结尾的最长上升子序列长度
条件：若有a[j] 满足(1)j<i (2)a[j]<a[i]则有dp[i]=dp[j]+1
若保证dp[i]最大即在满足(1)(2)条件下使dp[j]最大
求最大值的过程使用树状数组维护
有函数
ask(pos)：查询值域 [1,pos]\内最大的 dp 值；
update(k,v)：在值域 k 的位置，更新保存更大的 dp 值 v
这是整体思路，详细解析在注释
#include<bits/stdc++.h> using namespace std; const int N=1e6+5; int n,a[N],c[N],dp[N],ans; int lowbit(int n){ return n&-n; } void update(int k,int v){ for(int i=k;i<N;i+=lowbit(i)){ c[i]=max(c[i],v); } } int ask(int pos){ int ans=0; for(int i=pos;i;i-=lowbit(i)){ ans=max(ans,c[i]); } return ans; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); a[i]++; } //c[x] 维护值等于 x 的位置对应的最长上升子序列长度最大值 //更新条件(1)i<j(2)a[i]<a[j] for(int i=1;i<=n;i++){ dp[i]=ask(a[i]-1)+1; //查询值域[1,a[i]-1](前缀)所有对应的dp值的最大值 //后面a[i+1]到a[n]没update能保证位置i<j(1) //值域到a[i]-1保证a[j]值一定小于当前位置值a[i](2)，+1即表示接上a[i] update(a[i],dp[i]); ans=max(ans,dp[i]);//所有位置最长上升子序列的最大值即为答案 } printf("%d\n",ans); }二，拓扑排序
适用于有向无环图 DAG，若图有环则不存在拓扑序
图中任意一条有向边 u to v，顶点 u 在序列里一定出现在顶点 v 的前面， 则这个序列就称为图 G 的拓扑序列，求解该序列的过程叫做拓扑排序。
求解过程就是先设置队列，后遍历全图的点，若该点入度为0入队，后一直遍历队列出队直到队列为空，遍历队列中点的临界点，若其入度为0入队
模板如下
void kahn(){ queue<int> q; // 入度为0的点入队 for(int i=1;i<=n;i++) if(in[i]==0) q.push(i); while(!q.empty()){ int u=q.front(); q.pop(); topo.push_back(u); for(int v:g[u]){ in[v]--; if(in[v]==0) q.push(v); } } } main函数 for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; g[u].push_back(v); in[v]++； } kahn();例题解析：食物链
非常典型的模板
如图所示为某生态系统的食物网示意图，据图回答问题。
现在给你n个物种和m条能量流动关系，求其中的食物链条数。
物种的名称为从1到n编号
M条能量流动关系形如
a1 b1
a2 b2
a3 b3
......
am-1 bm-1
am bm
其中ai bi表示能量从物种ai流向物种bi,注意单独的一种孤立生物不算一条食物链
我们分析题目
食物网 = 有向无环图 DAG（自然界不会出现捕食环，不存在循环），可以用拓扑排序 + DP求解。
设 dp[u]：以 u 为终点的完整食物链数量。
- 若 u 是生产者（入度 = 0）：它自己不能算食物链，但它是路径起点，dp[u] = 1（代表一条待延伸的起始链）；
- 若 u 不是生产者：(
)（所有有边
的 v 的 dp 值相加）。
学过八下生物的都知道，在计算食物链条数的时候，若一点链接到该点，该点的食物链数量可以继承那一个点的食物链数量，若有多点则可全部继承进行累加
我们再看第一个点，生产者虽不算一条食物链，但任意一点链接生产者都可以构成一条食物链，根据上面的继承理论，有dp[生产者]=1
输出方面：只有出度 = 0的点才是食物链终点，遍历所有点 u： 如果 out[u] = 0，就把 dp[u] 累加到总答案里。 原因：只有走到没有下一捕食者的生物，才是一条完整食物链。
代码如下
#include<bits/stdc++.h> const int N=2e5+5; using namespace std; int n,m,in[N],out[N],dp[N],ans; vector<int> g[N]; void tuopu(){ queue<int> q; for(int i=1;i<=n;i++){ if(!in[i]&&out[i]) q.push(i),dp[i]=1; } //dp[i]以i为终点的食物链条数 while(!q.empty()){ int u=q.front(); q.pop(); for(int v:g[u]){ in[v]--; dp[v]+=dp[u]; if(!in[v]) q.push(v); } } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; g[u].push_back(v); in[v]++;out[u]++; } tuopu(); for(int i=1;i<=n;i++){ if(!out[i]) ans+=dp[i]; } cout<<ans; }三，并查集初步
树形结构，能够快速进行合并和查询的集合
作用：快速判断两点是否连通、合并连通块
模板如下：
初始化 for(int i=1;i<=n;i++){ fa[i]=i; } 找祖先 int Find(int x){ if(x==fa[x]) return x; return fa[x]=Find(fa[x]); } 合并 void merge(int x,int y){ x=Find(x),y=Find(y); if(x==y) return ; if(sz[x]>sz[y]) swap(x,y); fa[x]=y; sz[y]+=sz[x]; }今天到这
-路由导航与页面跳转)
