前言

带*为下标从1开始，否则为从0开始

基础算法

快速排序*

void qsort(ll l,ll r)
{
   
  if(l>=r) return;
  ll val=arr[l],p=l,q=r;
  while(p<q)
  {
   
    while(p<q&&arr[q]>val) q--;
    if(p<q){
   arr[p]=arr[q];p++;}
    while(p<q&&arr[p]<val) p++;
    if(p<q){
   arr[q]=arr[p];q--;}
  }
  arr[p]=val;
  qsort(l,p-1);
  //if(m-1>p) 求第m小数
  qsort(p+1,r);
}

并查集

带权+路径压缩+启发式合并（前提：权不考虑符号）

ll find(ll x) {
   
  if(x==father[x]) return x;
  ll fa=father[x];
  father[x]=find(father[x]);
  value[x]=(value[x]+value[fa])%2;
  return father[x];
}
void merge(ll u,ll v,ll val) {
   
  ll fu=find(u),fv=find(v);
  if(height[fu]>height[fv]) {
   
    father[fv]=fu;
    value[fv]=(val+value[u]-value[v]+2)%2;
  } else {
   
    father[fu]=fv;
    value[fu]=(val+value[v]-value[u]+2)%2;
  }
  if(height[fu]==height[fv]) ++height[fu];
}

高精度（输入输出均为逆序字符串）

加/乘 通用模板

//__int128 yyds
string [add@mult](string aa,string bb) {
   
  int cnta=aa.length(),cntb=bb.length(),cntc=[max(cnta,cntb)+1@cnta+cntb+1];
  int a[N],b[N],c[N];
  clr(a,0);clr(b,0);clr(c,0);
  rep(i,0,cnta) a[i]=aa[i]-'0';
  rep(i,0,cntb) b[i]=bb[i]-'0';
  [rep(i,0,cntc) c[i]=a[i]+b[i];@
  rep(i,0,cnta) rep(j,0,cntb) c[i+j]+=a[i]*b[j];]
  ll t=0;
  rep(i,0,cntc) {
   
    c[i]+=t;
    t=c[i]/10;
    c[i]%=10;
  }
  while(c[cntc]==0&&cntc) --cntc;
  string cc;
  rep(i,0,cntc+1) cc+=c[i]+'0';
  return cc;
}

数论

拓展欧几里得

ll exgcd(ll a,ll b,ll &x,ll &y) {
   
  if(!b) return x=1,y=0,a;
  ll t=exgcd(b,a%b,y,x);
  y-=(a/b)*x;
  return t;
}

逆元（拓欧，最小非负整数解，特判）

//qpow(val,p-2)，费马小定理（val的逆元，p为质数）
//i^-1=-p/i*(p%i)^-1
ll inel(ll a,ll b,ll c,ll &x,ll &y) {
   
  ll gcd=exgcd(a,b,x,y);
  if(c%gcd!=0) return 0;
  ll t;
  if(b) {
   
    t=b/gcd;
    x=(x*c/gcd%t+abs(t))%t;
  }
  if(a) {
   
    t=a/gcd;
    y=(y*c/gcd%t+abs(t))%t;
  }
  return gcd;
}

质数

线性欧拉质数筛

bitset<N> notprime;
vec prime;
ll phi[N];
void getprime(ll n) {
   
  phi[1]=1;
  for(ll i=2; i<=n; ++i) {
   
    if(!notprime[i]) {
   
      prime.pb(i);
      phi[i]=i-1;
    }
    for(ll j=0; j<prime.size()&&i*prime[j]<=n; ++j) {
   
      notprime[i*prime[j]]=true;
      if(i%prime[j]==0) {
   
        phi[i*prime[j]]=phi[i]*prime[j];
        break;
      }
      phi[i*prime[j]]=phi[i]*(prime[j]-1);
    }
  }
}

质数个数

ll count(ll x) {
   
  ll ans=0;
  for(ll i=0; i<prime.size()&&prime[i]*prime[i]<=x; ++i) {
   
    for(; x%prime[i]==0; ++ans) x/=prime[i];
  }
  if(x!=1) ++ans;
  return ans;
}

