[TOC]
typedef long long int ll;
typedef double db;
const db EPS=1e-7; // 有时候也用eps-
浮点数精度设置
cout<<fixed<<setprecision(15); -
关闭流同步
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
template<typename I>I qread(){
I x=0;char ch=getchar();
while(ch<'0' || ch>'9'){ ch=getchar(); }
while(ch>='0' && ch<='9'){ x=x*10+ch-'0';ch=getchar(); }
return x;
}template<typename I>I qread(){
I x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}// 需测试是否可用
__int128 get128() {
__int128 x = 0, sgn = 1;
char c = getchar();
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') sgn = -1;
for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
return sgn * x;
}
void print128(__int128 x) {
if (x < 0) {
putchar('-');x = -x;
}
if (x >= 10) print128(x / 10);
putchar(x % 10 + '0');
}scanf("%[^\n]", s) // 需测试是否可用
getline(cin, s)
gets(buf,MAXN,stdin);对$[1,n]$区间整数二分，$work(x)$是一个函数，$x$较大的时候为true，较小时为false，输出最小的令$work(x)$为true的$x$，如果不存在输出0
int il=1,ir=n,imid,re=0;
while(il<=ir){
imid=(il+ir)>>1;
if(work(imid)){
re=imid;ir=imid-1;
}else{
il=imid+1;
}
}对$[l,r]$区间实数二分，找$work(x)$为true最小的点，小于答案的$work$为false，大等于的为true
db mid;
while(r-l>EPS){
mid=(l+r)/2;
if(work(mid)){
r=mid;
}else{
l=mid;
}
}
// 之后使用l或者r都行。。。反正区间范围很小了lower_bound(a+1,a+n+1,num); // 返回指向a[1...n]中第一个大于等于num的数字的指针
upper_bound(a+1,a+n+1,num); // 返回指向a[1...n]中第一个大于num的数字的指针
// 如果不存在返回a+n+1
// 可以通过upper_bound查找小于等于某个数的元素数量在区间$[l,r]$上找类二次函数$f(x)$的极小整点，注意整数三分取不到边界点，需要特判
double tri(){
int l=1,r=1e9;
while(r-l>5){
int lmid=(1ll*l*2+r)/3;
int rmid=(1ll*l+r*2)/3;
double flmid=f(lmid),frmid=f(rmid);
if(flmid<=frmid){
r=rmid;
}else{
l=lmid;
}
}
double ans=f(l);
for(int i=l+1;i<=r;++i){
ans=min(f(i),ans);
}
return ans
}实数三分更简单些，也不需要考虑端点问题
这里求的是$f(x)$的极大值点
db l=0,r=1e9,lmid,rmid; // 根据需要取
while(r-l>eps){
lmid=(l*2+r)/3;
rmid=(l+r*2)/3;
if(f(lmid)>f(rmid)){
r=rmid;
}else{
l=lmid;
}
}
// 之后用l或r都行const int MAXN=1e5+10;
int v[MAXN],vd[MAXN],n,tot;
void lsh(){
for(int i=1;i<=n;++i){
vd[i]=v[i];
}
sort(vd+1,vd+n+1);
tot=unique(vd+1,vd+n+1)-vd-1;
for(int i=1;i<=n;++i){
v[i]=lower_bound(vd+1,vd+tot+1,v[i])-vd;
}
}适用于下标从1开始的数组
typedef long long int ll;
const int N = 50005;
int n,m,maxn,c[N];
struct query {
int il, ir, id;
bool operator<(const query &x) const {
if (il/maxn!=x.il/maxn) return il < x.il;
return (il/maxn)&1?ir<x.ir:ir>x.ir;
}
}qs[N];
void work(int co,ll p){...} // 自己设计
// in main
maxn = sqrt(n);
// 输入
sort(qs+1,qs+m+1);
cnt[c[1]]=1; // 初始区间放在了[1,1]，这样不容易错，但是记得要把相关信息也初始化了
for (int i=1,l=1,r=1;i<=m;i++) {
while (l > qs[i].il) work(c[--l],1);
while (r < qs[i].ir) work(c[++r],1);
while (l < qs[i].il) work(c[l++],-1);
while (r > qs[i].ir) work(c[r--],-1);
// 更新答案
}启发式分治是一种分治的思路。对于区间$[il,ir]$，下述算法：
的时间复杂度是$O(an+bn\log n)$
这个时间复杂度的证明是利用树剖的性质做的
典型例题：P2949 [USACO09OPEN]Work Scheduling G
简单来说，利用堆来维护选过的，每次遇到新的，就和堆里的比一下，再选合适的
典型例题：P1792 [国家集训队]种树
求$n$元环上取$m$个元素，不能取相邻的元素时，取得的价值最大
一句话概括思路：每次取一个元素出来后，将其与两边的元素合并成一个大元素，这个元素的值是两边的元素价值和减被选出来的元素价值，这样就实现了“反悔”，又不违背条件
const int N=2e5+10;
struct Node{
int pre,nxt,va,id;
bool operator < (const Node & nn) const {
return va<nn.va;
}
}nd[N];
int n,m;bool uned[N];
void unio(int id){
int pre=nd[id].pre,nxt=nd[id].nxt;
nd[id].nxt=nd[nxt].nxt;
nd[nd[nxt].nxt].pre=id;
nd[id].pre=nd[pre].pre;
nd[nd[pre].pre].nxt=id;
nd[id].va=nd[pre].va+nd[nxt].va-nd[id].va;
uned[pre]=uned[nxt]=true;
}
int work(){
// 进来的时候保证双向链表环已经连好了
priority_queue<Node>q;
for(int i=1;i<=n;++i){
q.push(nd[i]);
}
int ans=0;Node u;int id;
while(m){
u=q.top();q.pop();
if(uned[u.id]) continue;
--m;id=u.id;ans+=nd[id].va;
unio(id);q.push(nd[id]);
}
return ans;
}typedef long long int ll;
ll gcd(ll a, ll b){
return b==0?a:gcd(b,a%b);
}可以使用$\mathrm{lcm}(a,b)=\frac{ab}{\gcd(a,b)}$求$\mathrm{lcm}$
对于要取模的情况，可以使用分解因数做
带模版本
ll qpow(ll a,ll x,ll M){
ll ret=1;
while(x){
if(x&1) ret=ret*a%M;
a=a*a%M;x>>=1; // 这里有可能爆long long
}
return ret;
}不带模版本根据带模版本更改就行
不要使用$O(\log x)$的“龟速乘”，除非发现可能被卡精度了，那玩意贼慢
long long qmul(unsigned long long x,unsigned long long y,ll m){
unsigned long long tmp=(x*y-(unsigned long long)((long double)x/m*y)*m);
return (tmp+m)%m;
}（如果非要用龟速乘，直接搬快速幂的板子就行）
typedef long long int ll;
const int M=998244353;
struct Mat{
int R,C;
vector< vector<ll> >mat;
Mat(int _R,int _C):R(_R),C(_C){
mat.resize(R,vector<ll>(C,0));
}
Mat(vector< vector<ll> >&_mat):mat(_mat),R(_mat.size()),C(_mat[0].size()){
}
const vector<ll> & operator [] (const int r) const {
return mat[r];
}
vector<ll> & operator [] (const int r) {
return mat[r];
}
Mat operator * (const Mat & mm) const {
Mat res=Mat(R,mm.C);
for(int r=0;r<R;++r){
for(int c=0;c<mm.C;++c){
for(int i=0;i<C;++i){
res[r][c]=(res[r][c]+mat[r][i]*mm[i][c]%M)%M;
}
}
}
return res;
}
static Mat eye(int N){
Mat res(N,N);
for(int i=0;i<N;++i) res[i][i]=1;
return res;
}
friend ostream & operator << (ostream & os,const Mat & mat){
os<<"{ siz:("<<mat.R<<","<<mat.C<<") , "<<"\n";
for(int r=0;r<mat.R;++r){
for(int c=0;c<mat.C;++c){
os<<mat[r][c]<<" ";
}
os<<"\n";
}
os<<"}\n";
return os;
}
};
Mat qpow(Mat a,ll x){
Mat res=Mat::eye(a.R);
if(x<=0) return res;
while(x){
if(x&1) res=res*a;
a=a*a;x>>=1;
}
return res;
}用于求$\sum\limits_{r=1}\limits^{n}f(r)\lfloor \frac{k}{r}\rfloor$
这里sumf(ll l,ll r)是用来求$\sum\limits_{i=l}\limits^{r}f(i)$的
typedef long long int ll;
ll sumf(ll l,ll r){
return (r-l+1)*(l+r)/2;
}
ll zcfk(ll n,ll k){
ll ans=0;
for(ll l=1,r;l<=n;l=r+1){
if(k/l!=0) r=min(k/(k/l),n);
else r=n;
ans+=(k/l)*sumf(l,r);
}
return ans;
}对所有的$0\le i\le 2^n-1$，快速求解$\sum\limits_{j\subset i}a_j$
// f为读入的数据
for(int j = 0; j < n; ++j){
for(int i = 0; i < 1 << n; ++i){
if((i >> j) & 1) f[i] += f[i ^ (1 << j)];
}
}也可以求解$\sum\limits_{i\subset j}a_j$
for(int j = 0; j < n; ++j){
for(int i = (1 << n)-1; i >= 0; --i){
if(((i >> j) & 1)==0) f[i] += f[i ^ (1 << j)];
}
}时间复杂度$O(n2^n)$，注意这两个前缀和都包括了自己
// n 方程个数，m 变量个数，a 是 n*(m+1) 的增广矩阵，free 是否为自由变量
// 返回自由变量个数，-1无解
const double EPS = 1e-8;
const int N = 2000 + 7;
double x[N];
bool free_x[N];
int sgn(double x) { return x < -EPS ? -1 : x > EPS; }
int gauss(vector<vector<double> >& a, int n, int m) {
fill(x, x + m + 1, 0);
fill(free_x, free_x + m + 1, true);
// 求上三角矩阵
int r = 0, c = 0;
while (r < n && c < m) {
int mr = r;
for (int i = r + 1; i < n; i++) {
if (abs(a[i][c]) > abs(a[mr][c])) mr = i;
}
if (mr != r) swap(a[r], a[mr]);
if (!sgn(a[r][c])) {
a[r][c] = 0;
++c;
continue;
}
for (int i = r + 1; i < n; i++) {
if (a[i][c]) {
double t = a[i][c] / a[r][c];
for (int j = c; j <= m; j++) a[i][j] -= a[r][j] * t;
}
}
++r, ++c;
}
for (int i = r; i < n; i++) {
if (sgn(a[i][m])) return -1;
}
// 求解 x0, x1, ..., xm-1
if (r < m) {
for (int i = r - 1; i >= 0; i--) {
int fcnt = 0, k = -1;
for (int j = 0; j < m; j++) {
if (sgn(a[i][j]) && free_x[j]) {
++fcnt;
k = j;
}
}
if (fcnt > 0) continue;
double s = a[i][m];
for (int j = 0; j < m; j++) {
if (j != k) s -= a[i][j] * x[j];
}
x[k] = s / a[i][k];
free_x[k] = 0;
}
return m - r;
}
for (int i = m - 1; i >= 0; i--) {
double s = a[i][m];
for (int j = i + 1; j < m; j++) s -= a[i][j] * x[j];
x[i] = s / a[i][i];
}
return 0;
}const int MAXN=1e8+10;
int mnf[MAXN];bool isprime[MAXN];
void init(){
memset(isprime,true,sizeof(isprime));
for(int i=1;i<MAXN;++i) mnf[i]=i;
isprime[0]=isprime[1]=false;
for(int i=2;i<MAXN;++i){
if(isprime[i]){
for(int j=i+i;j<MAXN;++j){
if(isprime[j]) isprime[j]=false,mnf[j]=i;
}
}
}
}时间复杂度$O(n\log\log n)$
// O(logn)
// 前置：快速乘、快速幂
// int范围只需检查2, 7, 61
bool isprime(ll n) {
if (n < 3) return n == 2;
if (!(n & 1)) return false;
ll d = n - 1, r = 0;
while (!(d & 1)) d >>= 1, r++;
static vector<ll> A = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
for (ll a : A) {
ll t = qpow(a, d, n);
if (t <= 1 || t == n - 1) continue;
for (int i = 0; i < r; i++) {
t = qmul(t, t, n);
if (t == 1) return false;
if (t == n - 1) break;
}
if (t != 1 && t != n - 1) return false;
}
return true;
}ll inv[N];
void initInv() {
inv[1]=1;
for (int i=2;i<N;i++) {
inv[i]=1LL*(MOD-MOD/i)*inv[MOD%i]%MOD;
}
}// a ^ x = b (mod p)，要求模数为素数
ll BSGS(ll a, ll b, ll p) {
a %= p;
if (!a && !b) return 1;
if (!a) return -1;
map<ll, ll> mp;
ll m = ceil(sqrt(p)), v = 1;
for (int i = 1; i <= m; i++) {
(v *= a) %= p;
mp[v * b % p] = i;
}
ll vv = v;
for (int i = 1; i <= m; i++) {
auto it = mp.find(vv);
if (it != mp.end()) return i * m - it->second;
(vv *= v) %= p;
}
return -1;
}
// 模数可以非素数
ll exBSGS(ll a, ll b, ll p) {
a %= p; b %= p;
if (a == 0) return b > 1 ? -1 : (b == 0 && p != 1);
ll c = 0, q = 1;
for (;;) {
ll g = gcd(a, p);
if (g == 1) break;
if (b == 1) return c;
if (b % g) return -1;
++c; b /= g; p /= g; q = a / g * q % p;
}
map<ll, ll> mp;
ll m = ceil(sqrt(p)), v = 1;
for (int i = 1; i <= m; i++) {
(v *= a) %= p;
mp[v * b % p] = i;
}
for (int i = 1; i <= m; i++) {
(q *= v) %= p;
auto it = mp.find(q);
if (it != mp.end()) return i * m - it->second + c;
}
return -1;
}
// 已知 x, b, p，求 a
ll SGSB(ll x, ll b, ll p) {
ll g = primitive_root(p);
return qk(g, BSGS(qk(g, x, p), b, p), p);
}const int MAXN=1e5+10;
struct USet{
vector<int>fa,siz;int sz;
void init(int _sz){
sz=_sz;
fa=siz=vector<int>(sz+10);
for(int i=1;i<=sz;++i){
fa[i]=i;sz[i]=1;
}
}
int findfa(int x){ return fa[x]==x?x:fa[x]=findfa(fa[x]);}
bool unio(int x,int y){ // 返回是否合并成功
int xx=findfa(x),yy=findfa(y);
if(xx==yy){
return false;
}else if(sz[xx]<sz[yy]){
swap(xx,yy);
}
fa[yy]=xx;sz[xx]+=sz[yy];
return true;
}
int size(int x){
return sz[findfa(x)];
}
}uset;// pa 为负数表示集合大小
unordered_map<int, int> pa;
void _set(int x) { if (!pa.count(x)) pa[x] = -1; }
int find(int x) { return (pa[x] < 0) ? x : pa[x] = find(pa[x]); }
void merge(int a, int b) {
int x = find(a), y = find(b);
if (x == y) return;
if (pa[x] > pa[y]) swap(x, y);
pa[x] += pa[y];
pa[y] = x;
}代码是NOI2001食物链的，题意是三种动物，A吃B、B吃C、C吃A，有n个动物，每个动物只属于一个种类，之后每次给“XY是同类”或者“X吃Y的断言”，如果一句话和之前的矛盾就是假的，否则就是真的
主要思想：将每个生物分成三个状态：自身、它吃的、被它吃的。在代码中i号动物：自身是i、吃i的是i+n、被i吃的是i+2*n，再用并查集维护三个关系就行
相当于只用按秩合并的并查集，单次操作时间复杂度是$O(\log n)$的
const int MAXN=5e4+10;
int n,k,ans,m,fa[MAXN*3],sz[MAXN*3];
void init(){
for(int i=1;i<MAXN*3;++i) {
fa[i]=i;sz[i]=1;
}
}
int findFa(int u){
return u==fa[u]?fa[u]:(fa[u]=findFa(fa[u]));
}
void unio(int x,int y){
int xx=findFa(x),yy=findFa(y);
if(xx==yy){
return;
}
if(sz[xx]<sz[yy]){
swap(xx,yy);
}
fa[yy]=xx;sz[xx]+=sz[yy];
}
bool work1(int a,int b){ // a,b同类
int at=findFa(a),bt=findFa(b);
int ae=findFa(a+2*n),be=findFa(b+2*n);
int ea=findFa(a+n),eb=findFa(b+n);
if(at==eb || at==be || ea==bt || ea==be || ae==bt || ae==eb){
return true;
}
unio(at,bt);unio(ae,be);unio(ea,eb);
return false;
}
bool work2(int a,int b){ // a吃b
int at=findFa(a),bt=findFa(b);
int ae=findFa(a+2*n),be=findFa(b+2*n);
int ea=findFa(a+n),eb=findFa(b+n);
if(at==bt || at==be || ea==bt || ea==eb || ae==eb || ae==be){
return true;
}
unio(at,eb);unio(bt,ae);unio(ea,be);
return false;
}work1和work2返回是不是假话
const int MAXN=1e5+10,MAXLOG=20;
struct ST{
static int lg2[MAXN],pow2[MAXN];
int n;int V[MAXN],st[MAXN][MAXLOG];
static void gen(){
lg2[1]=0;
for(int i=2;i<MAXN;++i){
lg2[i]=lg2[i>>1]+1;
}
pow2[0]=1;
for(int i=1;i<32;++i){
pow2[i]=pow2[i-1]<<1;
}
}
void init(){
for(int i=1;i<=n;++i){
st[i][0]=V[i];
}
for(int j=1;j<MAXLOG;++j){
for(int i=1;i+pow2[j]-1<=n;++i){
st[i][j]=max(st[i][j-1],st[i+pow2[j-1]][j-1]);
}
}
}
int query(int il,int ir){
int s=lg2[ir-il+1];
return max(st[il][s],st[ir-pow2[s]+1][s]);
}
}; // 不要开在栈里，另外如果只有一个ST表就不用写结构体了
// 在main里先ST::gen()，然后再对每个ST表.init()const int MAXN=5e4+10;
struct TreeArray{
int ta[MAXN],n;
static int lowbit(int x){
return x&(-x);
}
void build(){
for(int i=1,j;i<=n;++i){
j=i+lowbit(i);
if(j<=n){
ta[j]+=ta[i];
}
}
}
void add(int x,int p){
while(x<=n){
ta[x]+=p;x+=lowbit(x);
}
}
int _sum(int x){
int re=0;
while(x){
re+=ta[x];x-=lowbit(x);
}
return re;
}
int sum(int l,int r){
return _sum(r)-_sum(l-1);
}
};==记得init！==
typedef long long int ll;
const int MAXN=5e5+10;
struct TreeArray{
ll b[MAXN],bi[MAXN];int n;
void init(int _n,ll * a){ // 使用差分数组O(n)建树，注意需要memset
n=_n;
for(int i=1,j;i<=n;++i){
b[i]+=a[i];bi[i]+=a[i]*i;
j=i+lowbit(i);
if(j<=n){
b[j]+=b[i];bi[j]+=bi[i];
}
}
}
static int lowbit(int x){
return (x)&(-x);
}
void _add(int i,ll p){
int x=i;ll pp=p*i;
while(x<=n){
b[x]+=p;bi[x]+=pp;x+=lowbit(x);
}
}
void add(int l,int r,ll p){
_add(l,p);_add(r+1,-p);
}
ll _sum(ll * t,int r){
ll re=0;
while(r){
re+=t[r];r-=lowbit(r);
}
return re;
}
ll sum(int l,int r){
return ((r+1)*_sum(b,r)-l*_sum(b,l-1)) - (_sum(bi,r)-_sum(bi,l-1));
}
};一定记得建树时使用差分数组！
typedef long long int ll;
const int N=1e5+10;
struct TreeArray {
ll t[N][N];
static int lowbit(int x) { return x & (-x); }
void add(int x, int y, int d) {
for (int i = x; i <= n; i += lowbit(i))
for (int j = y; j <= m; j += lowbit(j)) t[i][j] += d;
}
ll get(int x, int y) {
ll sum = 0;
for (int i = x; i > 0; i -= lowbit(i))
for (int j = y; j > 0; j -= lowbit(j)) sum += t[i][j];
return sum;
}
ll query(int x, int y, int xx, int yy) {
return get(xx, yy) - get(x - 1, yy) - get(xx, y - 1) + get(x - 1, y - 1);
}
};
TreeArray t0, t1, t2, t3;
void add4(int x, int y, ll d) {
t0.add(x, y, d);
t1.add(x, y, d * x);
t2.add(x, y, d * y);
t3.add(x, y, d * x * y);
}
void range_add(int x, int y, int xx, int yy, ll d) {
add4(x, y, d);
add4(x, yy + 1, -d);
add4(xx + 1, y, -d);
add4(xx + 1, yy + 1, d);
}
ll get4(int x, int y) {
return (x + 1) * (y + 1) * t0.get(x, y)
- (y + 1) * t1.get(x, y)
- (x + 1) * t2.get(x, y)
+ t3.get(x, y);
}
ll range_sum(int x, int y, int xx, int yy) {
return get4(xx, yy) - get4(x - 1, yy) - get4(xx, y - 1) + get4(x - 1, y - 1);
}以动态开点为例，这里是支持两种操作的线段树：
- 区间加减，保证所有数字不会变成负数
- 询问区间中有多少个数为$0$
重点都在代码注释里，检查线段树的时候和重点对比，看是不是少了啥
const int MAXN=1e5+10,N=1e9; // 用N表示每次询问/操作的上界
struct Node{
int ls,rs,mn,mnct,tag;
}node[MAXN*50]; // 一般40倍空间就够了
#define ls(x) node[x].ls
#define rs(x) node[x].rs
#define mn(x) node[x].mn
#define mnct(x) node[x].mnct
#define len(x) node[x].len
#define tag(x) node[x].tag
int tot;
void newNode(int & p,int l,int r){
p=++tot;node[p]={0,0,0,r-l+1,0};
// 新建点的时候记得初始化（特别是多样例的时候）
}
void pushDown(int p,int l,int r){
// pushDown的时候：
// 1.要更新子结点的信息
// 2.把子结点的tag也更新了！
// 3.如果子结点此时不存在，新建子结点
// 4.清空本结点的tag
int mid=(l+r)>>1;
if(!ls(p)){
newNode(ls(p),l,mid);
mn(ls(p))=tag(p);tag(ls(p))=tag(p);mnct(ls(p))=mid-l+1;
}else{
mn(ls(p))+=tag(p);tag(ls(p))+=tag(p);
}
if(!rs(p)){
newNode(rs(p),mid+1,r);
mn(rs(p))=tag(p);tag(rs(p))=tag(p);mnct(rs(p))=r-mid;
}else{
mn(rs(p))+=tag(p);tag(rs(p))+=tag(p);
}
tag(p)=0;
}
void pushUp(int p,int l,int r){
// pushUp的时候：
// 1.由于在pushUp之前一定pushDown过（也就是新建了结点），所以不需要再考虑空结点
// 2.根据子结点的信息更新本结点的信息
if(mn(ls(p))<mn(rs(p))){
mn(p)=mn(ls(p));mnct(p)=mnct(ls(p));
}else if(mn(ls(p))>mn(rs(p))){
mn(p)=mn(rs(p));mnct(p)=mnct(rs(p));
}else{
mn(p)=mn(rs(p));mnct(p)=mnct(ls(p))+mnct(rs(p));
}
}
void add(int & p,int l,int r,int L,int R,int a){
// 操作的时候：
// 1.如果当前结点为空，新建结点（传入了引用，所以直接新建就行）
// 2.如果当前结点的范围在LR里，就更新tag和信息，再返回
// 3.如果不在，一定要先pushDown，再判断范围要不要处理子结点信息，再pushUp
if(!p) newNode(p,l,r);
if(L<=l && r<=R){
mn(p)+=a;tag(p)+=a;return;
}
pushDown(p,l,r);
int mid=(l+r)>>1;
if(mid>=L) add(ls(p),l,mid,L,R,a);
if(mid+1<=R) add(rs(p),mid+1,r,L,R,a);
pushUp(p,l,r);
}
int query(int & p,int l,int r,int L=0,int R=N){
// 询问的时候：
// 1.如果当前结点为空，考虑是不是可以直接返回某些信息
// 2.如果当前结点范围在LR里，就计算贡献，然后返回
// 3.如果不在，一定要先pushDown，在判断范围来获得子结点贡献。这时不用pushUp
if(!p) return r-l+1;
if(L<=l && r<=R){
if(mn(p)==0){
return mnct(p);
}else{
return 0;
}
}
pushDown(p,l,r);
int mid=(l+r)>>1,res=0;
if(mid>=L) res+=query(ls(p),l,mid,L,R);
if(mid+1<=R) res+=query(rs(p),mid+1,r,L,R);
return res;
}这里使用的例题：权值线段树，记录出现次数最多的数及其次数。做题的时候可以和板子对，不要照抄板子
注意，线段树合并复杂度的保证是：对于每次合并的两个序列，每个对应序列中的点对都满足：最多只有一个有值
const int MAXN=1e5+10,MAXLOG=25,N=100000;
struct Node{
int ls,rs,typ,mxc;
}node[MAXN*80];
#define ls(x) (node[x].ls)
#define rs(x) (node[x].rs)
#define typ(x) (node[x].typ)
#define mxc(x) (node[x].mxc)
int rt[MAXN],tot;
typedef pair<int,int>pii;
#define id first
#define ct second
void upd(pii & p,pii np){
if(p.ct<np.ct){
p=np;
}else if(p.ct==np.ct && p.id>np.id){
p=np;
}
}
pii query(int p,int l,int r,int ql,int qr){
if(ql<=l && r<=qr){
return pii(typ(p),mxc(p));
}
int mid=(l+r)>>1;pii res=pii(0,0);
if(mid>=ql && ls(p)) upd(res,query(ls(p),l,mid,ql,qr));
if(mid<qr && rs(p)) upd(res,query(rs(p),mid+1,r,ql,qr));
return res;
}
int newNode(int z=0){int p=++tot;mxc(p)=ls(p)=rs(p)=0;typ(p)=z;return p;}
int add(int p,int l,int r,int z,int d){
if(!p) p=newNode(z);
if(l==r) {mxc(p)+=d;return p;}
int mid=(l+r)>>1;
if(z<=mid) ls(p)=add(ls(p),l,mid,z,d);
if(z>mid) rs(p)=add(rs(p),mid+1,r,z,d);
if( mxc(rs(p))>mxc(ls(p)) ){
mxc(p)=mxc(rs(p));typ(p)=typ(rs(p));
}else{
mxc(p)=mxc(ls(p));typ(p)=typ(ls(p));
}
return p;
}
int merge(int r1,int r2,int l,int r){
if(!r1) return r2;
if(!r2) return r1;
if(l==r){
mxc(r1)+=mxc(r2);typ(r1)=l;return r1;
}
int mid=(l+r)>>1;
ls(r1)=merge(ls(r1),ls(r2),l,mid);
rs(r1)=merge(rs(r1),rs(r2),mid+1,r);
if( mxc( ls(r1) ) < mxc( rs(r1) ) ){
mxc(r1)=mxc(rs(r1));typ(r1)=typ( rs(r1) );
}else{
mxc(r1)=mxc(ls(r1));typ(r1)=typ( ls(r1) );
}
return r1;
}using namespace std;
const int N = 1e6 + 6;
char nc() {
static char buf[1000000], *p = buf, *q = buf;
return p == q && (q = (p = buf) + fread(buf, 1, 1000000, stdin), p == q)
? EOF
: *p++;
}
int rd() {
int res = 0;
char c = nc();
while (!isdigit(c)) c = nc();
while (isdigit(c)) res = res * 10 + c - '0', c = nc();
return res;
}
int t, n, m;
int a[N];
int mx[N << 2], se[N << 2], cn[N << 2], tag[N << 2];
long long sum[N << 2];
inline void pushup(int u) { // 向上更新标记
const int ls = u << 1, rs = u << 1 | 1;
sum[u] = sum[ls] + sum[rs];
if (mx[ls] == mx[rs]) {
mx[u] = mx[rs];
se[u] = max(se[ls], se[rs]);
cn[u] = cn[ls] + cn[rs];
} else if (mx[ls] > mx[rs]) {
mx[u] = mx[ls];
se[u] = max(se[ls], mx[rs]);
cn[u] = cn[ls];
} else {
mx[u] = mx[rs];
se[u] = max(mx[ls], se[rs]);
cn[u] = cn[rs];
}
}
inline void pushtag(int u, int tg) { // 单纯地打标记，不暴搜
if (mx[u] <= tg) return;
sum[u] += (1ll * tg - mx[u]) * cn[u];
mx[u] = tag[u] = tg;
}
inline void pushdown(int u) { //下传标记
if (tag[u] == -1) return;
pushtag(u << 1, tag[u]), pushtag(u << 1 | 1, tag[u]);
tag[u] = -1;
}
void build(int u = 1, int l = 1, int r = n) { //建树
tag[u] = -1;
if (l == r) {
sum[u] = mx[u] = a[l], se[u] = -1, cn[u] = 1;
return;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void modify_min(int L, int R, int v, int u = 1, int l = 1, int r = n) {
if (mx[u] <= v) return;
if (L <= l && r <= R && se[u] < v) return pushtag(u, v);
int mid = (l + r) >> 1;
pushdown(u);
if (L <= mid) modify_min(L, R, v, u << 1, l, mid);
if (mid < R) modify_min(L, R, v, u << 1 | 1, mid + 1, r);
pushup(u);
}
int query_max(int L, int R, int u = 1, int l = 1, int r = n) { //查询最值
if (L <= l && r <= R) return mx[u];
int mid = (l + r) >> 1, r1 = -1, r2 = -1;
pushdown(u);
if (L <= mid) r1 = query_max(L, R, u << 1, l, mid);
if (mid < R) r2 = query_max(L, R, u << 1 | 1, mid + 1, r);
return max(r1, r2);
}
long long query_sum(int L, int R, int u = 1, int l = 1, int r = n) { //数值
if (L <= l && r <= R) return sum[u];
int mid = (l + r) >> 1;
long long res = 0;
pushdown(u);
if (L <= mid) res += query_sum(L, R, u << 1, l, mid);
if (mid < R) res += query_sum(L, R, u << 1 | 1, mid + 1, r);
return res;
}
void go() { //根据题意
n = rd(), m = rd();
for (int i = 1; i <= n; i++) a[i] = rd();
build();
for (int i = 1; i <= m; i++) {
int op, x, y, z;
op = rd(), x = rd(), y = rd();
if (op == 0)
z = rd(), modify_min(x, y, z);
else if (op == 1)
printf("%d\n", query_max(x, y));
else
printf("%lld\n", query_sum(x, y));
}
}
signed main() {
t = rd();
while (t--) go();
return 0;
}#include <cstdio>
#include <iostream>
using namespace std;
int inline rd() {
register char act = 0;
register int f = 1, x = 0;
while (act = getchar(), act < '0' && act != '-')
;
if (act == '-') f = -1, act = getchar();
x = act - '0';
while (act = getchar(), act >= '0') x = x * 10 + act - '0';
return x * f;
}
const int N = 5e5 + 5, SZ = N << 2, INF = 0x7fffffff;
int n, m;
int a[N];
struct data {
int mx, mx2, mn, mn2, cmx, cmn, tmx, tmn, tad;
long long sum;
} t[SZ];
void pushup(int u) {
const int lu = u << 1, ru = u << 1 | 1;
t[u].sum = t[lu].sum + t[ru].sum;
if (t[lu].mx == t[ru].mx) {
t[u].mx = t[lu].mx, t[u].cmx = t[lu].cmx + t[ru].cmx;
t[u].mx2 = max(t[lu].mx2, t[ru].mx2);
} else if (t[lu].mx > t[ru].mx) {
t[u].mx = t[lu].mx, t[u].cmx = t[lu].cmx;
t[u].mx2 = max(t[lu].mx2, t[ru].mx);
} else {
t[u].mx = t[ru].mx, t[u].cmx = t[ru].cmx;
t[u].mx2 = max(t[lu].mx, t[ru].mx2);
}
if (t[lu].mn == t[ru].mn) {
t[u].mn = t[lu].mn, t[u].cmn = t[lu].cmn + t[ru].cmn;
t[u].mn2 = min(t[lu].mn2, t[ru].mn2);
} else if (t[lu].mn < t[ru].mn) {
t[u].mn = t[lu].mn, t[u].cmn = t[lu].cmn;
t[u].mn2 = min(t[lu].mn2, t[ru].mn);
} else {
t[u].mn = t[ru].mn, t[u].cmn = t[ru].cmn;
t[u].mn2 = min(t[lu].mn, t[ru].mn2);
}
}
void push_add(int u, int l, int r, int v) {
// 更新加法标记的同时，更新 $\min$ 和 $\max$ 标记
t[u].sum += (r - l + 1ll) * v;
t[u].mx += v, t[u].mn += v;
if (t[u].mx2 != -INF) t[u].mx2 += v;
if (t[u].mn2 != INF) t[u].mn2 += v;
if (t[u].tmx != -INF) t[u].tmx += v;
if (t[u].tmn != INF) t[u].tmn += v;
t[u].tad += v;
}
void push_min(int u, int tg) {
// 注意比较 $\max$ 标记
if (t[u].mx <= tg) return;
t[u].sum += (tg * 1ll - t[u].mx) * t[u].cmx;
if (t[u].mn2 == t[u].mx) t[u].mn2 = tg; // !!!
if (t[u].mn == t[u].mx) t[u].mn = tg; // !!!!!
if (t[u].tmx > tg) t[u].tmx = tg; // 更新取 $\max$ 标记
t[u].mx = tg, t[u].tmn = tg;
}
void push_max(int u, int tg) {
if (t[u].mn > tg) return;
t[u].sum += (tg * 1ll - t[u].mn) * t[u].cmn;
if (t[u].mx2 == t[u].mn) t[u].mx2 = tg;
if (t[u].mx == t[u].mn) t[u].mx = tg;
if (t[u].tmn < tg) t[u].tmn = tg;
t[u].mn = tg, t[u].tmx = tg;
}
void pushdown(int u, int l, int r) {
const int lu = u << 1, ru = u << 1 | 1, mid = (l + r) >> 1;
if (t[u].tad)
push_add(lu, l, mid, t[u].tad), push_add(ru, mid + 1, r, t[u].tad);
if (t[u].tmx != -INF) push_max(lu, t[u].tmx), push_max(ru, t[u].tmx);
if (t[u].tmn != INF) push_min(lu, t[u].tmn), push_min(ru, t[u].tmn);
t[u].tad = 0, t[u].tmx = -INF, t[u].tmn = INF;
}
void build(int u = 1, int l = 1, int r = n) {
t[u].tmn = INF, t[u].tmx = -INF; // 取极限
if (l == r) {
t[u].sum = t[u].mx = t[u].mn = a[l];
t[u].mx2 = -INF, t[u].mn2 = INF;
t[u].cmx = t[u].cmn = 1;
return;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void add(int L, int R, int v, int u = 1, int l = 1, int r = n) {
if (R < l || r < L) return;
if (L <= l && r <= R) return push_add(u, l, r, v); // !!! 忘 return
int mid = (l + r) >> 1;
pushdown(u, l, r);
add(L, R, v, u << 1, l, mid), add(L, R, v, u << 1 | 1, mid + 1, r);
pushup(u);
}
void tomin(int L, int R, int v, int u = 1, int l = 1, int r = n) {
if (R < l || r < L || t[u].mx <= v) return;
if (L <= l && r <= R && t[u].mx2 < v) return push_min(u, v); // BUG: 忘了返回
int mid = (l + r) >> 1;
pushdown(u, l, r);
tomin(L, R, v, u << 1, l, mid), tomin(L, R, v, u << 1 | 1, mid + 1, r);
pushup(u);
}
void tomax(int L, int R, int v, int u = 1, int l = 1, int r = n) {
if (R < l || r < L || t[u].mn >= v) return;
if (L <= l && r <= R && t[u].mn2 > v) return push_max(u, v);
int mid = (l + r) >> 1;
pushdown(u, l, r);
tomax(L, R, v, u << 1, l, mid), tomax(L, R, v, u << 1 | 1, mid + 1, r);
pushup(u);
}
long long qsum(int L, int R, int u = 1, int l = 1, int r = n) {
if (R < l || r < L) return 0;
if (L <= l && r <= R) return t[u].sum;
int mid = (l + r) >> 1;
pushdown(u, l, r);
return qsum(L, R, u << 1, l, mid) + qsum(L, R, u << 1 | 1, mid + 1, r);
}
long long qmax(int L, int R, int u = 1, int l = 1, int r = n) {
if (R < l || r < L) return -INF;
if (L <= l && r <= R) return t[u].mx;
int mid = (l + r) >> 1;
pushdown(u, l, r);
return max(qmax(L, R, u << 1, l, mid), qmax(L, R, u << 1 | 1, mid + 1, r));
}
long long qmin(int L, int R, int u = 1, int l = 1, int r = n) {
if (R < l || r < L) return INF;
if (L <= l && r <= R) return t[u].mn;
int mid = (l + r) >> 1;
pushdown(u, l, r);
return min(qmin(L, R, u << 1, l, mid), qmin(L, R, u << 1 | 1, mid + 1, r));
}
int main() {
n = rd();
for (int i = 1; i <= n; i++) a[i] = rd();
build();
m = rd();
for (int i = 1; i <= m; i++) {
int op, l, r, x;
op = rd(), l = rd(), r = rd();
if (op <= 3) x = rd(); // scanf("%d",&x);
if (op == 1)
add(l, r, x); // 区间加
else if (op == 2)
tomax(l, r, x); // a[i]=max(a[i],x)
else if (op == 3)
tomin(l, r, x); // a[i]=min(a[i],x);
else if (op == 4)
printf("%lld\n", qsum(l, r)); // 求和
else if (op == 5)
printf("%lld\n", qmax(l, r)); // 求最大值
else
printf("%lld\n", qmin(l, r)); // 求最小值
}
return 0;
}const int MAXN=1e5+10;
struct PNode{
int ls,rs,val;
}node[MAXN<<5];
#define ls(p) (node[p].ls)
#define rs(p) (node[p].rs)
#define val(p) (node[p].val)
int rt[MAXN],tot;
int newNode(int cpy=0){
int u=++tot;
memcpy(node+u,node+cpy,sizeof(PNode));
return u;
}
int build(int l,int r){
int u=newNode();
if(l==r){
return u;
}
int mid=(l+r)>>1;
ls(u)=build(l,mid);rs(u)=build(mid+1,r);
return u;
}
int add(int l,int r,int v,int rtp){
int u=newNode(rtp);++val(u);
if(l==r){
return u;
}
int mid=(l+r)>>1;
if(v<=mid){
ls(u)=add(l,mid,v,ls(rtp));
}else{
rs(u)=add(mid+1,r,v,rs(rtp));
}
return u;
}
int query(int rtl,int rtr,int l,int r,int k){
if(l==r){
return l;
}
int mid=(l+r)>>1;
if(val(ls(rtr))-val(ls(rtl))>=k){
return query(ls(rtl),ls(rtr),l,mid,k);
}else{
return query(rs(rtl),rs(rtr),mid+1,r, k-(val(ls(rtr))-val(ls(rtl))) );
}
}- 如果
RE，先想想是不是结点数不够 - 如果有一个操作需要两次
add，第一次用add(rt[i],rt[i-1])，第二次就要用add(rt[i],rt[i])了（注意这样的话，时间线的长度是一般的两倍）
const int MAXN=5e5+10,MAXLOG=25;
int lg2[MAXN],fa[MAXN][MAXLOG],dep[MAXN],n,m;
vector<int>G[MAXN];
void init(){
lg2[1]=0;
for(int i=2;i<MAXN;++i)
lg2[i]=lg2[i>>1]+1;
}
void dfs(int u,int fu){
dep[u]=dep[fu]+1;fa[u][0]=fu;
for(int i=1;i<MAXLOG;++i)
fa[u][i]=fa[ fa[u][i-1] ][i-1];
for(int v:G[u])
if(v!=fu)
dfs(v,u);
}
int lca(int x,int y){
if(dep[x]<dep[y])
swap(x,y);
while(dep[x]>dep[y])
x=fa[x][ lg2[dep[x]-dep[y]] ];
if(x==y)
return x;
for(int k=lg2[dep[x]];k>=0;--k)
if(fa[x][k]!=fa[y][k])
x=fa[x][k],y=fa[y][k];
return fa[x][0];
}lg2[x]表示$\lfloor\log _2 x\rfloor$，也可以表示x二进制表达的位数数量减一（或从0开始计数的最高位位数）；fa[x][k]表示x的向上跳$2^k$次所在结点；lca的最后过程相当于模拟二进制过
树上启发式合并
int dfn[MAXN],rnk[MAXN],dfed[MAXN],n,big[MAXN],siz[MAXN],c[MAXN];
// dfn,dfed,rnk分别为：dfs序，子树dfs序最大，某个dfs序对应结点
// big,siz,c分别为：重儿子编号、子树大小、信息
ll ans[MAXN];
struct Mem{
int cnt[MAXN];ll ss; // 保存的信息
void add(int u){...} // 如果复杂度为O(K)，则总复杂度O(nKlogn)
void clear(int dfnl,int dfnr){...}
// 清除dfs序在[dfnl,dfnr]之间的所有点的数据
// dsu on tree里面，当清除数据的时候一定都是整个子树的数据一起清除，所以直接用dfs序做就行
}mem;
void dfs0(int u,int fu){
dfn[u]=++dfn[0];rnk[dfn[u]]=u;siz[u]=1; // 这里别写错
for(int v:G[u]){
if(v!=fu){
dfs0(v,u);siz[u]+=siz[v];
if(siz[v]>siz[big[u]]) big[u]=v;
}
}
dfed[u]=dfn[0];
}
void dfs1(int u,int fu,bool kp){
for(int v:G[u])
if(v!=fu && v!=big[u]) dfs1(v,u,false); // 处理轻儿子的答案，并且不保留贡献
if(big[u])
dfs1(big[u],u,true); // 处理重儿子的答案
for(int v:G[u])
if(v!=fu && v!=big[u])
for(int i=dfn[v];i<=dfed[v];++i)
mem.add(rnk[i]); // 轻儿子子树上的数据全都加上
mem.add(u); // 自身的数据算上
ans[u]=mem.ss; // 统计答案
if(!kp) // 如果不需要保持mem，就清空
mem.clear(dfn[u],dfed[u]);
}树上启发式合并在dfs过程中需要使用子树的信息，其主要包括几个过程：
- 分别计算轻儿子子树的答案，但是不保留子树上的信息
- 计算重儿子子树的答案，同时保留其子树的信息、计算贡献
- 使用
dfn和dfed将所有轻儿子子树的信息合并，同时计算贡献 - 最后根据
kp判断是否保留u子树的信息，如果不保留，就使用dfn全部清除
dsu on tree的时间复杂度和启发式分治的原理一样
这个是处理两点路径上点权加和两点路径点权和的
const int MAXN=1e5+10;
int fa[MAXN],dep[MAXN],siz[MAXN],big[MAXN],n,rt;
int dfn[MAXN],dfed[MAXN],top[MAXN],rnk[MAXN];
vector<int>G[MAXN];
void addE(int u,int v){G[u].push_back(v);G[v].push_back(u);}
void dfs1(int u,int fu){
fa[u]=fu;dep[u]=dep[fu]+1;siz[u]=1;big[u]=0;
for(int v:G[u])
if(v!=fu){
dfs1(v,u);siz[u]+=siz[v];
if(siz[v]>siz[big[u]])
big[u]=v;
}
}
void dfs2(int u,int tp){
dfn[u]=++dfn[0];rnk[dfn[0]]=u;top[u]=tp;
if(big[u]) dfs2(big[u],tp);
for(int v:G[u])
if(v!=fa[u] && v!=big[u])
dfs2(v,v);
dfed[u]=dfn[0];
}
typedef long long int ll;
struct Node{
ll sum,tag;
}node[MAXN*40]; // 一般都是有初始权的，所以使用一般的线段树就行
#define ls(p) ((p)<<1)
#define rs(p) (ls(p)|1)
#define sum(p) (node[p].sum)
#define tag(p) (node[p].tag)
int N;ll val[MAXN],M; // N:操作最大值，一般=n；M:模数
void pushDown(int p,int l,int r){
int mid=(l+r)>>1;
tag(ls(p))=(tag(ls(p))+tag(p))%M;
tag(rs(p))=(tag(rs(p))+tag(p))%M;
sum(ls(p))=(sum(ls(p))+tag(p)*(mid-l+1))%M;
sum(rs(p))=(sum(rs(p))+tag(p)*(r-mid))%M;
tag(p)=0;
}
void build(int p,int l,int r){
if(l==r){
sum(p)=val[rnk[l]];return;
}
int mid=(l+r)>>1;
build(ls(p),l,mid);build(rs(p),mid+1,r);
sum(p)=(sum(ls(p))+sum(rs(p)))%M;
}
void add(int p,int l,int r,int L,int R,ll a){
if(L<=l && r<=R){
sum(p)=(sum(p)+a*(r-l+1))%M;tag(p)=(tag(p)+a)%M;return;
}
pushDown(p,l,r);
int mid=(l+r)>>1;
if(mid>=L) add(ls(p),l,mid,L,R,a);
if(mid+1<=R) add(rs(p),mid+1,r,L,R,a);
sum(p)=(sum(ls(p))+sum(rs(p)))%M;
}
ll query(int p,int l,int r,int L,int R){
if(L<=l && r<=R)
return sum(p);
pushDown(p,l,r);
int mid=(l+r)>>1;ll ss=0;
if(mid>=L) ss=(ss+query(ls(p),l,mid,L,R))%M;
if(mid+1<=R) ss=(ss+query(rs(p),mid+1,r,L,R))%M;
return ss;
}
void work1(int x,int y,ll a){ // 将x,y路径上的点点权+a
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]]){
add(1,1,N,dfn[top[x]],dfn[x],a);
x=fa[top[x]];
}else{
add(1,1,N,dfn[top[y]],dfn[y],a);
y=fa[top[y]];
}
}
if(dep[x]>dep[y]){
add(1,1,N,dfn[y],dfn[x],a);
}else{
add(1,1,N,dfn[x],dfn[y],a);
}
}
ll work2(int x,int y){ // 查询x,y路径上的点权和
ll ss=0;
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]]){
ss=(ss+query(1,1,N,dfn[top[x]],dfn[x]))%M;
x=fa[top[x]];
}else{
ss=(ss+query(1,1,N,dfn[top[y]],dfn[y]))%M;
y=fa[top[y]];
}
}
if(dep[x]>dep[y]){
ss=(ss+query(1,1,N,dfn[y],dfn[x]))%M;
}else{
ss=(ss+query(1,1,N,dfn[x],dfn[y]))%M;
}
return ss;
}
int main() {
// 读入等
dfs1(rt,0);
dfs2(rt,rt);
build(1,1,N);
// 处理询问
}树剖主要运用的性质是：重链上的点的dfn是连续的，且一个点向根部跳最多跳log级的链
记得：
- dfs两次
- 设置
N=n！ build线段树
这里的01-trie是用来处理XOR-MST的
根结点编号为0
const int MAXN=2e5*100,MAXB=30,MXI=0x7fffffff;
int pw2[MAXB+1];
typedef long long int ll;
struct ZOTrie{
int tot,tr[MAXN][2],bit[MAXN]; // bit[x]表示x结点往儿子走的时候其表示的位数
static void gen(){
pw2[0]=1;
for(int i=1;i<=MAXB;++i)
pw2[i]=pw2[i-1]*2;
}
void init(){
tot=0;memset(tr,0,sizeof(tr));memset(bit,0,sizeof(bit));bit[0]=30;
}
void insert(int x){
int cur=0;
for(int i=MAXB,b;i>=0;--i){
b=(x>>i)&1;
if(!tr[cur][b]) {
tr[cur][b]=++tot;bit[tot]=bit[cur]-1;
}
cur=tr[cur][b];
}
}
int find(int rt1,int rt2){
// 从rt1和rt2中分别选择两个数，要求其异或值最小，返回其值
int va1=-1,va2=-1;
if(tr[rt1][0] && tr[rt2][0]) va1=find(tr[rt1][0],tr[rt2][0]);
if(tr[rt1][1] && tr[rt2][1]) va2=find(tr[rt1][1],tr[rt2][1]);
if(va1!=-1 && va2!=-1) return min(va1,va2);
if(va1!=-1) return va1;if(va2!=-1) return va2;
if(tr[rt1][0] && tr[rt2][1]) va1=find(tr[rt1][0],tr[rt2][1])+pw2[bit[rt1]];
if(tr[rt1][1] && tr[rt2][0]) va2=find(tr[rt1][1],tr[rt2][0])+pw2[bit[rt1]];
if(va1!=-1 && va2!=-1) return min(va1,va2);
if(va1!=-1) return va1;if(va2!=-1) return va2;
return 0;
}
ll dfs(int u){
ll an=0;
if(tr[u][0] && tr[u][1]) an+=1ll*find(tr[u][0],tr[u][1])+pw2[bit[u]];
if(tr[u][0]) an+=dfs(tr[u][0]);
if(tr[u][1]) an+=dfs(tr[u][1]);
return an;
}
}trie;
// in main
ZOTrie::gen();
trie.init();
int n;cin>>n;
for(int i=1,x;i<=n;++i) cin>>x,trie.insert(x);
cout<<trie.dfs(0)<<'\n';如果要重构XOR-MST，则需要两个find函数，一个是原始函数，另一个用来找哪些点需要被连边
const int MAXN=1e5+10;
struct Treap{ // multiset
struct BNode{
int ls,rs,key,ct,pr,siz;
}node[MAXN];
#define ls(p) (node[p].ls)
#define rs(p) (node[p].rs)
#define key(p) (node[p].key)
#define ct(p) (node[p].ct)
#define pr(p) (node[p].pr) // 保证堆的性质：父亲借点的pr小于两个儿子的
#define siz(p) (node[p].siz) // siz是包括重复元素的，比如{1,2,2}的siz=3
int tot,rt;
void newNode(int & p,int key){
p=++tot;node[p]={0,0,key,1,rand(),1};
}
void lrotate(int & p){
int t=rs(p);
rs(p)=ls(t);
ls(t)=p;
siz(t)=siz(p);
siz(p)=siz(ls(p))+siz(rs(p))+ct(p);
p=t;
}
void rrotate(int & p){
int t=ls(p);
ls(p)=rs(t);
rs(t)=p;
siz(t)=siz(p);
siz(p)=siz(ls(p))+siz(rs(p))+ct(p);
p=t;
}
void insert(int & p,int key){
if(!p) { newNode(p,key);return;}
++siz(p);
if(key(p)==key){
++ct(p);
}else if(key(p)<key){
insert(rs(p),key);
if(pr(rs(p))<pr(p)) lrotate(p);
}else if(key(p)>key){
insert(ls(p),key);
if(pr(ls(p))<pr(p)) rrotate(p);
}
}
bool sub(int & p,int key){ // 删除一个key
if(!p) return false;
if(key(p)==key){
if(ct(p)>1) {
--ct(p);--siz(p);return true;
}
if(!ls(p) || !rs(p)){
p=ls(p)+rs(p);return true;
}else if(pr(ls(p))<pr(rs(p))){
rrotate(p);
return sub(p,key);
}else{
lrotate(p);
return sub(p,key);
}
}else if(key(p)<key){
bool suc=sub(rs(p),key);
if(suc) --siz(p);
return suc;
}else if(key(p)>key){
bool suc=sub(ls(p),key);
if(suc) --siz(p);
return suc;
}
return false;
}
int del(int & p,int key){ // 删除满足key(p)=key的结点p的值
if(!p) return 0;
if(key(p)==key){
if(!ls(p) || !rs(p)){
p=ls(p)+rs(p);return ct(p);
}else if(pr(ls(p))<pr(rs(p))){
rrotate(p);
return del(p,key);
}else{
lrotate(p);
return del(p,key);
}
}else if(key(p)<key){
int suc=del(rs(p),key);
siz(p)-=suc;
return suc;
}else if(key(p)>key){
int suc=del(ls(p),key);
siz(p)-=suc;
return suc;
}
return 0;
}
int queryRank(int p,int key){ // multiset，第一个key元素的排名，没有就返回0
if(!p) return 0;
if(key(p)==key){
return siz(ls(p))+1;
}else if(key(p)<key){
return siz(ls(p))+ct(p)+queryRank(rs(p),key);
}else{
return queryRank(ls(p),key);
}
}
int queryEle(int p,int rk){ // 返回排名为rk的元素，没有就返回0
if(!p) return 0;
if(rk<=siz(ls(p))){
return queryEle(ls(p),rk);
}else if(rk>siz(ls(p))+ct(p)){
return queryEle(rs(p),rk-siz(ls(p))-ct(p));
}else{
return key(p);
}
}
int ans;
void _queryPre(int p,int key){
if(!p) return;
if(key(p)<key){
ans=p;_queryPre(rs(p),key);
}else{
_queryPre(ls(p),key);
}
}
int queryPre(int key){ // 查询小于key的最大的数 0表示不存在
ans=0;
_queryPre(rt,key);
return key(ans);
}
void _queryNxt(int p,int key){
if(!p) return;
if(key(p)>key){
ans=p;_queryNxt(ls(p),key);
}else{
_queryNxt(rs(p),key);
}
}
int queryNxt(int key){ // 查询大于key的最小的数 0表示不存在
ans=0;
_queryNxt(rt,key);
return key(ans);
}
};const int MAXN=1e5+10;
struct Treap{ // set
struct BNode{
int ls,rs,key,ct,pr,siz;
}node[MAXN];
#define ls(p) (node[p].ls)
#define rs(p) (node[p].rs)
#define key(p) (node[p].key)
#define ct(p) (node[p].ct)
#define pr(p) (node[p].pr) // 保证堆的性质：父亲借点的pr小于两个儿子的
#define siz(p) (node[p].siz) // siz是包括重复元素的，比如{1,2,2}的siz=3
int tot,rt;
void newNode(int & p,int key){
p=++tot;node[p]={0,0,key,1,rand(),1};
}
void lrotate(int & p){
int t=rs(p);
rs(p)=ls(t);
ls(t)=p;
siz(t)=siz(p);
siz(p)=siz(ls(p))+siz(rs(p))+1;
p=t;
}
void rrotate(int & p){
int t=ls(p);
ls(p)=rs(t);
rs(t)=p;
siz(t)=siz(p);
siz(p)=siz(ls(p))+siz(rs(p))+1;
p=t;
}
bool insert(int & p,ull key){
if(!p) { newNode(p,key);return true;}
bool suc=false;
if(key(p)<key){
suc=insert(rs(p),key);siz(p)+=suc;
if(pr(rs(p))<pr(p)) lrotate(p);
}else if(key(p)>key){
suc=insert(ls(p),key);siz(p)+=suc;
if(pr(ls(p))<pr(p)) rrotate(p);
}else if(key(p)==key){
suc=false;
}
return suc;
}
bool del(int & p,ull key){ // 删除满足key(p)=key的结点p
if(!p) return false;
bool suc=false;
if(key(p)==key){
if(!ls(p) || !rs(p)){
p=ls(p)+rs(p);return true;
}else if(pr(ls(p))<pr(rs(p))){
rrotate(p);
return del(p,key);
}else{
lrotate(p);
return del(p,key);
}
}else if(key(p)<key){
suc=del(rs(p),key);
siz(p)-=suc;
}else if(key(p)>key){
suc=del(ls(p),key);
siz(p)-=suc;
}
return suc;
}
int queryRank(int p,int key){ // set，key元素的排名
if(!p) return 0;
if(key(p)==key){
return siz(ls(p))+1;
}else if(key(p)<key){
return siz(ls(p))+1+queryRank(rs(p),key);
}else{
return queryRank(ls(p),key);
}
}
int queryEle(int p,int rk){ // 返回排名为rk的元素
if(!p) return 0;
if(rk<=siz(ls(p))){
return queryEle(ls(p),rk);
}else if(rk>siz(ls(p))+1){
return queryEle(rs(p),rk-siz(ls(p))-1);
}else{
return key(p);
}
}
int ans;
void _queryPre(int p,int key){
if(!p) return;
if(key(p)<key){
ans=p;_queryPre(rs(p),key);
}else{
_queryPre(ls(p),key);
}
}
int queryPre(int key){ // 查询小于key的最大的数 0表示不存在
ans=0;
_queryPre(rt,key);
return key(ans);
}
void _queryNxt(int p,int key){
if(!p) return;
if(key(p)>key){
ans=p;_queryNxt(ls(p),key);
}else{
_queryNxt(rs(p),key);
}
}
int queryNxt(int key){ // 查询大于key的最小的数 0表示不存在
ans=0;
_queryNxt(rt,key);
return key(ans);
}
};typedef long long int ll;
const int MAXN=1e5+10;
struct Splay{ // multiset
// 查询到空的时候，也需要splay！不然复杂度就假了！
int tot,rt;
int chl[MAXN][2],fa[MAXN],siz[MAXN],ct[MAXN];
ll key[MAXN],sum[MAXN];
int newNode(ll ke){
// 返回一个新 孤立 的结点，其key就是ke，注意在新连了边之后需要重新pushUp
++tot;chl[tot][0]=chl[tot][1]=fa[tot]=0;
key[tot]=sum[tot]=ke;siz[tot]=ct[tot]=1;
return tot;
}
void pushUp(int p){ // p和其两个儿子已经确定，需要更新p的siz和sum
// pushUp(0)没用
siz[p]=siz[chl[p][0]]+siz[chl[p][1]]+ct[p];
sum[p]=sum[chl[p][0]]+sum[chl[p][1]]+ct[p]*key[p];
}
int get(int p) { // 获得p的儿子类型
return p==chl[fa[p]][1];
}
void rotate(int x) { // 将x旋转，注意这时候一定有fa[x]!=0
int y=fa[x],z=fa[y],chk=get(x);
chl[y][chk]=chl[x][chk^1];
if(chl[x][chk^1]) fa[chl[x][chk^1]]=y;
chl[x][chk^1]=y;
fa[y]=x;
if(z) chl[z][y==chl[z][1]]=x;
fa[x]=z;
pushUp(y);pushUp(x);
}
void splay(int x){
// 保证x和fa[x]必须已经pushUp过，再往上会自动pushUp
// splay(0)理论上不会出问题。。。
for(int f=fa[x];(f=fa[x]);rotate(x))
if(fa[f]) rotate(get(x)==get(f)?f:x);
rt=x;
}
void insert(ll ke){
if(!rt){
rt=newNode(ke);return;
}
int cur=rt,f=0;
while(true){
if(key[cur]==ke){
++ct[cur];pushUp(cur);pushUp(f);splay(cur);
break;
}
f=cur;cur=chl[cur][key[cur]<ke];
if(!cur){
int nn=newNode(ke);
fa[nn]=f;chl[f][key[f]<ke]=nn;pushUp(f);
splay(nn);break;
}
}
}
int queryRank(ll ke){ // 查询ke的排名，如果不存在这个数返回0
int rk=0,cur=rt,f=0;
while(cur){
if(ke<key[cur]){
f=cur;cur=chl[cur][0];
}else if(ke>key[cur]){
rk+=siz[chl[cur][0]]+ct[cur];
f=cur;cur=chl[cur][1];
}else{
rk+=1+siz[chl[cur][0]];break;
}
}
if(cur){
splay(cur);return rk;
}else{ // 即使没有找到也要splay！
splay(f);return 0;
}
}
ll queryEle(int rk){
if(rk>siz[rt]) return 0; // 超过范围直接return 0，防止被超过siz的询问卡
int cur=rt;
while(true){
if(rk<=siz[chl[cur][0]]){
cur=chl[cur][0];
}else{
rk-=ct[cur]+siz[chl[cur][0]];
if(rk<=0) break;
cur=chl[cur][1];
}
}
splay(cur);return key[cur];
}
int _pre(){ // 访问根左儿子子树的最右，并且转动到根
int cur=chl[rt][0]; // cur=0不会造成影响
while(chl[cur][1]) cur=chl[cur][1];
splay(cur);return cur;
}
int _nxt(){ // 访问根右儿子子树的最左，并且转动到根
int cur=chl[rt][1];
while(chl[cur][0]) cur=chl[cur][0];
splay(cur);return cur;
}
bool sub(ll ke){ // 删除一个key对应的值
if(!queryRank(ke)) return false;
if(ct[rt]>1){
--ct[rt];pushUp(rt);
}else if(!chl[rt][0] && !chl[rt][1]){
rt=0;
}else if(!chl[rt][0]){
rt=chl[rt][1];
fa[rt]=0;
}else if(!chl[rt][1]){
rt=chl[rt][0];
fa[rt]=0;
}else{
int cur=rt,x=_pre();
// 查pre的时候，不会影响到rt的右儿子
// 根据pre和双旋的性质，splay(x)之后，cur没有左儿子
// x实际上就是新的rt
fa[chl[cur][1]]=x;
chl[x][1]=chl[cur][1];
pushUp(x);
}
return true;
}
ll queryPre(ll ke){ // 查询小于ke的最大的数，0表示不存在
int cur=rt,f=0,ret=0;
while(cur){
if(key[cur]>=ke){
f=cur;cur=chl[cur][0];
}else{
ret=cur;
f=cur;cur=chl[cur][1];
}
}
splay(f);
return ret==0?0:key[ret];
}
ll queryNxt(ll ke){
int cur=rt,f=0,ret=0;
while(cur){
if(key[cur]<=ke){
f=cur;cur=chl[cur][1];
}else{
ret=cur;
f=cur;cur=chl[cur][0];
}
}
splay(f);
return ret==0?0:key[ret];
}
}T;typedef long long int ll;
const int MAXN=1e5+10;
struct SplayArray{ // splay数组
// 查询到空的时候，也需要splay！不然复杂度就假了！
int tot,rt;
int chl[MAXN][2],fa[MAXN],siz[MAXN];
ll val[MAXN],sum[MAXN];
bool tag[MAXN]; // 旋转tag
int newNode(ll va){
// 返回一个新 孤立 的结点，其key就是ke，注意在新连了边之后需要重新pushUp
++tot;chl[tot][0]=chl[tot][1]=fa[tot]=0;
siz[tot]=1;val[tot]=sum[tot]=va;tag[tot]=false;
return tot;
}
void pushUp(int p){ // p和其两个儿子已经确定，需要更新p的siz和sum
// pushUp(0)没用
siz[p]=siz[chl[p][0]]+siz[chl[p][1]]+1;
sum[p]=sum[chl[p][0]]+sum[chl[p][1]]+val[p];
}
void pushDown(int p){
if(!tag[p]) return;
// debug(p);cout_n;
// debug(p);debug(tag[chl[p][0]]);debug(tag[chl[p][1]]);
swap(chl[p][0],chl[p][1]);
tag[chl[p][0]]^=true;
tag[chl[p][1]]^=true;
tag[p]=false;
// debug(tag[chl[p][0]]);debug(tag[chl[p][1]]);cout_n;
}
int get(int p) { // 获得p的儿子类型
return p==chl[fa[p]][1];
}
void rotate(int x) {
// 将x旋转，注意这时候一定有fa[x]!=0
// rotate会自动将两个儿子的状态更新到被旋转结点父亲结点
// 如果保证fa[x]和x都被pushDown过那么旋转就没有问题
int y=fa[x],z=fa[y],chk=get(x);
chl[y][chk]=chl[x][chk^1];
if(chl[x][chk^1]) fa[chl[x][chk^1]]=y;
chl[x][chk^1]=y;
fa[y]=x;
if(z) chl[z][y==chl[z][1]]=x;
fa[x]=z;
pushUp(y);pushUp(x);
}
void splay(int x){
// 保证x和fa[x]必须已经pushUp过，再往上会自动pushUp
// splay(0)理论上不会出问题。。。
for(int f=fa[x];(f=fa[x]);rotate(x))
if(fa[f]) rotate(get(x)==get(f)?f:x);
rt=x;
}
int kth(int k){
if(k>siz[rt] || k<=0) return 0;
int cur=rt;
while(true){
pushDown(cur);
if(k<=siz[chl[cur][0]]){
cur=chl[cur][0];
}else{
k-=1+siz[chl[cur][0]];
if(k<=0) break;
cur=chl[cur][1];
}
}
splay(cur);return cur;
}
int findIdx(int x){
// x结点的下标
if(x>siz[rt]) return 0;
stack<int>ps;
int y=x;
while(y){
ps.push(y);y=fa[y];
}
while(ps.size()){
y=ps.top();ps.pop();
pushDown(y);
}
splay(x);
return siz[chl[x][0]]+1;
}
void rotateToRoot(int x){
debug(x);debug(val[x]);
stack<int>ps;
int y=x;
while(y){
ps.push(y);y=fa[y];
}
while(ps.size()){
y=ps.top();ps.pop();
pushDown(y);
}
splay(x);
}
void rotateToRootR(int x){
debug(x);debug(val[x]);
stack<int>ps;
int y=x;
while(y!=rt){
ps.push(y);y=fa[y];
}
while(ps.size()){
y=ps.top();ps.pop();
pushDown(y);
}
for(int f=fa[x];(f=fa[x],f!=rt);rotate(x))
if(fa[f]!=rt) rotate(get(x)==get(f)?f:x);
// debug(rt);debug(chl[rt][1]);debug(x);
}
int insert(ll va,int k=-1){
// 在k后面插入va，如果k==-1，就在数组末尾插入
// debug(va);debug(k);cout_n;
int cur,f;
if(!rt){
rt=newNode(va);
return rt;
}
if(k==-1) k=siz[rt];
if(k==0){
kth(1);
f=rt;cur=newNode(va); // 此时chl[rt][0]应该是空
chl[f][0]=cur;fa[cur]=f;
pushUp(f);
splay(cur);
return cur;
}else{
kth(k); // 把第k个旋转上来
f=rt;cur=chl[rt][1];
// debug(cur);cout_n;
if(!cur){
cur=newNode(va);
chl[f][1]=cur;fa[cur]=f;
pushUp(f);
}else{
do{
pushDown(cur);
f=cur;cur=chl[cur][0];
}while(cur);
cur=newNode(va);
chl[f][0]=cur;fa[cur]=f;pushUp(f);
}
splay(cur);
return cur;
}
}
void reverse(int il,int ir){
// 必须保证：il的左边有东西，ir的右边有东西
debug("reverse");debug(il);debug(ir);cout_n;
int nl=kth(il-1),nr=kth(ir+1);
rotateToRoot(nl);rotateToRootR(nr);cout_n;
// debug(siz[ chl[ chl[rt][1] ][0] ]);cout_n;
tag[ chl[ chl[rt][1] ][0] ]^=true;
// debug(chl[ chl[rt][1] ][0]);cout_n;
}
friend void _osdfs(SplayArray & spa,int p,queue<ll>&_qq){
spa.pushDown(p);
if(spa.chl[p][0]) _osdfs(spa,spa.chl[p][0],_qq);
_qq.push(spa.val[p]);
if(spa.chl[p][1]) _osdfs(spa,spa.chl[p][1],_qq);
}
friend ostream & operator << (ostream & os,SplayArray & spa){
queue<ll>_qq;
_osdfs(spa,spa.rt,_qq);
while(_qq.size()) {
os<<_qq.front()<<' ';_qq.pop();
}
return os;
}
}T;这部分不要直接抄代码！
对应题：ICPC2020南京
void dfs(int u){
siz[u]=1;
for(auto v:G[u]){
dfs(v);siz[u]+=siz[v];
}
for(int i=0;i<=siz[u];++i) {
f0[0][i]=f0[1][i]=f1[0][i]=f1[1][i]=INF;
}
int ii,nn=int(G[u].size());
ii=1;f0[ii][0]=hp[u];f1[ii][1]=0;
int ss=1;
for(int v,i=0;i<nn;++i){
ii=(i&1);v=G[u][i];
for(int k=0;k<=siz[v]+ss;++k){
f0[ii][k]=f1[ii][k]=INF;
}
for(int j=0;j<=ss;++j){
for(int k=0;k<=siz[v];++k){
f0[ii][j+k]=min(f0[ii][j+k],
f0[ii^1][j]+min(dp[v][k][0]+hp[v],dp[v][k][1]));
f1[ii][j+k]=min(f1[ii][j+k],
f1[ii^1][j]+min(dp[v][k][0],dp[v][k][1]));
}
}
ss+=siz[v];
}
for(int i=0;i<=siz[u];++i){
dp[u][i][0]=f0[ii][i];dp[u][i][1]=f1[ii][i];
}
}本题siz就是子树大小，实际上siz应该定义成背包的大小
只提供写法参考，实际上不一定要这么写
如果时限很紧的话，试着把ll换成int
typedef long long int ll;
const int MAXN=1e5+10;
const ll M[2]={1000000009,998244353};
const ll B[2]={29,31};
ll powB[2][MAXN];
void init(){
powB[0][0]=1;powB[1][0]=1;
for(int i=1;i<MAXN;++i){
powB[0][i]=powB[0][i-1]*B[0]%M[0];powB[1][i]=powB[1][i-1]*B[1]%M[1];
}
}
struct THash{
ll h[2];
void move(char ch){
h[0]=(h[0]*B[0]+ch)%M[0];
h[1]=(h[1]*B[1]+ch)%M[1];
}
bool operator < (const THash & th) const {
if(h[0]!=th.h[0]){
return h[0]<th.h[0];
}else{
return h[1]<th.h[1];
}
}
void prt(){
cout<<h[0]<<" , "<<h[1];
}
};
THash minu(const THash & thl,int l,const THash & thr,int r){
// 给l,r处hash的前缀和，得到[l+1,r]的hash
THash th;
th.h[0]=( thr.h[0]- (thl.h[0]*powB[0][r-l]%M[0]) + M[0] ) %M[0];
th.h[1]=( thr.h[1]- (thl.h[1]*powB[1][r-l]%M[1]) + M[1] ) %M[1];
return th;
}字符串下标从$0$开始，长度为$n$
半径长度d1、d2均为从位置i到回文串最右端位置包含的字符个数（包括i）
vector<int> d1(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
k++;
}
d1[i] = k--;
if (i + k > r) {
l = i - k;
r = i + k;
}
}
vector<int> d2(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) {
k++;
}
d2[i] = k--;
if (i + k > r) {
l = i - k - 1;
r = i + k;
}
}字符串下标从0开始。前缀函数定义：$\pi[i]$表示$s[0...i]$中最长相同真前缀和真后缀的长度
vector<int> getPi(string & s) {
int n = (int)s.length();vector<int> pi(n);
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j > 0 && s[i] != s[j]) j = pi[j - 1];
if (s[i] == s[j]) j++;
pi[i] = j;
}
return pi;
}const int N=60,L=1e6+10; // 模式串、文本串长度
const int MAXN = N * 10000; // 这里空间能开大点就开大点
struct ACAuto{
int tot,tr[MAXN][26],fail[MAXN],cnt[MAXN];
// cnt[u]:u字符串出现次数
void init() {
for(int i=0;i<=tot;++i){
memset(tr[i],0,sizeof(tr[i]));
fail[i]=cnt[i]=0;
}
tot=0;
}
void insert(char * s, int id) { // id 表示原始字符串的编号
int u = 0,c;char * p=s;
while(*p){
c=*(p++)-'a';
if(!tr[u][c]) tr[u][c]=++tot;
u=tr[u][c];
}
++cnt[u];
}
void build() {
queue<int>q;
for (int i=0;i<26;i++){
if (tr[0][i]) q.push(tr[0][i]);
}
while (q.size()) {
int u = q.front();q.pop();
for (int i=0;i<26;i++) {
if (tr[u][i]){
fail[tr[u][i]]=tr[fail[u]][i];q.push(tr[u][i]);
}else{
tr[u][i]=tr[fail[u]][i];
}
}
}
}
int query(char * t){
int u=0,c,res=0;
while(*t){
c=*(t++)-'a';
u=tr[u][c];
for(int j=u;j && cnt[j]!=-1;j=fail[j]){
res+=cnt[j];cnt[j]=-1;
}
}
return res;
}
};注意：
-
$v=fail[u]$ 表示$v$是$u$的最长后缀 -
这个使用的是oi-wiki的自动机改进，
tr[u][c]可能直接表示转移，即tr[fail[u]][i]，所以直接使用tr[u][c]转移就行 -
在
query的时候，有时候需要在fail树上跳，一定要注意将vis过的点标记上，不要重复跳，不然时间复杂度就爆炸 -
fail树有时候会很有用，对于某一个问题，可以考虑fail树在这个问题上的意义是什么 -
记得
build！ -
模式串总长为
L的AC自动机，下面的算法while(*t){ c=(*t++)-'a'; u=tr[u][c]; for(Dat dat:ds[u]){ ... } // ds[u]记录的fail树上u所有的“真实插入的串”的终点结点的信息 }
时间复杂度是$L\sqrt L$
int c2i(char ch){
return ch-'a';
}
struct SNode{
int len,link,nxt[26];
};
const int MAXLEN=1e5+10;
struct SAM{
SNode node[MAXLEN<<1];
int sz,lst;
void init(){
for(int i=0;i<sz;++i) memset(node+i,0,sizeof(SNode));
node[0].len=0;node[0].link=-1;sz=1;lst=0;
}
void extend(char ch){
int cur=sz++,c=c2i(ch);
node[cur].len=node[lst].len+1; // 新结点p长度一定是lst加一
int p=lst;
while(p!=-1 && !node[p].nxt[c]){
node[p].nxt[c]=cur;p=node[p].link;
// p的link指p最长非相同endpos后缀的结点
// 所有的这些结点如果nxt[c]没有的话都应该指向p
}
if(p==-1){ // 已经跳到不存在的点了
node[cur].link=0;
}else{ // 跳到的点存在
int q=node[p].nxt[c]; // p通过c转移的结点
if(node[p].len+1==node[q].len){
node[cur].link=q;
// 如果q对应的最长串就是p最长的加上c
// 那么直接将cur的link给到q就行
}else{ // 如果不是，就需要克隆点
int cln=sz++;
// cln表示的是新的endpos
// 这个endpos满足：其最长串是p最长串加上c
node[cln].len=node[p].len+1;
memcpy(node[cln].nxt,node[q].nxt,sizeof(node[q].nxt));
node[cln].link=node[q].link;
while(p!=-1 && node[p].nxt[c]==q){
node[p].nxt[c]=cln;
p=node[p].link;
}
node[q].link=node[cur].link=cln;
}
}
lst=cur;
}
};注意：
- 在构建图的过程中，
link和nxt都是可能改变的，所以不要妄图使用DAG的信息在线计算答案 -
$minlen(v)=len(link(v))+1$ ，并且每次增加的子串数量为$len(cur)-minlen(cur)+1=len(cur)-len(link(cur))$ - 在SAM中有一条“主链”，也就是整串的链，这条链的结点表示真实存在于原字符串的$endpos$（或者说右端点），可能有特殊含义
-
cur表示的就是右端点所在的endpos！利用这点可以求类似“endpos中有多少个不同位置的子串”问题 - 构建完之后，
lst通过link到达的所有状态都是“终止状态”，并且点的值域是[0,sz-1]！也就是sz并不对应一个点 - 多样例记得清空
node信息！
注意：判断是否是连通图，下面的板子没有验证连通性
kruskal，那就说明是稠密图，那用$O(n^2)$的prim就行
typedef long long int ll;
const int MAXN=5e3+10;
ll co[MAXN][MAXN],le[MAXN]; // 邻接矩阵 最小值数组
int n;bool vis[MAXN];
ll prim(){
memset(le,0x3f,sizeof(le));memset(vis,false,sizeof(vis));
ll res=0,len=0;int u=1;
while(u){
vis[u]=true;res+=len;
for(int v=1;v<=n;++v){
if(!vis[v]){
le[v]=min(le[v],co[u][v]);
}
}
u=0; // le[0]就是INF
for(int i=1;i<=n;++i){
if(!vis[i] && le[i]<le[u]){
u=i;len=le[i];
}
}
}
return res;
}最常用写法
本质就是sort+并查集，就不贴代码了
const int MAXN=1e5+10;
typedef long long int ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
struct edge{
int v;ll w;
edge(int _v=0,ll _w=0):v(_v),w(_w){
}
};
struct cmpNode{
bool operator () (const edge & e1,const edge & e2) const {
return e1.w>e2.w;
}
};
vector<edge>G[MAXN];
ll dist[MAXN];int n,m;bool vis[MAXN];
void dijkstra(int s){
memset(dist,0x3f,sizeof(dist));
memset(vis,false,sizeof(vis));
priority_queue<edge,vector<edge>,cmpNode>q;
dist[s]=0;q.push(edge(s,dist[s]));
while(q.size()){
edge e=q.top();q.pop();
if(vis[e.v]){
continue;
}
vis[e.v]=true;
for(auto v:G[e.v]){
if(!vis[v.v] && dist[v.v]>dist[e.v]+v.w){
dist[v.v]=dist[e.v]+v.w;q.push(edge(v.v,dist[v.v]));
}
}
}
}typedef long long int ll;
struct node {
int v;
ll w;
node(int v=0, ll w=0) : v(v), w(w){};
};
const int MAXN = 1e5+100;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll dist[MAXN];int dcnt[MAXN];bool inQ[MAXN];
vector<node> G[MAXN];
bool relax(int u,int v,ll w) {
if (dist[v]>dist[u]+w) {
dist[v]=dist[u]+w;++dcnt[v];
return true;
}else{
return false;
}
}
bool SPFA(int s,int cntV) { // 返回是否有负环，s是源，cntV是点的数量
memset(dist, (int)INF, sizeof(dist));memset(dcnt, 0, sizeof(dcnt));
queue<int>Q;inQ[s]=true;dist[s] = 0;Q.push(s);
while (!Q.empty()) {
int u = Q.front();Q.pop();
inQ[u]=false;
for (node i : G[u]) {
if ( relax(u, i.v, i.w) && !inQ[i.v] ) {
if (dcnt[i.v]>=cntV+1) {
return true;
}
Q.push(v);
inQ[v]=true;
}
}
}
return false;
}typedef long long int ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int MAXN=3e2+10;
int n;
ll dist[MAXN][MAXN];
void floyd(){
// 先将dist里面图的边权标上，其他的是INF
for (int k=1; k<=n; k++) {
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
}
}A*可以看作一种图论搜索，下面的“点”都可以理解成一种状态
定义起点$s$、终点$t$，从起点开始的距离函数$g(x)$，到终点的距离函数$h(x)$，以及估价函数$f(x)=g(x)+h(x)$
A*算法每次从优先队列中取出一个$f$最小的元素，然后更新其相邻的状态（就是加入队列）
定义$h^(x)$为$x$到终点$t$实际的距离函数，实际上$h^(x)$就是反向图$s$到$x$的最短路
如果$h\le h^*$，则A*可以找到最优解；在满足前式的情况下，如果$h$满足三角形不等式，那么A*过程中不会多次从某优先队列中取某一个点（此时时间复杂度最有保障）
三角形不等式指：如果有边$\lang u,v\rang$那么$h(v)\le h(u)+w(\lang u,v\rang )$
注意在需要字典序最小的情况可以使用优先队列维护待遍历队列，其他的不写了
const int MAXN=1e5+10;
vector<int>G[MAXN];
int en[MAXN],n,m,din[MAXN],dout[MAXN];
void add(int u,int v){
G[u].push_back(v);++din[v];++dout[u];
}
stack<int>res;
void dfs(int u){
int ie=en[u]++;
while(ie<G[u].size()){
dfs(G[u][ie]);
ie=en[u]++;
}
res.push(u);
}
// in main
int s=1; // 起点，注意需要先判断有没有欧拉回路/路径存在，以及起点应该在哪
dfs(s);
while(res.size()){
cout<<res.top()<<' ';res.pop();
}const int MAXN=1e3+10;
int G[MAXN][MAXN];
int ct[MAXN],n,m,d[MAXN];
void add(int u,int v){
++G[u][v];++G[v][u];++d[u];++d[v];
}
stack<int>res;
void dfs(int u){
for(int v=ct[u];v<=n;++v){
while(G[u][v]){
--G[u][v];--G[v][u];
ct[u]=v;
dfs(v);
}
}
res.push(u);
}
// in main
dfs(s); // 找到起点s
while(res.size()){
cout<<res.top()<<' ';res.pop();
}const int MAXN=1e3+10;
int dir[MAXN][MAXN],n,nxt[MAXN];
// dir[u][v]=1表示u->v
void work(){
nxt[0]=1;nxt[1]=n+1;
for(int i=2;i<=n;++i){
int pre=0,j=nxt[0];
for(;j;j=nxt[j],pre=nxt[pre]){
if(dir[i][j]==1){
nxt[pre]=i;nxt[i]=j;break;
}
}
}
int u=nxt[0];
while(u!=n+1){
cout<<u<<' ';u=nxt[u];
}
cout<<'\n';
}// Tarjan算法，注意这里dfn[0]和scid[0]都表示计数器
int dfn[MAXN],low[MAXN],scid[MAXN];
struct SC{
int sz,pt;
}sc[MAXN];
stack<int>scst;
bool inst[MAXN];
void scdfs(int u){
dfn[u]=low[u]=++dfn[0];
scst.push(u);inst[u]=true;
for(auto v:G[u]){
if(!dfn[v]){
scdfs(v);low[u]=min(low[u],low[v]);
}else if(inst[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
int id=++scid[0],v;
while(scst.top()!=u){
v=scst.top();scst.pop();inst[v]=false;
++sc[id].sz;scid[v]=id;
}
scst.pop();inst[u]=false;
++sc[id].sz;scid[u]=id;
}
}数据格式
- 命题
x为真：x - 命题
x为假：!x - 命题
a、b等可以推出x为真：a b -> x - 命题
a、b等可以推出x为假：a b -> !x
其中a、b、x均为数字
const int MAXN=1e6+10;
int n,m,res[MAXN],cnt[MAXN],c2a[MAXN];
// n:陈述句个数 m:命题个数
// res[i]表示i这个命题是否被确定
// cnt[c]表示c这个条件还有几个前件没有确定
// c2a[c]表示c这个条件得到的结论
vector<int>a2c[MAXN]; // a2c[a]表示a这个前件会指向的集合
bool usable[MAXN]; // usable[c]表示c这个条件集合已经没用了(存在前件为假)
void init(){
memset(res,-1,sizeof(res));memset(usable,true,sizeof(usable));
}
void noAns(){
cout<<"conflict\n";exit(0);
}
typedef char * pchar;
int isNum(pchar & pc){
int re=0;
while(*pc && *pc!=' ' && *pc!='\n'){
if(*pc<'0' || *pc>'9'){
++pc;
}else{
re=re*10+(*pc++)-'0';
}
}
++pc;
return re;
}
queue<int>aq;
bool assign(int a,int x){
if(res[a]==!x){
noAns();
return false;
}else if(res[a]==x){
return false;
}else{
res[a]=x;
return true;
}
}
void gen(char * str,int c){
char * p=str;
if(strstr(str,"->")!=nullptr){
int a;
while( (a=isNum(p)) ){
a2c[a].push_back(c);++cnt[c];
}
if(*p=='!'){ // a<0,为...->!a
++p;a=-isNum(p);
}else{
a=isNum(p);
}
c2a[c]=a;
}else{
int a;
if(*p=='!'){
++p;a=isNum(p);assign(a,0);
}else{
a=isNum(p);assign(a,1);
}
aq.push(a);
}
}
const int MAXLEN=MAXN<<2;
char str[MAXLEN];
void work(){
while(aq.size()){
int a=aq.front();aq.pop();
if(res[a]==0){
for(int c:a2c[a]){
usable[c]=false;
}
}
for(int c:a2c[a]){
--cnt[c];
if(cnt[c]==0 && usable[c]){
usable[c]=false;
int _a=c2a[c];
if(_a<0){
if(assign(-_a,0)){
aq.push(-_a);
}
}else if(_a>0){
if(assign(_a,1)){
aq.push(_a);
}
}
}
}
}
}
void prt(){
for(int i=1;i<=m;++i){
printf(res[i]==1?"T":"F");
}
printf("\n");
}先init()，输入语句str后放入gen(str)里，然后跑work()就行
const int MAXN=1e5+10;
struct TwoSatBF{ // 暴力求解字典序最小的解
int n;vector<int>G[MAXN<<1];
bool slt[MAXN<<1];
// 偶数点：false 奇数点：true 这样x^1就是反面
void init(int _n){
n=_n;
for(int i=0;i<(n<<1);++i){
G[i].clear();slt[i]=false;
}
}
void addLimit(int x,int y){
// 选了x就要选y，具体看情况使用
G[x].push_back(y);
G[y^1].push_back(x^1);
}
stack<int>st;
void clearst(){while(st.size()) st.pop();}
bool dfs(int u){
if(slt[u^1]){
return false;
}else if(slt[u]){
return true;
}
slt[u]=true;
st.push(u);
for(auto v:G[u]){
if(!dfs(v)){
return false;
}
}
return true;
}
bool solve(){
for(int u=0;u<(n<<1);u+=2){
if(!slt[u] && !slt[u^1]){
clearst();
if(!dfs(u)){
clearst();
if(!dfs(u^1)){
return fales;
}
}
}
}
return true;
}
};const int MAXN=2e6+10; // 注意开两倍空间
struct TwoSatSC{
// x和x+1一组，其中x=2k，共n组，编号[0,2n-1]，注意编号是从0开始！
void init(int _n){ // 多样例记得memset
n=_n;
}
vector<int>G[MAXN];
void add(int u,int v){
// 选了u就要选v，不自带对称建边
G[u].push_back(v);
}
int n,dfn[MAXN],low[MAXN],scid[MAXN],scsz,dfsz;
struct SC{
int sz,pt;
}sc[MAXN];
stack<int>scst;
bool inst[MAXN];
void scdfs(int u){
dfn[u]=low[u]=++dfsz;
scst.push(u);inst[u]=true;
for(auto v:G[u]){
if(!dfn[v]){
scdfs(v);low[u]=min(low[u],low[v]);
}else if(inst[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
int id=++scsz,v;
while(scst.top()!=u){
v=scst.top();scst.pop();inst[v]=false;
++sc[id].sz;scid[v]=id;
}
scst.pop();inst[u]=false;
++sc[id].sz;scid[u]=id;
}
}
bool check(){
for(int i=0;i<2*n;++i){
if(!dfn[i]){
scdfs(i);
}
}
for(int i=0;i<2*n;i+=2){
if(scid[i]==scid[i+1]){
return false;
}
}
return true;
}
void prt(){
for(int i=0;i<2*n;i+=2){
cout<<(scid[i]<scid[i+1]?"0 ":"1 ");
}
}
};#define pb push_back
const int MAXN=1e5+10;
vector<int>dc[MAXN],G[MAXN],T[MAXN<<1];
int dfn[MAXN],low[MAXN],dccnt,sp;
stack<int>dcst;
void dcdfs(int u){
dfn[u]=low[u]=++dfn[0];
dcst.push(u);
for(int v:G[u]){
if(dfn[v]){
low[u]=min(low[u],dfn[v]);
}else{
dcdfs(v);
low[u]=min(low[u],low[v]);
if(dfn[u]==low[v]){
++dccnt;++sp;
int x;
do{
x=dcst.top();dcst.pop();dc[dccnt].pb(x);
T[x].pb(sp);T[sp].pb(x);
}while(x!=v);
dc[dccnt].pb(u);
T[sp].pb(u);T[u].pb(sp);
}
}
}
}注意下：
- 记考察去重、去自环、图连通性的影响
- 图$G=\lang{1,2},{(1,2)}\rang$也是一个点双，会被记录；只有一个点的平凡图并不会被记录，因为会被认为不属于任何点双
- 圆方树
T中，双连通分量会被拍成方点，每个原图中的点（被称为圆点）都会连接到所有其所在的双连通分量对应的方点上，特别的，如果一个方点连接了正好两个圆点，这两个圆点的边是一个桥；所有T中度大于1的都是割点 -
sp在一开始要置成n
const int MAXN=1e5+10;
typedef pair<int,int> pii;
#define ff first
#define ss second
#define pb push_back
vector<int>G[MAXN];
int n,m,ans,vist[MAXN],dd[MAXN];
int work() {
for(int u,v,i=1;i<=m;i++){
u=edges[i].ff;v=edges[i].ss;
if(dd[u]==dd[v]){
G[min(u,v)].pb(max(u,v));
}else if(dd[u]>dd[v]){
G[v].pb(u);
}else if(dd[u]<dd[v]){
G[u].pb(v);
}
}
for(int u=1;u<=n;u++){
for(auto v:G[u])
vist[v]=u;
for(auto v:G[u])
for(auto w:G[v])
if(vist[w]==u)
++ans;
}
return ans;
}时间复杂度$O(n\sqrt n)$
下面的代码求的是最短路，其中会有三类边，一个是$u\to v$、一个是$u\to [l,r]$、一个是$[l,r]\to v$
原理：
其中绿色、蓝色表示线段树上的边权为$0$的边，黄色表示同类点的双向边权为$0$的边
橙色是单个点指向区间点，紫色边是区间点指向单个点
typedef long long int ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+10;
const int MAXN=N*10;
#define pb push_back
struct Edge{
int v;ll w;
bool operator < (const Edge & e) const {
return w>e.w;
}
};
vector<Edge>G[MAXN];
void addE(int u,int v,ll w){
G[u].pb(Edge{v,w});
}
struct Node{
int il,ir,ls,rs;
}node[MAXN];
#define ls(p) (node[p].ls)
#define rs(p) (node[p].rs)
#define il(p) (node[p].il)
#define ir(p) (node[p].ir)
int rt[2],tot,id[N][2],n,m,s;
void newNode(int & p,int l,int r){
p=++tot;il(p)=l;ir(p)=r;
}
void build0(int & p,int l,int r){
if(!p) newNode(p,l,r);
if(l==r){
id[l][0]=p;return;
}
int mid=(l+r)>>1;
build0(ls(p),l,mid);
build0(rs(p),mid+1,r);
addE(p,ls(p),0);addE(p,rs(p),0);
}
void build1(int & p,int l,int r){
if(!p) newNode(p,l,r);
if(l==r){
id[l][1]=p;return;
}
int mid=(l+r)>>1;
build1(ls(p),l,mid);
build1(rs(p),mid+1,r);
addE(ls(p),p,0);addE(rs(p),p,0);
}
void add0(int p,int u,int L,int R,ll w){
if(L<=il(p) && ir(p)<=R){
addE(id[u][1],p,w);return;
}
int mid=(il(p)+ir(p))>>1;
if(mid>=L) add0(ls(p),u,L,R,w);
if(mid+1<=R) add0(rs(p),u,L,R,w);
}
void add1(int p,int L,int R,int v,ll w){
if(L<=il(p) && ir(p)<=R){
addE(p,id[v][0],w);return;
}
int mid=(il(p)+ir(p))>>1;
if(mid>=L) add1(ls(p),L,R,v,w);
if(mid+1<=R) add1(rs(p),L,R,v,w);
}
void addSelf(){
for(int i=1;i<=n;++i)
addE(id[i][0],id[i][1],0);addE(id[i][1],id[i][0],0);
}
ll dist[MAXN];bool vis[MAXN];
void dijkstra(int s){
memset(dist,0x3f,sizeof(dist));
priority_queue<Edge>q;
q.push(Edge{id[s][0],0});q.push(Edge{id[s][1],0});
dist[id[s][0]]=dist[id[s][1]]=0;int u;
while(q.size()){
Edge nn=q.top();q.pop();u=nn.v;
if(vis[u]){
continue;
}
vis[u]=true;
for(Edge e:G[u]){
if(!vis[e.v] && dist[e.v]>dist[u]+e.w){
dist[e.v]=dist[u]+e.w;q.push(Edge{e.v,dist[e.v]});
}
}
}
}
// in main
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m>>s;
build0(rt[0],1,n);build1(rt[1],1,n);
ll w;
for(int u,v,l,r,opt,i=1;i<=m;++i){
cin>>opt;
switch(opt){
case 1:{
cin>>u>>v>>w;
addE(id[u][0],id[v][0],w);
break;
}
case 2:{
cin>>u>>l>>r>>w;
add0(rt[0],u,l,r,w);
break;
}
case 3:{
cin>>v>>l>>r>>w;
add1(rt[1],l,r,v,w);
break;
}
}
}
addSelf();dijkstra(s);
for(int i=1;i<=n;++i){
if(dist[id[i][0]]==INF){
dist[id[i][0]]=-1;
}
cout<<min(dist[id[i][0]],dist[id[i][1]])<<' ';
}
cout<<'\n';
路径覆盖指：给定有向图$G=(V,E)$。设$P$是$G$的一个简单路(顶点不相交)的集合。如果$V$中每个顶点恰好在$P$的一条路上，则称$P$是$G$的一个路径覆盖
在DAG上求路径覆盖，由于在路径覆盖中，a->b->c可以看作：a这个点只选择了一个b作为其出边、而b只选择了c
因此可以将每一个点拆成两个点：左边的表示最后的路径中有这个点作为起点，右边的表示有这个点作为终点，之后将所有的图上的边加入这个二分图。由于一个点只能“选择”一个另一个点“去往”，同时一个点也只能被一个另一个点“来自”，这里跑二分图的最大流就行
这个算法必须要求原图是DAG，因为如果不是DAG，而是有环的话，那么环上的点就都会满足“有入有出”，因此二分图的算法会求出来它，但是实际上我们要的是路径
有两类点，一类叫$A$，一类叫$B$，存在一些取了$A$里某个点就不能取$B$中的某个点（或者反之）的约束，取点有价值，问怎么取点价值最高
这种问题可以这么建模：对于$\forall a\in A$，从$s$连流量为$a$价值的边到$a$，$\forall b\in B$，从$b$连流量为$b$价值的边到$t$，对于任何限制$(a,b)$，从$a$连一条流量为无穷的边到$b$，之后跑最小割，就可以表示“最少舍弃哪些边”，也就是得到了最大的价值
直接用例题：
如果：
-
要求所有路径点不交
- 将一个点$x$拆成入点$x_i$和出点$x_o$，连流量为$1$、花费为负点权的边
- 对于原图上的边$\lang u,v\rang $，连$u_o$到$v_i$的流量为$1$、花费为$0$的边
-
要求仅在点交，不能边交
- 将一个点$x$拆成入点$x_i$和出点$x_o$，连流量为$INF$、花费为负点权的边
- 对于原图上的边$\lang u,v\rang $，连$u_o$到$v_i$的流量为$1$、花费为$0$的边
-
可以任意交
- 将一个点$x$拆成入点$x_i$和出点$x_o$，连流量为$INF$、花费为负点权的边
- 对于原图上的边$\lang u,v\rang $，连$u_o$到$v_i$的流量为$INF$、花费为$0$的边
时间复杂度：$O(nm)$
template <typename T>struct hungarian {
int n;
vector<int> matchx,matchy; // 左右集合对应的匹配点
vector<int> pre; // 连接右集合的左点
vector<bool> visx,visy; // 拜访数组 左右
vector<T> lx,ly;
vector<vector<T> > g;
vector<T> slack;
T inf,res;
queue<int> q;
int org_n,org_m;
hungarian(int _n, int _m) {
org_n = _n;
org_m = _m;
n = max(_n, _m);
inf = numeric_limits<T>::max();
res = 0;
g = vector<vector<T> >(n, vector<T>(n));
matchx = vector<int>(n, -1);
matchy = vector<int>(n, -1);
pre = vector<int>(n);
visx = vector<bool>(n);
visy = vector<bool>(n);
lx = vector<T>(n, -inf);
ly = vector<T>(n);
slack = vector<T>(n);
}
void addEdge(int u, int v, T w) {
if(w<0){ // 负权不如不匹配
g[u][v]=0;
}else{
g[u][v] = w;
}
}
bool check(int v) {
visy[v] = true;
if (matchy[v] != -1) {
q.push(matchy[v]);
visx[matchy[v]] = true; // in S
return false;
}
// 找到新的未匹配点 更新匹配点 pre 数组记录着"非匹配边"上与之相连的点
while (v != -1) {
matchy[v] = pre[v];
swap(v, matchx[pre[v]]);
}
return true;
}
void bfs(int i) {
while (!q.empty()) {
q.pop();
}
q.push(i);
visx[i] = true;
while (true) {
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v = 0; v < n; v++) {
if (!visy[v]) {
T delta = lx[u] + ly[v] - g[u][v];
if (slack[v] >= delta) {
pre[v] = u;
if (delta) {
slack[v] = delta;
} else if (check(v)) { // delta=0 代表有机会加入相等子图 找增广路
// 找到就return 重建交错树
return;
}
}
}
}
}
// 没有增广路 修改顶标
T a = inf;
for (int j = 0; j < n; j++) {
if (!visy[j]) {
a = min(a, slack[j]);
}
}
for (int j = 0; j < n; j++) {
if (visx[j]) { // S
lx[j] -= a;
}
if (visy[j]) { // T
ly[j] += a;
} else { // T'
slack[j] -= a;
}
}
for (int j = 0; j < n; j++) {
if (!visy[j] && slack[j] == 0 && check(j)) {
return;
}
}
}
}
void solve() {
// 初始顶标
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
lx[i] = max(lx[i], g[i][j]);
}
}
for (int i = 0; i < n; i++) {
fill(slack.begin(), slack.end(), inf);
fill(visx.begin(), visx.end(), false);
fill(visy.begin(), visy.end(), false);
bfs(i);
}
// custom
for (int i = 0; i < n; i++) {
if (g[i][matchx[i]] > 0) {
res += g[i][matchx[i]];
} else {
matchx[i] = -1;
}
}
// cout << res << "\n";
// for (int i = 0; i < org_n; i++) {
// cout << matchx[i] + 1 << " ";
// }
// cout << "\n";
}
};
// in main.cpp
int n;
cin>>n>>m; // 图左右的点数量
hungarian<int> solver(n,m);
while(ecnt--){
int u,v,w;
solver.addEdge(u-1,v-1,w); // solver里面的下标都是从0开始，u,v表示左右第几个点
solver.solve();
}const int MAXN=2010;
const int INF=0x3f3f3f3f;
struct Dinic {
struct Edge {
int from, to, cap, flow;
Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};
int n, m, s, t;
vector<Edge>edges;
vector<int>G[MAXN];
int d[MAXN],cur[MAXN];bool vis[MAXN];
void init(int n) {
this->n=n;
for (int i = 0; i <=n; i++) G[i].clear();
edges.clear();
}
void addEdge(int from, int to, int cap) {
edges.push_back(Edge(from, to, cap, 0));
edges.push_back(Edge(to, from, 0, 0));
m = edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
bool BFS() {
memset(vis, 0, sizeof(vis));
queue<int> Q;Q.push(s);d[s] = 0;vis[s] = 1;
while (!Q.empty()) {
int x = Q.front();Q.pop();
for (int i = 0; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if (!vis[e.to] && e.cap > e.flow) {
vis[e.to] = 1;
d[e.to] = d[x] + 1;
Q.push(e.to);
}
}
}
return vis[t];
}
int DFS(int x,int a) {
if (x == t || a == 0) return a;
int flow = 0, f;
for (int& i = cur[x]; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if (d[x]+1==d[e.to] && (f=DFS(e.to,min(a,e.cap-e.flow))) > 0) {
e.flow += f;
edges[G[x][i] ^ 1].flow -= f;
flow += f;a -= f;
if (a == 0) break;
}
}
return flow;
}
int maxFlow(int s, int t) {
this->s = s;
this->t = t;
int flow = 0;
while (BFS()) {
memset(cur, 0, sizeof(cur));
flow += DFS(s, INF);
}
return flow;
}
}dinic;时间复杂度$O(n^2m)$，在二分图最大匹配时是$O(m\sqrt n)$
注意：
- 在输出方案时，遍历边，并且判断边是否是满的（
e.flow==e.cap） - 使用
.maxFlow(s,t)求最大流 - 不需要考虑环的问题
最小割相当于把图中所有点分成两个集合S、T（其中源点在S集合、汇点在T集合）且要求所有S到T的边的花费和最小
最大流等于最小割
跑完最大流之后，在输出方案的时候，从s开始，根据边是否有残差流量来dfs，这样可以找到所有S集合的点
const long long INF=0x3f3f3f3f3f3f3f3f;
// const int INF=0x3f3f3f3f;
const int N=3e4+10,M=3e4+10;
template<typename T>struct MCMF{
int n,m,tot=1,lnk[N],cur[N],ter[M],nxt[M],cap[M];
T dis[N],ret,cost[M]; // ret:最小花费
bool vis[N];
void see(int n){
for(int i=1;i<=n;++i){
for(int e=lnk[i];e;e=nxt[e]){
if(e&1) continue;
int v=ter[e];
cout<<i<<" -> "<<v<<" : f("<<cap[e]<<") c("<<cost[e]<<") "<<endl;
}
}
}
void init(){
tot=1;ret=0;memset(lnk,0,sizeof(lnk));
}
void _add(int u,int v,int w,T c) {
ter[++tot]=v;nxt[tot]=lnk[u];lnk[u]=tot;cap[tot]=w;cost[tot]=c;
}
void addEdge(int u,int v,int w,T c) {
_add(u, v, w, c);_add(v, u, 0, -c);
}
bool spfa(int s,int t){
memset(dis,0x3f,sizeof(dis));
memcpy(cur,lnk,sizeof(lnk));
queue<int>q;q.push(s);dis[s]=0;vis[s]=true;
while(!q.empty()){
int u=q.front();q.pop();vis[u]=false;
for(int ie=lnk[u];ie;ie=nxt[ie]){
int v=ter[ie];
if(cap[ie] && dis[v]>dis[u]+cost[ie]){
dis[v]=dis[u]+cost[ie];
if(!vis[v]) q.push(v),vis[v]=true;
}
}
}
return dis[t]!=INF;
}
int dfs(int u,int t,int flow){
if(u==t) return flow;
vis[u]=true;
int ans=0;
for(int & ie=cur[u];ie && ans<flow;ie=nxt[ie]){
int v=ter[ie];
if(!vis[v] && cap[ie] && dis[v]==dis[u]+cost[ie]){
int x=dfs(v,t,min(cap[ie],flow-ans));
if(x) ret+=x*cost[ie],cap[ie]-=x,cap[ie^1]+=x,ans+=x;
}
}
vis[u]=false;
return ans;
}
int mcmf(int s,int t){
int ans=0;
while(spfa(s,t)){
int x;
while( ( x=dfs(s,t,0x3f3f3f3f) ) ) ans+=x;
}
return ans; // 最大流，ret是花费
}
};
MCMF<long long>mcmf;时间复杂度：$O(mnf)$，其中$f$为最大流
注意，由于使用了SPFA，所以在有环的问题中可能会出错
时间复杂度仍然是$O(nmf)$
const int N=2e3+10,M=1e5+5;
typedef double db;
const db INF=1e18,eps=1e-10;
struct MCMF{
int n,m,tot=1,lnk[N],cur[N],ter[M],nxt[M],cap[M];
db dis[N],ret,cost[M]; // ret:最小花费
bool vis[N];
void see(int n){
for(int i=1;i<=n;++i){
for(int e=lnk[i];e;e=nxt[e]){
if(e&1) continue;
int v=ter[e];
cout<<i<<" -> "<<v<<" : f("<<cap[e]<<") c("<<cost[e]<<") "<<endl;
}
}
}
void init(){
tot=1;ret=0;memset(lnk,0,sizeof(lnk));
}
void _add(int u,int v,int w,db c) {
ter[++tot]=v;nxt[tot]=lnk[u];lnk[u]=tot;cap[tot]=w;cost[tot]=c;
}
void addEdge(int u,int v,int w,db c) {
_add(u, v, w, c);_add(v, u, 0, -c);
}
bool spfa(int s,int t){
fill(dis,dis+N,INF);
memcpy(cur,lnk,sizeof(lnk));
queue<int>q;q.push(s);dis[s]=0;vis[s]=true;
while(!q.empty()){
int u=q.front();q.pop();vis[u]=false;
for(int ie=lnk[u];ie;ie=nxt[ie]){
int v=ter[ie];
if(cap[ie] && dis[v]>dis[u]+cost[ie]){
dis[v]=dis[u]+cost[ie];
if(!vis[v]) q.push(v),vis[v]=true;
}
}
}
return dis[t]!=INF;
}
int dfs(int u,int t,int flow){
if(u==t) return flow;
vis[u]=true;
int ans=0;
for(int & ie=cur[u];ie && ans<flow;ie=nxt[ie]){
int v=ter[ie];
if(!vis[v] && cap[ie] && abs(dis[v]-(dis[u]+cost[ie]))<eps ){
int x=dfs(v,t,min(cap[ie],flow-ans));
if(x) ret+=x*cost[ie],cap[ie]-=x,cap[ie^1]+=x,ans+=x;
}
}
vis[u]=false;
return ans;
}
int mcmf(int s,int t){
int ans=0;
while(spfa(s,t)){
int x;
while( ( x=dfs(s,t,0x3f3f3f3f) ) ) ans+=x;
}
return ans; // 最大流，ret是花费
}
}mcmf;const int MAXN=610,INF=0x3f3f3f3f;
int ew[MAXN][MAXN],n,m,sd[MAXN];bool vis[MAXN],bin[MAXN];
int contract(int & s, int & t){
memset(sd,0,sizeof(sd));memset(vis,false,sizeof(vis));
int k,maxc,mncut=0;
for(int i=1;i<=n;++i){
k=-1;maxc=-1;
for(int j=1;j<=n;++j){
if(!vis[j] && !bin[j] && sd[j]>maxc){
maxc=sd[j];k=j;
}
}
if(k==-1){ // 此时已经选完
return mncut;
}
s=t;t=k;mncut=maxc;vis[k]=true;
for(int j=1;j<=n;++j){
if(!vis[j] && !bin[j]) sd[j]+=ew[k][j];
}
}
return mncut;
}
int StoerWagner(){
int ans=INF,s,t;
for(int i=1;i<=n-1;++i){
ans=min(ans,contract(s,t));
// 用s与t不属于同一集合时的最小割更新答案；s和t本质是随机选的
bin[t]=true; // s与t属于同一集合
for(int j=1;j<=n;++j){
if(!bin[j]) {
ew[s][j]+=ew[j][t];ew[j][s]+=ew[j][t];
}
}
}
return ans;
}小心重边（自环无所谓）
struct MT19937{
bool isInit;int index,MT[624];
void srand(int seed){
index = 0;
isInit = 1;
MT[0] = seed;
for(int i=1; i<624; i++){
int t = 1812433253 * (MT[i-1] ^ (MT[i-1] >> 30)) + i;
MT[i] = t & 0xffffffff; //取最后的32位
}
}
void generate(){
for(int i=0; i<624; i++){
int y = (MT[i] & 0x80000000) + (MT[(i+1) % 624] & 0x7fffffff);
MT[i] = MT[(i + 397) % 624] ^ (y >> 1);
if (y & 1) MT[i] ^= 2567483615;
}
}
int rand(){
if(index == 0)
generate();
int y = MT[index];
y = y ^ (y >> 11);
y = y ^ ((y << 7) & 2636928640);
y = y ^ ((y << 15) & 4022730752);
y = y ^ (y >> 18);
index = (index + 1) % 624;
return y;
}
}mt;
// in main
mt.srand(0); //设置随机种子-
取消字节对齐
在MLE的时候使用
#pragma pack(1)