莫比乌斯反演

概述莫比乌斯反演定理:$$ F(n)=\sum_{d|n}f(d) $$--------->$$ f(n)=\sum_{d|n}μ(d)F(\frac{n}{d}) $$

- 阅读全文 -

TJOI2016&HEOI2016-排序

题目在2016年,佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题,现在他在研究一个难题,需要你来帮助他。这个难题是这样子的:给出一个1到n的全排列,现在对这个全排列序列进行m次局部排序,排序分为两种:• (0,l,r)表示将区间[l,r]的数字升序排序• (1,l,r)表示将区间[l,r]的数字降序排序最后询问第q位置上的数字。思路第一反应是数据结构强搞,肯定有一

- 阅读全文 -

模板集合

正向表int tot=0,h[M]; struct edge{ int nxt; int to,cost; }G[3*M]; void add(int a,int b,int c){ G[++tot]=(edge){h[a],b,c}; h[a]=tot; }

- 阅读全文 -

排序算法

稳先从最简单的计数排序开始吧。计数排序(O(n+k))#include<bits/stdc++.h> using namespace std; int n;int A[105],B[105]; int cnt[105]; int main(){ cin>>n; for(int i=1;i<=n;i++){ scanf("%d&

- 阅读全文 -

动态逆序对(CDQ分治)

题目对于序列 $A$ ,它的逆序对数定义为满足 $i<j$ ,且 $Ai>Aj$ 的数对 $(i,j)$ 的个数。给定 $1$ 到 $n$ 的一个排列,按照某种顺序依次删除 $m$ 个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。思路1我们反向来看,离线询问,将问题转变成一个一个往序列中加入元素。接着很容易发现这是一道三元组的题目,对于两个数来说,必须在满足题目条件的同

- 阅读全文 -