滑动窗口

上界最大字串和

val=mxval=mxl=mxr=0;p=q=1;
while(q<=n)
{
   
    if(val+arr[q]<=m)
    {
   
        val+=arr[q++];
        continue;
    }
    if(val>mxval)
    {
   
        mxl=p;
        mxr=q;
        mxval=val;
    }
    val+=arr[q++];
    while(val>m) val-=arr[p++];
}

动态规划

经典dp

//以i为右边界的最大子串和
dp[i]=max(dp[i-1]+arr[i],arr[i]);
//(i,j)位置时的最长公共子序列，最长回文子序列=a和a的逆序的最长公共子序列
dp[i][j]=dp[i-1][j-1]+1 arr[i]==arr[j]
dp[i][j]=max(dp[i][j-1]+dp[i-1][j]) arr[i]!=arr[j]//删掉这行变成最长公共子串
//dp维护最长不下降子序列
for(ll i=1;i<=n;i++) dp[i]=inf;
for(ll i=1;i<=n;i++) *lower_bound(dp+1,dp+1+n,arr[i])=arr[i];
ans=lower_bound(dp+1,dp+1+n,inf)-(dp+1);

状压dp

位运算

// 获取 a 的第 b 位，最低位编号为 0
int getBit(int a, int b) {
    return (a >> b) & 1; }
// 将 a 的第 b 位设置为 0 ，最低位编号为 0
int unsetBit(int a, int b) {
    return a & ~(1 << b); }
// 将 a 的第 b 位设置为 1 ，最低位编号为 0
int setBit(int a, int b) {
    return a | (1 << b); }
// 将 a 的第 b 位取反 ，最低位编号为 0
int flapBit(int a, int b) {
    return a ^ (1 << b); }
ll lowbit(ll x) {
   return x&(-x);}

内建函数

转自OI Wiki

__builtin_clzll(n)//前导0的个数
63-__builtin_clzll(n);//取对数
64-__builtin_clzll(n);//长度
__builtin_ffsll(n)//末尾最后一个1的位置，位置从1开始
__builtin_ctzll(n)//末尾连续0的个数
__builtin_clrsbll(n)//符号位为0时返回n前导0的个数-1，否则返回前导1的个数-1。
int __builtin_parityll(unsigned int x)//1的个数的奇偶性。
__builtin_popcountll(n);//二进制1的个数

字符串

Trie树

struct node {
   
  ll nxt[26];
} trie[N];
ll cont;

void insert(string s) {
   
  ll p=0;
  for(ll i=0; i<s.length(); ++i) {
   
    ll &to=trie[p].nxt[str[i]-'a'];
    if(to) p=to;
    else {
   
      p=to=++cont;
      memset(trie+p,0,sizeof trie[p]);
    }
  }
}

ll query(string s) {
   
  ll p=0,ans=0;
  for(ll i=0; i<s.length(); ++i) {
   
    ll &to=trie[p].nxt[s[i]-'a'];
    if(to) {
   
      p=to;
      ans+=i位置匹配成功;
    } else 匹配失败;
  }
  ans+=匹配成功;
  return ans;
}

void init() {
   
  memset(trie,0,sizeof trie[0]);
  cont=0;
}

拓展kmp（标准kmp板子？你还没记住？）

//pre[i]为i位置（右开）最长公共前后缀
//if(t[++p]==t[++q]) pre[q]=pre[p]; else pre[q]=p; 优化
//p=pre[p];重叠 p=0;不重叠
//lent-nxt[lent]首尾添加能构成的最小循环节长度
//注意体会与manacher思想的相似性，nxt决定ext，带-x的下标一般是模式串的，为了与主串统一到0下标开始
vec exprekmp(string s) {
   
  ll len=s.length();
  vec nxt(len);
  nxt[0]=len;
  for(ll i=1,l=0,r=0; i<len; ++i) {
   
    if(i+nxt[i-l]>=r) {
   
      if(i>r) r=i;
      while(r<len&&s[r]==s[r-i]) ++r;
      nxt[i]=r-i;
      l=i;
    } else nxt[i]=nxt[i-l];
  }
  return nxt;
}
vec exkmp(string s,string t) {
   
  ll lens=s.length(),lent=t.length();
  vec nxt=exprekmp(t),ext(lens);
  for(ll i=0,l=0,r=0; i<lens; ++i) {
   
    if(i+nxt[i-l]>=r) {
   
      if(i>r) r=i;
      while(r<lens&&s[r]==t[r-i]) ++r;
      ext[i]=r-i;
      l=i;
    } else ext[i]=nxt[i-l];
  }
  return ext;
}

manacher

//?奇下标偶长度，字符偶下标和奇长度，与前一个?结合
//中间位置（右开）=原始下标：i-1>>1;原始长度：len-1>>1
//起始位置：i-rds[i]>>1，结束位置（右开）：i+rds[i]-1>>1;
//回文长度：rds[i]-1；
vec manacher(string raw) {
   
  string s="!?";
  for(auto v:raw) {
   
    s+=v;
    s+='?';
  }
  ll len=s.length();
  vec rds(len);
  for(ll i=0,l=0,r=0; i<len; ++i) {
   
    rds[i]=r>i?min(rds[2*l-i],r-i):1;
    while(s[i+rds[i]]==s[i-rds[i]]) ++rds[i];
    if(i+rds[i]>r) r=i+rds[l=i];
  }
  return rds;
}

图论

遍历

dfs

void dfs(ll now)
{
   
    if(vis[now]) return;
    vis[now]=true;
    for(ll i=0; i<graph[now].size(); i++)
    {
   
        ll nxt=graph[now][i];
        dfs(nxt);
    }
}

bfs

void bfs(ll now)
{
   
    queue<ll> que;
    que.push(now);
    while(!que.empty())
    {
   
        ll t=que.front();
        que.pop();
        if(vis[t]) continue;
        vis[t]=true;
        for(ll i=0; i<graph[t].size(); i++)
        {
   
            ll nxt=graph[t][i];
            que.push(nxt);
        }
    }
}

二分图最大匹配（前向星）

ll hd[N],pre[N];
bitset<N> vis;
ll to[2*N],nxt[2*N];
ll n,m,k,cnt;//n匹配点数量，m被匹配点数量，k边数量
bool dfs(ll u) {
   
  for(ll i=hd[u]; i; i=nxt[i]) {
   
    if(vis[to[i]]) continue;
    vis[to[i]]=true;
    if(!pre[to[i]]||dfs(pre[to[i]])) {
   
      pre[to[i]]=u;
      return true;
    }
  }
  return false;
}
    while(k--) {
   
      ll u,v;
      cin>>u>>v;
      add(u,v+n);
      add(v+n,u);
    }
    ll cnt=0;
    for(ll i=1; i<=n; ++i) {
   
      vis.reset();
      cnt+=dfs(i);
    }
    cout<<cnt<<endl;

最短路径

Dij

邻接矩阵

ll n,s,e;
ll dis[maxn],g[maxn][maxn];
bool vis[maxn];
//g[ta][tb]=g[tb][ta]=min(g[ta][tb],tc);
  dis[s]=0;
  while(s!=e)
  {
   
    ll mindis=inf,idx;
    vis[s]=true;
    rep(i,0,n)
    {
   
      dis[i]=min(dis[i],dis[s]+g[s][i]);
      if(!vis[i]&&dis[i]<mindis) mindis=dis[idx=i];
    }
    if(mindis==inf) break;
    s=idx;
  }
  cout<<dis[e]<<endl;

堆优化+前向星

ll n,m;
ll dis[maxn],hd[maxn];
bool vis[maxn];
ll cnt;
ll to[maxm],w[maxm],nxt[maxm];
ll ta,tb,tc,s,e;
struct node {
   
  ll s,w;
  bool operator<(const node &a)const {
   
    return a.w<w; //与condition()同步
  }
};
priority_queue<node> que;

  //init
  memset(dis,inf,sizeof dis);
  memset(vis,0,sizeof vis);
  memset(hd,0,sizeof hd)//*******WARNING********
  cnt=0;
  //in
  cin>>n>>m;
  rep(i,0,m) {
   
    cin>>ta>>tb>>tc;

    w[++cnt]=tc;
    to[cnt]=tb;
    nxt[cnt]=hd[ta];
    hd[ta]=cnt;
  }
  cin>>s>>e;
  //dij
  dis[s]=0;
  que.push(node{
   s,0});
  while(!que.empty()) {
   
    node t=que.top();
    que.pop();
    if(vis[t.s]) continue;//易忘
    vis[t.s]=true;
    for(ll i=hd[t.s]; i; i=nxt[i]) {
   
      if(dis[t.s]+w[i]<dis[to[i]])//易忘
        //if(condition(stucture(dis[pnt],w[i]),dis[to[i]])) <条件>的<结构> ex. min(dis[pnt],w[i])>dis[to[i]] 最大的路径的边的最小值
      {
   
        dis[to[i]]=dis[t.s]+w[i];
        que.push(node{
   to[i],dis[to[i]]});
      }
    }
  }
  //out
  cout<<dis[e]<<endl;

树

树链剖分+线段树 维护 查询/更新树上路径+更新子树和+单点更新

剖分部分

vector<ll> tree[N];
struct Info
{
   
	ll fa,hson,depth,weight,dfn,top,val;
} info[N];
ll cnt;
ll rankk[N];
void dfsson(ll now,ll depth,ll fa)
{
   
	info[now].depth=depth;
	info[now].weight=1;
	info[now].fa=fa;
	for(ll i=0; i<tree[now].size(); i++)
	{
   
		ll nxt=tree[now][i];
		if(nxt==fa) continue;
		dfsson(nxt,depth+1,now);
		info[now].weight+=info[nxt].weight;
		if(info[nxt].weight>info[info[now].hson].weight) info[now].hson=nxt;
	}

}
void dfsfather(ll now,ll top)
{
   
	info[now].top=top;
	info[now].dfn=++cnt;//dfn第二次更新
	rankk[cnt]=now;
	if(info[now].hson) dfsfather(info[now].hson,top);
	for(ll i=0; i<tree[now].size(); i++)
	{
   
		ll nxt=tree[now][i];
		if(nxt==info[now].fa||nxt==info[now].hson) continue;
		dfsfather(nxt,nxt);
	}
}

线段树部分

#define root tree[rt]
#define sonl tree[rt<<1]
#define sonr tree[rt<<1|1]
struct St
{
   
	ll l,r;
	ll val,lazy;
} st[N<<2];
inline void pushup(ll rt)
{
   
	root.val=lson.val+rson.val;
}
inline void pushdown(ll rt)
{
   
	if(!root.lazy) return;

	lson.val+=root.lazy*(lson.r-lson.l+1);
	rson.val+=root.lazy*(rson.r-rson.l+1);

	lson.lazy+=root.lazy;
	rson.lazy+=rson.lazy;
	root.lazy=0;
}

void build(ll rt,ll l,ll r)
{
   
	root.l=l;
	root.r=r;
	if(l==r)
	{
   
		root.val=info[rankk[l]].val;
		return;
	}
	ll mid=l+r>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	pushup(rt);
}

void update(ll rt,ll l,ll r,ll val)
{
   
	if(root.l>r||root.r<l) return;
	if(root.l>=l&&root.r<=r)
	{
   
		root.val+=val*(root.r-root.l+1);//使用root的l和r！
		root.lazy+=val;
		return;//return！return！return！
	}
	pushdown(rt);
	update(rt<<1,l,r,val);
	update(rt<<1|1,l,r,val);
	pushup(rt);
}
ll query(ll rt,ll l,ll r)
{
   
	if(root.l>r||root.r<l) return 0;
	if(root.l>=l&&root.r<=r) return root.val;
	pushdown(rt);
	return queryone(rt<<1,l,r)+queryone(rt<<1|1,l,r);
}

维护部分

//路径点权和(更新点权类似）
inline ll querypath(ll u,ll v) {
   
   ll ans=0;
   while(info[u].top!=info[v].top) {
   
      if(info[info[u].top].depth<info[info[v].top].depth) swap(u,v);//小于，比较top
      ans+=query(1,info[info[u].top].dfn,info[u].dfn);
      u=info[info[u].top].father;
   }
   if(info[u].dfn>info[v].dfn) swap(u,v);//大于
   ans+=query(1,info[u].dfn,info[v].dfn);
   return ans;
}
//子树点权更新
update(1,info[x].dfn,info[x].dfn+info[x].weight-1,a);

最小生成树（Prim）（邻接矩阵无优化）*

int prim() {
   
  int ans=0;
  vis.reset();
  dis[1]=0;
  vis[1]=true;
  for(int i=1; i<=n; i++) {
   
    dis[i]=graph[1][i];
  }
  for(int i=0; i<n-1; i++) {
   
    int mindis=inf,index;
    for(int j=1; j<=n; j++) {
   
      if(vis[j]==false&&dis[j]<mindis) {
   
        mindis=dis[j];
        index=j;
      }
    }
    ans+=mindis;
    vis[index]=true;
    for(int j=1; j<=n; j++) {
   
      if(vis[j]==false) {
   
        dis[j]=min(graph[index][j],dis[j]);
      }
    }
  }
  return ans;
}

双向链表遍历*

vector<ll> graph[N];
ll n;
void dfs(ll p,ll fa) {
   
  if(graph[p].size()==1) return;//判断叶节点
  for(auto v:graph[p]) {
   
    if(v==fa) continue;
    dfs(v,p);
  }
}
  cin>>n;
  graph[0].push_back(1);
  graph[1].push_back(0);
  for(ll i=0; i<n-1; ++i) {
   
    ll a,b;
    cin>>a>>b;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }
  dfs(1,0);

二叉树

先序遍历+中序遍历->后序遍历（dfs）

int n;
int pre[maxn];
int in[maxn];
bool head;
void build(int la,int ra,int lb,int rb) {
   
  if(la==ra) return;
  if(la+1==ra) {
   
    if(head) {
   
      printf("%d",pre[la]);
      head=false;
    } else printf(" %d",pre[la]);
    return;
  }
  int p=lb;
  while(in[p]!=pre[la]&&p<rb)p++;
  build(la+1,la+1+p-lb,lb,p);
  build(la+1+p-lb,ra,p+1,rb);
  if(head) {
   
    printf("%d",pre[la]);
    head=false;
  } else printf(" %d",pre[la]);
}

  while(~scanf("%d",&n)) {
   
    head=true;
    rep(i,0,n) scanf("%d",&pre[i]);
    rep(i,0,n) scanf("%d",&in[i]);
    build(0,n,0,n);
    puts("");
  }

查询/修改

树状数组*

ll tree[maxn];
void update(ll x,ll v) {
   
  while(x<=n) {
   
    tree[x]+=v;
    x+=lowbit(x);
  }
}
ll getsum(ll x) {
   
  ll ans=0;
  while(x) {
   
    ans+=tree[x];
    x-=lowbit(x);
  }
  return ans;
}
ll query(ll l,ll r) {
   
  return getsum(r)-getsum(l-1);
}

线段树

维护区间和 支持区间加和乘

#define root tree[rt]
#define sonl tree[rt<<1]
#define sonr tree[rt<<1|1]

struct node {
   
  ll l,r,sum,lazyadd,lazymuti;
} tree[N<<2];
ll arr[N];
ll n,m;

void pushup(ll rt) {
   
  root.sum=(sonl.sum+sonr.sum)%mod;
}

void pushdown(ll rt) {
   
  ll mid=root.l+root.r>>1;
  sonl.sum=(sonl.sum*root.lazymuti+root.lazyadd*(mid-root.l+1))%mod;
  sonl.lazymuti=sonl.lazymuti*root.lazymuti%mod;
  sonl.lazyadd=(sonl.lazyadd*root.lazymuti+root.lazyadd)%mod;
  sonr.sum=(sonr.sum*root.lazymuti+root.lazyadd*(root.r-mid))%mod;
  sonr.lazymuti=sonr.lazymuti*root.lazymuti%mod;
  sonr.lazyadd=(sonr.lazyadd*root.lazymuti+root.lazyadd)%mod;
  root.lazymuti=1;
  root.lazyadd=0;
}

void build(ll rt,ll l,ll r) {
   
  root.l=l;
  root.r=r;
  tree[rt].lazymuti=1;
  if(l==r) {
   
    root.sum=arr[l]%mod;
    return ;
  }
  ll mid=root.l+root.r>>1;
  build(rt<<1,root.l,mid);
  build(rt<<1|1,mid+1,root.r);
  pushup(rt);
}

void update(ll rt,ll l,ll r,ll muti,ll add) {
   
  if(l<=root.l&&r>=root.r) {
   
    root.sum=(root.sum*muti+add*(root.r-root.l+1))%mod;
    root.lazymuti=root.lazymuti*muti%mod;
    root.lazyadd=(root.lazyadd*muti+add)%mod;
    return ;
  }
  ll mid=root.l+root.r>>1;
  pushdown(rt);
  if(l<=mid) update(rt<<1,l,r,muti,add);
  if(r>mid) update(rt<<1|1,l,r,muti,add);
  pushup(rt);
}

ll query(ll rt,ll l,ll r) {
   
  if(l<=root.l&&r>=root.r) return root.sum;
  pushdown(rt);
  ll ans=0;
  ll mid=root.l+root.r>>1;
  if(l<=mid) ans=(ans+query(rt<<1,l,r))%mod;
  if(r>mid) ans=(ans+query(rt<<1|1,l,r))%mod;
  return ans;
}

维护两两乘积，支持区间加

struct St
{
   
	ll l,r;
	ll sumone,sumtwo,lazy;
} st[N<<2];
inline void pushup(ll rt)
{
   
	root.sumtwo=(lson.sumtwo+rson.sumtwo)%mod;
	root.sumone=(lson.sumone+rson.sumone)%mod;
}
inline void pushdown(ll rt)
{
   
	if(!root.lazy) return;

	lson.sumtwo=(lson.sumtwo+root.lazy*root.lazy%mod*(lson.r-lson.l+1)%mod+root.lazy*2*lson.sumone)%mod;
	rson.sumtwo=(rson.sumtwo+root.lazy*root.lazy%mod*(rson.r-rson.l+1)%mod+root.lazy*2*rson.sumone)%mod;

	lson.sumone=(lson.sumone+root.lazy*(lson.r-lson.l+1))%mod;
	rson.sumone=(rson.sumone+root.lazy*(rson.r-rson.l+1))%mod;

	lson.lazy=(lson.lazy+root.lazy)%mod;
	rson.lazy=(rson.lazy+root.lazy)%mod;
	root.lazy=0;
}
void build(ll rt,ll l,ll r)
{
   
	root.l=l;
	root.r=r;
	if(l==r)
	{
   
		root.sumone=arr[l];
		root.sumtwo=root.sumone*root.sumone%mod;
		return;
	}
	ll mid=l+r>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	pushup(rt);
}
void update(ll rt,ll l,ll r,ll val)
{
   
	if(root.l>r||root.r<l) return;
	if(root.l>=l&&root.r<=r)
	{
   
		root.sumtwo=(root.sumtwo+val*val%mod*(root.r-root.l+1)%mod+val*2*root.sumone)%mod;
		root.sumone=(root.sumone+val*(root.r-root.l+1))%mod;
		root.lazy=(root.lazy+val)%mod;
		return;
	}
	pushdown(rt);
	update(rt<<1,l,r,val);
	update(rt<<1|1,l,r,val);
	pushup(rt);
}
ll queryone(ll rt,ll l,ll r)
{
   
	if(root.l>r||root.r<l) return 0;
	if(root.l>=l&&root.r<=r) return root.sumone;
	pushdown(rt);
	return (queryone(rt<<1,l,r)+queryone(rt<<1|1,l,r))%mod;
}
ll querytwo(ll rt,ll l,ll r)
{
   
	if(root.l>r||root.r<l) return 0;
	if(root.l>=l&&root.r<=r) return root.sumtwo;
	pushdown(rt);
	return (querytwo(rt<<1,l,r)+querytwo(rt<<1|1,l,r))%mod;
}
ll one=queryone(1,l,r);
ll two=querytwo(1,l,r);
ans=(one*one-two+mod)%mod*invtwo%mod;

扫描线（面积并）

struct scanline {
   
   ll l,r,y,dir;
   bool operator<(const scanline b)const {
   
      return y<b.y;
   }
} line[N];
ll realx[N];
struct node {
   
   ll l,r,sum,cnt;
} tree[(N<<2)+(N<<1)];
ll n;
void pushup(ll rt) {
   
   if(root.cnt) root.sum=realx[root.r+1]-realx[root.l];
   else root.sum=sonl.sum+sonr.sum;
}
void build(ll rt,ll l,ll r) {
   
   root.l=l;
   root.r=r;
   root.sum=root.cnt=0;
   if(l==r) return ;
   ll mid=l+r>>1;
   build(rt<<1,l,mid);
   build(rt<<1|1,mid+1,r);
}
void update(ll rt,scanline t) {
   
   if(realx[root.r+1]<=t.l||realx[root.l]>=t.r) return;
   if(t.l<=realx[root.l]&&t.r>=realx[root.r+1]) {
   
      root.cnt+=t.dir;
      pushup(rt);
      return ;
   }
   update(rt<<1,t);
   update(rt<<1|1,t);
   pushup(rt);
}
inline ll query(ll h) {
   
   return tree[1].sum*h;
}
void solve() {
   
   scanf("%lld",&n);
   for(ll i=1; i<=n; i++) {
   
      ll x1,y1,x2,y2;
      scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
      line[i*2-1]= {
   x1,x2,y1,1};
      line[i*2]= {
   x1,x2,y2,-1};
      realx[i*2-1]=x1;
      realx[i*2]=x2;
   }
   n<<=1;
   sort(line+1,line+1+n);
   sort(realx+1,realx+1+n);
   ll r=unique(realx+1,realx+1+n)-realx-1;
   build(1,1,r-1);
   ll ans=0;
   for(ll i=1; i<n; i++) {
   
      update(1,line[i]);
      ans+=query(line[i+1].y-line[i].y);
   }
   printf("%lld\n",ans);
}

可持久化线段树（暂不支持区间更新）*

#define tinfo ll rt,ll l,ll r
#define sl sonl[rt],l,mid
#define sr sonr[rt],mid+1,r
#define mid (l+r>>1)
const ll M=N*(64-__builtin_clzll(N))+10;

ll arr[N];
ll sonl[M],sonr[M],tree[M],cnt;

ll build(tinfo) {
   
  rt=++cnt;
  if(l==r) {
   
    tree[rt]=arr[l];
    return rt;
  }
  sonl[rt]=build(sl);
  sonr[rt]=build(sr);
  pushup(rt);
  return rt;
}

ll update(tinfo,ll p,ll v) {
   
  ll rtnew=++cnt;
  if(l==r) {
   
    tree[rtnew]=v;
    return cnt;
  }
  if(p<=mid) {
   
    sonl[rtnew]=update(sl,p,v);
    sonr[rtnew]=sonr[rt];
  } else {
   
    sonl[rtnew]=sonl[rt];
    sonr[rtnew]=update(sr,p,v);
  }
  pushup(rtnew);
  return rtnew;
}

稀疏表（Sparse Table）

ll st[20][N];
ll log(ll x) {
   
  return 63-__builtin_clzll(x);
}
void stable() {
   
  ll logn=log(n);
  for(int i=0; i<n; i++)
  st[0][i]=cha[i];
  for(int i=1; i<=logn; i++)
  for(int j=0; j+(1<<i)<=n; j++)//<=号
  st[i][j]=__gcd(st[i-1][j],st[i-1][j+(1<<i-1)]);
}
ll query(ll l,ll r) {
   
  ll logn=log(r-l);
  return __gcd(st[logn][l],st[logn][r-(1<<logn)]);
}