跳转至

个人模板

杂项

快读&O2优化

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define inf1 0x3f3f3f3f
#define inf2 0x3f3f3f3f3f3f3f3f
const double Pi = acos(-1);
std::ios::sync_with_stdio(false);
std::cin.tie(0);
cout<<fixed<<setprecision(20)<<ans<<endl;

read函数快读

inline int read()
{
    int z = 0, flag = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            flag = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        z = z * 10 + ch - '0';
        ch = getchar();
    }
    return z * flag;
}

函数式__int128 输入和输出

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
__int128 int128read()
{
    __int128 x=0;
    int flag=1;
    string a;
    cin>>a;
    for(char c:a)
    {
        if(c=='-')
            flag=-1;
        else
            x=x*10+c-'0';
    }
    return flag*x;
}
void int128print(__int128 x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
        int128print(x/10);
    putchar(x % 10 + '0');
}
int main()
{
    __int128 a=int128read(),b=int128read();
    int128print(a+b);
}

重载式 __int128 输入和输出

#include <bits/stdc++.h>
using namespace std;

istream &operator>>(istream &in, __int128 &x)
{
    x = 0;
    int flag = 1;
    string a;
    in >> a;
    for (char c : a)
    {
        if (c == '-')
            flag = -1;
        else
            x = x * 10 + c - '0';
    }
    x = flag * x;
    return in;
}

ostream &operator<<(ostream &out, __int128 &x)
{
    if (x < 0)
    {
        out << '-';
        x = -x;
    }
    stack<int> s;
    while (x)
    {
        s.push(x % 10);
        x /= 10;
    }
    while (!s.empty())
    {
        out << s.top();
        s.pop();
    }
    return out;
}

int main()
{
    __int128 a, b;
    cin >> a >> b;
    cout << a << ' ' << b << endl;
    return 0;
}

java ACM 基础

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    public static void main(String args[])
    {
        //BigDecimal大数Double类
        //读入
        Scanner cin = new Scanner (new BufferedInputStream(System.in));
        int a; double b; BigInteger c; String d;
        a = cin.nextInt(); b = cin.nextDouble(); c = cin.nextBigInteger(); 
        d = cin.nextLine(); // 每种类型都有相应的输入函数.
        System.out.printf("输入的为%d %f %s %s\n",a,b,c.toString(),d);

        c=cin.nextBigInteger(2); //大数以2进制读入
        String tmp=c.toString(2); ///将大数以二进制形式输出

        System.out.print(1); // cout << …;
        System.out.println(1); // cout << … << endl;
        System.out.printf("%d",1); // 与C中的printf用法类似.

        ///字符串处理
        String st = "abcdefg";
        System.out.println(st.charAt(0)); // st.charAt(i)就相当于st[i].
        char [] ch;
        ch = st.toCharArray(); // 字符串转换为字符数组.
        for (int i = 0; i < ch.length; i++) ch[i] += 1;
        System.out.println(ch); // 输入为“bcdefgh”.
        if (st.startsWith("a")) // 如果字符串以'0'开头.
            st = st.substring(1); // 则从第1位开始copy(开头为第0位).

        ///进制转化
        int num=15,base=2;
        System.out.printf("15转2进制为%s\n",Integer.toString(num, base));
        st="1111";
        System.out.printf("2进制的1111转10进制为%d\n",Integer.parseInt(st, base)); 

        // 把st当做base进制,转成10进制的int(parseInt有两个参数,第一个为要转的字符串,第二个为进制). 
        BigInteger m = new BigInteger(st, base); // st是字符串,base是st的进制.

        ///排序
        int n=cin.nextInt();
        Integer[] arr=new Integer[n];
        for(int i=0;i<n;i++)
            arr[i]=cin.nextInt();

        Arrays.sort(arr,new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;            ///从大到小排序
            }
        });

        for(int i=0;i<n;i++)
            System.out.printf("%d ",arr[i]);
        System.out.println();

        ///清空
        Arrays.fill(arr,5);
        for(int i=0;i<n;i++)
            System.out.printf("%d ",arr[i]);
        System.out.println();

        ///二分查找
        System.out.println(Arrays.binarySearch(arr, 5));
        ///如果key在数组中,则返回搜索值的索引;否则返回-1或者”-“(插入点)。
        ///插入点是索引键将要插入数组的那一点,即第一个大于该键的元素索引。
    }
}

java BigInteger 运算

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {

    public static void main(String args[]) 
    {
        Scanner cin = new Scanner(System.in);
        while (cin.hasNext()) ///相当于 scanf()!=EOF
        { 
            BigInteger a, b, c;

            //大数初始化
            //1.二进制字符串
            BigInteger interNum1 = new BigInteger("1011100111",2);
            //2.十进制字符串
            BigInteger interNum2 = new BigInteger("123456");
            //3.十进制数字
            BigInteger interNum3 = BigInteger.valueOf(8);

            //大数读入
            a = cin.nextBigInteger();
            b = cin.nextBigInteger();

            //基本运算
            //1.把a与b相加并赋给c
            c = a.add(b); 
            //2.把a与b相减并赋给c
            c = a.subtract(b); 
            //3.把a与b相乘并赋给c
            c = a.multiply(b); 
            //4.把a与b相除并赋给c
            c = a.divide(b);
            //5.取模,(需 b > 0,否则出现异常:ArithmeticException("BigInteger: modulus not positive"))
            c = a.mod(b);
            //6.求余
            c = a.remainder(b);
            //7.相当于a^b
            c = a.pow(2); 
            //8.根据该数值是小于、等于、或大于a 返回 -1、0 或 1
            int ans1 = a.compareTo(b);
            //9.判断两数是否相等,也可以用compareTo来代替
            boolean ans2 = a.equals(b); 
            //10.最大值和最小值
            c = a.min(b);
            c = a.max(b);

            //类型转换
            //1.转换为bigNum的二进制补码形式
            byte[] num1 = a.toByteArray(); 
            //2.转换为bigNum的十进制字符串形式
            String num2 = a.toString();    
            //3.转换为bigNum的radix进制字符串形式
            String num3 = a.toString(2);
            //4.将bigNum转换为int
            int num4 = a.intValue();
            //5.将bigNum转换为long
            long num5 = a.longValue();
            //6.将bigNum转换为float
            float num6 = a.floatValue();
            //7.将bigNum转换为double
            double num7 = a.doubleValue();

            //二进制运算
            //1.与:a&b
            BigInteger bigNum1 = a.and(b);
            //2.或:a|b
            BigInteger bigNum2 = a.or(b);
            //3.异或:a^b
            BigInteger bigNum3 = a.xor(b);
            //4.取反:~a
            BigInteger bigNum4 = a.not();
            //5.左移n位: (a << n)
            BigInteger bigNum5 = a.shiftLeft(3);
            //6.右移n位: (a >> n)
            BigInteger bigNum6 = a.shiftRight(3);
        }
    }
}

java BigDecimal 运算

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {

    public static void main(String args[]) 
    {
        Scanner cin = new Scanner(System.in);
        while (cin.hasNext()) ///相当于 scanf()!=EOF
        { 
            BigDecimal a, b, c;

            //大数初始化
            //1.十进制字符串
            BigDecimal interNum1 = new BigDecimal("0.005");
            //2.十进制数字
            BigDecimal interNum2 =new BigDecimal(0.000005);
            BigDecimal interNum3 = BigDecimal.valueOf(0.000005);

            //大数读入
            a = cin.nextBigDecimal();
            b = cin.nextBigDecimal();

            //大数保留小数位输出
            BigDecimal d=a.setScale(10, RoundingMode.HALF_UP);//保留十位小数
            System.out.println(d);

            //基本运算
            //1.把a与b相加并赋给c
            c = a.add(b); 
            //2.把a与b相减并赋给c
            c = a.subtract(b); 
            //3.把a与b相乘并赋给c
            c = a.multiply(b); 
            //4.把a与b相除并赋给c
            c = a.divide(b,10,BigDecimal.ROUND_UP); //舍入远离零的舍入模式。
            c = a.divide(b,10,BigDecimal.ROUND_DOWN); //接近零的舍入模式。
            c = a.divide(b,10,BigDecimal.ROUND_CEILING); //接近正无穷大的舍入模式。
            c = a.divide(b,10,BigDecimal.ROUND_FLOOR); //接近负无穷大的舍入模式。
            c = a.divide(b,10,BigDecimal.ROUND_HALF_UP); //向“最接近的”数字舍入,如果与两个相邻数字的距离相等,则为向上舍入的舍入模式。
            c = a.divide(b,10,BigDecimal.ROUND_HALF_DOWN); //向“最接近的”数字舍入,如果与两个相邻数字的距离相等,则为上舍入的舍入模式。
            c = a.divide(b,10,BigDecimal.ROUND_HALF_EVEN); //向“最接近的”数字舍入,如果与两个相邻数字的距离相等,则向相邻的偶数舍入。
            //5.求余
            c = a.remainder(b);
            //6.相当于a^b
            c = a.pow(2); 
            //7.根据该数值是小于、等于、或大于a 返回 -1、0 或 1
            int ans1 = a.compareTo(b);
            //8.判断两数是否相等,也可以用compareTo来代替
            boolean ans2 = a.equals(b); 
            //9.最大值和最小值
            c = a.min(b);
            c = a.max(b);
            //10.绝对值
            c = a.abs();

            //类型转换
            //1.转换为bigNum的十进制字符串形式
            String num2 = a.toString();
            //2.将bigNum转换为int
            int num4 = a.intValue();
            //3.将bigNum转换为long
            long num5 = a.longValue();
            //4.将bigNum转换为float
            float num6 = a.floatValue();
            //5.将bigNum转换为double
            double num7 = a.doubleValue();
        }
    }
}

判断周几

int getWeek(int y, int m, int d) {
    if (m == 1 || m == 2) { 
        m += 12;     
        y--; 
    } 
    int week = (d +1 + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7;
    return week;
}

组合数奇偶判断

在这里插入图片描述

图论

堆优化prim算法

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
struct node
{
    int to, val;
};
vector<node> v[100500];
struct node1
{
    int now, val;
    bool operator<(const node1 &a) const
    {
        return a.val < val;
    }
};
priority_queue<node1> que;
int dis[100500] = {0};
void prim()
{
    memset(dis, -1, sizeof(dis));
    que.push({1, 0});
    while (!que.empty())
    {
        node1 now = que.top();
        que.pop();
        if (dis[now.now] != -1)
            continue;
        dis[now.now] = now.val;
        for (int i = 0; i < v[now.now].size(); i++)
        {
            int to = v[now.now][i].to;
            int val = v[now.now][i].val;
            if (dis[to] != -1)
                continue;
            que.push({to, val});
        }
    }
}
int main()
{
    int n, m, from, to, val;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &from, &to, &val);
        v[from].push_back({to, val});
        v[to].push_back({from, val});
    }
    prim();
    ll ans = 0;
    for (ll i = 1; i <= n; i++)
    {
        if (dis[i] == -1)
            return 0 * puts("orz"); ///不连通
        ans += dis[i];
    }
    cout << ans << endl;
}

SPFA判断负环

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#define INF 0x3f3f3f3f

using namespace std;
const int MAXN = 5500;
int n,m,w;

struct Edge
{
    int v,w,next;
}edge[MAXN];
int head[MAXN],dis[MAXN],vis[MAXN],t;

void Init()
{
    memset(head,-1,sizeof(head));
    t = 0;
}
void Add_edge(int u,int v,int w)
{
    edge[t].v = v;edge[t].w = w;edge[t].next = head[u];head[u] = t++;
}

bool SPFA()
{
    int mark[MAXN];//记录每个点如队列的次数
    for(int i = 1;i <= n;i ++)
    {
        mark[i] = 0;dis[i] = INF;vis[i] = 0;
    }
    queue<int> q;
    q.push(1);  //我们只需要判断负环,随便找一个起点就好
    dis[1] = 0;
    vis[1] = 1;//入队列
    mark[1] ++;
    while(!q.empty())
    {
        int  u = q.front();
        q.pop();
        vis[u] = 0;//出队列
        for(int i = head[u];i != -1;i = edge[i].next)
        {
            int v = edge[i].v;
            if(dis[v] > dis[u] + edge[i].w)
            {
                dis[v] = dis[u] + edge[i].w;
                if(!vis[v])//不在队列中的时候出队
                {
                    q.push(v);mark[v] ++;vis[v] = 1;
                }
                if(mark[v] >= n)//如果不存在负环,那么最多更新n-1次就可以得到最终的答案,因为一次最少更新一个节点,那么如果出现了更新n次,那么就一定出现了负环
                    return false;
            }
        }
    }
    return true;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        Init();
        int u,v,z;
        scanf("%d%d%d",&n,&m,&w);
        for(int i = 0;i < m;i ++)
        {
            scanf("%d%d%d",&u,&v,&z);
            Add_edge(u,v,z);
            Add_edge(v,u,z);
        }
        for(int i = 0;i < w;i ++)
        {
            scanf("%d%d%d",&u,&v,&z);
            Add_edge(u,v,-z);
        }
        if(!SPFA())
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

dijikastra第k短路

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX = 1005;
int n,m;
int start,end,k;
struct Edge
{
    int w;
    int to;
    int next;
};
Edge e[100005];
int head[MAX],edgeNum;
int dis[MAX];   //dis[i]表示从i点到end的最短距离
bool vis[MAX];
int cnt[MAX];
vector<Edge> opp_Graph[MAX];

struct Node
{
    int f,g;    //f = g+dis[v]
    int v;      //当前到达的节点
    Node(int a, int b,int c):f(a),g(b),v(c){}
    bool operator < (const Node& a) const
    {
        return a.f < f;
    }
};

void addEdge(int from, int to, int w)
{
    e[edgeNum].to = to;
    e[edgeNum].w = w;
    e[edgeNum].next = head[from];
    head[from] = edgeNum++;
}

void dijikastra(int start)
{
    int i;
    memset(vis,0,sizeof(vis));
    for(i = 1; i <= n; i++)
        dis[i] = INF;
    dis[start] = 0;
    priority_queue<Node> que;
    que.push(Node(0,0,start));
    Node next(0,0,0);
    while(!que.empty())
    {
        Node now = que.top();
        que.pop();
        if(vis[now.v])              //从集合T中选取具有最短距离的节点
            continue;
        vis[now.v] = true;          //标记节点已从集合T加入到集合S中
        for(i = 0; i < opp_Graph[now.v].size(); i++)    //更新从源点到其它节点(集合T中)的最短距离
        {
            Edge edge = opp_Graph[now.v][i];
            if(!vis[edge.to] && dis[now.v] + edge.w < dis[edge.to])     //加不加前面的判断无所谓
            {
                dis[edge.to] = dis[now.v] + edge.w;
                next.f = dis[edge.to];
                next.v = edge.to;
                que.push(next);
            }
        }
    }
}

int A_Star()
{
    int i;
    priority_queue<Node> que;
    if(dis[start] == INF)
        return -1;
    que.push(Node(dis[start],0,start));
    Node next(0,0,0);
    while(!que.empty())
    {
        Node now = que.top();
        que.pop();
        cnt[now.v]++;
        if(cnt[end] == k)
            return now.f;
        if(cnt[now.v] > k)
            continue;
        for(i = head[now.v]; i != -1; i = e[i].next)
        {
            next.v = e[i].to;
            next.g = now.g + e[i].w;
            next.f = next.g + dis[e[i].to];
            que.push(next);
        }
    }
    return -1;
}

int main()
{
    int i;
    int from,to,w;
    edgeNum = 0;
    memset(head,-1,sizeof(head));
    memset(opp_Graph,0,sizeof(opp_Graph));
    memset(cnt,0,sizeof(cnt));
    scanf("%d %d",&n,&m);
    Edge edge;
    for(i = 1; i <= m; i++)
    {
        scanf("%d %d %d",&from,&to,&w);
        addEdge(from,to,w);
        edge.to = from;
        edge.w = w;
        opp_Graph[to].push_back(edge);
    }
    scanf("%d %d %d",&start,&end,&k);
    if(start == end)
        k++;
    dijikastra(end);
    int result = A_Star();
    printf("%d\n",result);
    return 0;
}

LCA+ST倍增算法

#include <bits/stdc++.h>
using namespace std;
//lca板子题,求俩个点最短距离
//树上两点最短路径:从根节点出发dis[u]+dis[v]-dis[lca]*2
struct node
{
    int to, next;
};
int tot = 0;
node edge[1000500] = {0};
int head[500500] = {0};
int fa[500500][18] = {0};
int dep[500500] = {0};
void add(int from, int to)
{
    edge[++tot].next = head[from];
    edge[tot].to = to;
    head[from] = tot;
}
void dfs(int now, int fa1)
{
    dep[now] = dep[fa1] + 1;
    fa[now][0] = fa1;
    for (int i = head[now]; i; i = edge[i].next)
    {
        int to = edge[i].to;
        if (to != fa1)
            dfs(to, now);
    }
}
int lca(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    for (int j = 17; j >= 0; j--)
    {
        if (dep[fa[x][j]] >= dep[y])
            x = fa[x][j];
    }
    if (x == y)
        return x;
    for (int j = 17; j >= 0; j--)
    {
        if (fa[x][j] != fa[y][j])
            x = fa[x][j], y = fa[y][j];
    }
    return fa[x][0];
}
int main()
{
    int n, m, s, f, t;
    scanf("%d%d%d", &n, &m, &s); ///s为根节点
    for (int i = 1; i <= n - 1; i++)
    {
        scanf("%d%d", &f, &t);
        add(f, t);
        add(t, f);
    }
    dfs(s, 0);
    for (int j = 1; j <= 17; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
        }
    }
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &f, &t);
        printf("%d\n", lca(f, t));
    }
}

树的直径

#include <bits/stdc++.h>

using namespace std;
struct node
{
    int to,val,next;
};
node edge[200500]={0};
int head[200500]={0};
int cnt=0;
int add_edge(int from,int to,int val)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].val=val;
    head[from]=cnt;
}
int dp[200500][4]={0};
int down[200500]={0};
int up[200500]={0};
int len[200500][3]={0};
int dfs1(int now,int fa)
{
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to,val=edge[i].val;
        if(to==fa)
            continue;
        dfs1(to,now);
        int tmp=dp[to][0]+val;
        if(tmp>dp[now][0])swap(dp[now][0],tmp);
        if(tmp>dp[now][1])swap(dp[now][1],tmp);
        if(tmp>dp[now][2])swap(dp[now][2],tmp);
        down[now]=max(down[now],down[to]);
    }
    down[now]=max(down[now],dp[now][0]+dp[now][1]);
}
int dfs2(int now,int fa)
{
    for(int i=head[now];i;i=edge[i].next)
    {
        if(edge[i].to==fa)
            continue;
        int tem=down[edge[i].to];
        if(tem>len[now][0])
            swap(tem,len[now][0]);
        if(tem>len[now][1])
            swap(tem,len[now][1]);
    }
    for(int i=head[now];i;i=edge[i].next)
    {
        int to=edge[i].to,val=edge[i].val;
        if(to==fa)
            continue;
        if(dp[now][0]==dp[to][0]+val)
        {
            dp[to][3]=max(dp[now][1],dp[now][3])+val;
            up[to]=max(dp[now][2],dp[now][3])+dp[now][1];
        }
        else if(dp[now][1]==dp[to][0]+val)
        {
            dp[to][3]=max(dp[now][0],dp[now][3])+val;
            up[to]=max(dp[now][2],dp[now][3])+dp[now][0];
        }
        else
        {
            dp[to][3]=max(dp[now][0],dp[now][3])+val;
            up[to]=max(dp[now][1],dp[now][3])+dp[now][0];
        }
        if(len[now][0]==down[to])
            up[to]=max(up[to],len[now][1]);
        else
            up[to]=max(up[to],len[now][0]);
        dfs2(to,now);
    }
}
int main()
{
    int n,from,to,val;
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d%d%d",&from,&to,&val);
        add_edge(from,to,val);
        add_edge(to,from,val);
    }
    dfs1(1,-1);
    dfs2(1,-1);
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,up[i]+down[i]);
    cout<<ans<<endl;
}

最大流算法

EK算法:

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
struct node
{
    ll to,val,next;
};
node edge[805]={0};
ll head[205]={0};
ll cnt=0;
ll s=1,e=1;
void add_edge(ll from,ll to,ll val)
{
    edge[cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].val=val;
    head[from]=cnt++;
}
ll pre[205]={0},tag[205]={0},vis[205]={0};
ll bfs()
{
    queue<ll>que;
    memset(tag,0,sizeof(tag));
    memset(pre,0,sizeof(pre));
    memset(vis,0,sizeof(vis));
    que.push(s);
    vis[s]=1;
    while(!que.empty())
    {
        ll now=que.front();
        que.pop();
        for(ll i=head[now];i!=-1;i=edge[i].next)
        {
            ll to=edge[i].to,val=edge[i].val;
            if(!vis[to]&&val>0)
            {
                vis[to]=1;
                pre[to]=now;
                tag[to]=i;
                if(to==e)
                    return 1;
                que.push(to);
            }
        }
    }
    return 0;
}
ll EK()
{
    ll ans=0;
    while(bfs())
    {
        ll min1=inf;
        for(ll i=e;i!=s;i=pre[i])
        {
            min1=min(min1,edge[tag[i]].val);
        }
        for(ll i=e;i!=s;i=pre[i])
        {
            edge[tag[i]].val-=min1;
            edge[tag[i]^1].val+=min1;
        }
        ans+=min1;
    }
    return ans;
}
int main()
{
    ll n,m,from,to,val;
    while(scanf("%lld%lld",&m,&n) == 2&&n){
        e=n;
        cnt=0;
        for(int i=1;i<=n;i++)
            head[i]=-1;
        for(ll i=1;i<=m;i++)
        {
            scanf("%lld%lld%lld",&from,&to,&val);
            add_edge(from,to,val);
            add_edge(to,from,0);
        }
        printf("%lld\n",EK());
    }
}

优化版Dinic算法:

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;

struct Edge
{
    ll from, to, cap, flow, index;
    Edge(ll from, ll to, ll cap, ll flow, ll index) : from(from), to(to), cap(cap), flow(flow), index(index) {}
};

struct Dinic
{
    ll N;
    vector<vector<Edge>> G;
    vector<Edge *> dad;
    vector<ll> Q;
    Dinic(ll N) : N(N), G(N), dad(N), Q(N) {}
    void AddEdge(ll from, ll to, ll cap)
    {
        G[from].push_back(Edge(from, to, cap, 0, G[to].size()));
        if (from == to)
            G[from].back().index++;
        G[to].push_back(Edge(to, from, 0, 0, G[from].size() - 1));
    }
    ll BlockingFlow(ll s, ll t)
    {
        fill(dad.begin(), dad.end(), (Edge *)NULL);
        dad[s] = &G[0][0] - 1;

        ll head = 0, tail = 0;
        Q[tail++] = s;
        while (head < tail)
        {
            ll x = Q[head++];
            for (ll i = 0; i < G[x].size(); i++)
            {
                Edge &e = G[x][i];
                if (!dad[e.to] && e.cap - e.flow > 0)
                {
                    dad[e.to] = &G[x][i];
                    Q[tail++] = e.to;
                }
            }
        }
        if (!dad[t])
            return 0;
        ll totflow = 0;
        for (ll i = 0; i < G[t].size(); i++)
        {
            Edge *start = &G[G[t][i].to][G[t][i].index];
            ll amt = INF;
            for (Edge *e = start; amt && e != dad[s]; e = dad[e->from])
            {
                if (!e)
                {
                    amt = 0;
                    break;
                }
                amt = min(amt, e->cap - e->flow);
            }
            if (amt == 0)
                continue;
            for (Edge *e = start; amt && e != dad[s]; e = dad[e->from])
            {
                e->flow += amt;
                G[e->to][e->index].flow -= amt;
            }
            totflow += amt;
        }
        return totflow;
    }

    ll GetMaxFlow(ll s, ll t)
    {
        ll totflow = 0;
        while (ll flow = BlockingFlow(s, t))
            totflow += flow;
        return totflow;
    }
};

int main()
{
    ll n, m, f, t, v, s, e;
    scanf("%lld%lld", &n, &m);
    scanf("%lld%lld", &s, &e);
    Dinic dinic(n + 10);
    for (ll i = 1; i <= m; i++)
    {
        scanf("%lld%lld%lld", &f, &t, &v);
        dinic.AddEdge(f, t, v);
    }
    printf("%lld\n", dinic.GetMaxFlow(s, e));
}

普通版本dinic:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int N = 5e2 + 7;
const int M = 2e5 + 7;

int head[N], nex[M], ver[M], tot = 1;
ll edge[M];
int n, m, s, t;
ll maxflow;
ll deep[N]; //层级数,其实应该是level
int now[M]; //当前弧优化
queue<int> q;

inline void add(int x, int y, int z)
{ //建正边和反向边
    ver[++tot] = y;
    edge[tot] = z;
    nex[tot] = head[x];
    head[x] = tot;
    ver[++tot] = x;
    edge[tot] = 0;
    nex[tot] = head[y];
    head[y] = tot;
}

inline bool bfs()
{ //在残量网络中构造分层图
    for (int i = 1; i <= n; i++)
        deep[i] = INF;
    while (!q.empty())
        q.pop();
    q.push(s);
    deep[s] = 0;
    now[s] = head[s]; //一些初始化
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        for (int i = head[x]; i; i = nex[i])
        {
            int y = ver[i];
            if (edge[i] > 0 && deep[y] == INF)
            { //没走过且剩余容量大于0
                q.push(y);
                now[y] = head[y]; //先初始化,暂时都一样
                deep[y] = deep[x] + 1;
                if (y == t)
                    return 1; //找到了
            }
        }
    }
    return 0;
}

//flow是整条增广路对最大流的贡献,rest是当前最小剩余容量,用rest去更新flow
ll dfs(int x, ll flow)
{ //在当前分层图上增广
    if (x == t)
        return flow;
    ll ans = 0, k, i;
    for (i = now[x]; i && flow; i = nex[i])
    {
        now[x] = i; //当前弧优化(避免重复遍历从x出发的不可拓展的边)
        int y = ver[i];
        if (edge[i] > 0 && (deep[y] == deep[x] + 1))
        {                                   //必须是下一层并且剩余容量大于0
            k = dfs(y, min(flow, edge[i])); //取最小
            if (!k)
                deep[y] = INF; //剪枝,去掉增广完毕的点
            edge[i] -= k;      //回溯时更新
            edge[i ^ 1] += k;  //成对变换
            ans += k;
            flow -= k;
        }
    }

    return ans;
}

void dinic()
{
    while (bfs())
        maxflow += dfs(s, INF);
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &s, &t);
    tot = 1;
    for (ll i = 1; i <= m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    dinic();
    printf("%lld\n", maxflow);
    return 0;
}

最小费用最大流算法

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
struct node
{
    int next;
    int flow;
    int dis;
    int to;
};
int head[100500]= {0};
node edge[100500]= {0};
int dis[100500]= {0};
int pre[100500]= {0};
int vis[100500]= {0};
int last[100500]= {0};
int flow[100500]={0};
char g[1000][1000]= {0};
int n,m,s,t,cnt=-1,maxflow=0,mincost=0;
int num(int i,int j)
{
    return i*m+j;
}
int add(int from,int to,int flow,int dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].flow=flow;
    edge[cnt].dis=dis;
    head[from]=cnt;
}
queue<int>w;
bool spfa(int start,int end1)
{
    w.push(start);
    memset(dis,0x3f3f3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memset(flow,0x3f3f3f,sizeof(flow));
    pre[end1]=-1;
    vis[start]=1;
    dis[start]=0;
    while(!w.empty())
    {
        int now=w.front();
        w.pop();
        vis[now]=0;
        for(int i=head[now]; i!=-1; i=edge[i].next)
        {
            //cout<<i<<endl;
            if(edge[i].flow>0&&dis[edge[i].to]>dis[now]+edge[i].dis)
            {
                dis[edge[i].to]=dis[now]+edge[i].dis;
                pre[edge[i].to]=now;
                last[edge[i].to]=i;
                flow[edge[i].to]=min(flow[now],edge[i].flow);
                if(!vis[edge[i].to])
                {
                    vis[edge[i].to]=1;
                    w.push(edge[i].to);
                }
            }
        }
    }
    return pre[end1]!=-1;
}
int MCMF()
{
    while(spfa(s,t))
    {
        maxflow+=flow[t];
        mincost+=dis[t]*flow[t];
        int now=t;
        while(now!=s)
        {
            edge[last[now]].flow-=flow[t];
            edge[last[now]^1].flow+=flow[t];
            now=pre[now];
        }
    }
}
int main()
{
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    s=n*m+200,t=n*m+100;
    for(int i=1; i<=n; i++)
    {
        scanf("%s",g[i]+1);
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(g[i][j]=='x')
                continue;
            if(j>1&&g[i][j-1]!='x')
            {
                add(num(i,j),num(i,j-1),1,1);
                add(num(i,j-1),num(i,j),0,-1);
            }
            if(i>1&&g[i-1][j]!='x')
            {
                add(num(i,j),num(i-1,j),1,1);
                add(num(i-1,j),num(i,j),0,-1);
            }
            if(j<m&&g[i][j+1]!='x')
            {
                add(num(i,j),num(i,j+1),1,1);
                add(num(i,j+1),num(i,j),0,-1);
            }
            if(i<n&&g[i+1][j]!='x')
            {
                add(num(i,j),num(i+1,j),1,1);
                add(num(i+1,j),num(i,j),0,-1);
            }
            if(g[i][j]=='F')
            {
                add(s,num(i,j),2,0);
                add(num(i,j),s,0,0);
            }
            if(g[i][j]=='C'||g[i][j]=='B')
            {
                add(num(i,j),t,1,0);
                add(t,num(i,j),0,0);
            }
        }
    }
    MCMF();
   // cout<<maxflow<<" "<<mincost<<endl;
    if(maxflow!=2)
        printf("-1\n");
    else
        printf("%d\n",mincost);
}

二分图模板

题意:给你n个长度相同,包含字母种类相同,每种字母数量相同,让你确定一个字符串集合,集合中的任意一个串不能通过交换任意两个不同的位置变成集合中的另一个串,问你集合最大有多个字符串。

思路:

我们对于两个一次操作(交换两个不同位置)不能互相变换的串建边,那么答案就是这个图的最大团。 一个图的最大团等于这个图补图的最大独立集,那么我们要建这个图的补图。 这个图的补图就是对能够一次操作互相变换的两个串建边。 那么现在答案就是这个补图的最大独立集。 这个补图一定是一个二分图。 二分图的最大独立集等于图中点的个数 - 最大匹配数。 所以我们现在可以对这个二分图求一个最大匹配。

#include <bits/stdc++.h>

using namespace std;
char a[1000][300] = {0};
int mp[1000][1000] = {0};
map<int, int> mp1, vis;
int n;
int dfs(int k)
{
    for (int i = 1; i <= n; i++)
    {
        if (mp[i][k] &&!vis[i])
        {
            vis[i] = 1;
            if (mp1[i] == 0 || dfs(mp1[i]))
            {
                mp1[i] = k;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    scanf("%d", &n);  ///两个字符串中不能有两个字符相同,问至少需要分为多少组
    for (int i = 1; i <= n; i++)
        scanf("%s", a[i] + 1);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            int sum = 0;
            for (int k = 1; a[i][k]; k++)
            {
                if (a[i][k] != a[j][k])
                    sum++;
            }
            if (sum == 2)
                mp[i][j] = 1;
        }
    }
    //cout<<mp[1][2]<<endl;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        vis.clear();
        ans += dfs(i);
    }
    cout << n - ans / 2 << endl;
}

二分图判断

#include <bits/stdc++.h>
using namespace std;
vector<int> v[100500];
int color[100500] = {0};
int bfs(int i)
{
    queue<int> que;
    que.push(i);
    while (!que.empty())
    {
        int now = que.front();
        que.pop();
        for (int i : v[now])
        {
            if (color[i] == 0)
            {
                color[i] = 3 - color[now];
                que.push(i);
            }
            else
            {
                if (color[i] == color[now])
                    return 0;
            }
        }
    }
    return 1;
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int from, to;
        scanf("%d %d", &from, &to);
        v[from].push_back(to);
        v[to].push_back(from);
    }
    for (int i = 1; i <= m; i++)
    {
        if (color[i] == 0)
        {
            int tmp = bfs(i);
            if (tmp == 0)
            {
                puts("No");
                return 0;
            }
        }
    }
    puts("Yes");
}
/*
输入:
7 6
1 2
1 3
2 4
2 5
3 6
3 7
输出:
Yes
输入:
3 3
1 2
2 3
1 3
输出:
No
*/

二分图最大匹配

#include <bits/stdc++.h>
using namespace std;
vector<int> v[100500];
map<int, int> mp, vis, mp1;
int dfs(int now)
{
    for (int i = 0; i < v[now].size(); i++)
    {
        int to = v[now][i];
        if (!vis[to])
        {
            vis[to] = 1;
            if (mp[to] == 0 || dfs(mp[to]))
            {
                mp[to] = now;
                mp1[now] = to;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    int n1, n2, m;
    scanf("%d%d%d", &n1, &n2, &m);
    int from, to;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &from, &to);
        to += n1;
        v[from].push_back(to);
        v[to].push_back(from);
    }
    int ans = 0;
    for (int i = 1; i <= n1; i++)
    {
        vis.clear();
        ans += dfs(i);
    }
    cout << ans << endl;
    for (int i = 1; i <= n1; i++)
        cout << max(0,mp1[i]-n1) << ' ';
}

二分图最大独立集:

选最多的点,满足两两之间没有边相连。

二分图中,最大独立集 =n- 最大匹配。

二分图最小点覆盖:

选最少的点,满足每条边至少有一个端点被选,不难发现补集是独立集。

二分图中,最小点覆盖 =n- 最大独立集。

二分图有向无向建图规则:

有左右之分建单向边,无左右之分建无向边 答案除2

一切树均为二分图

二分图最大权匹配:

题目:https://uoj.ac/problem/80

题解:https://blog.csdn.net/weixin_30528371/article/details/99263983

讲解:https://www.cnblogs.com/wenruo/p/5264235.html

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n, m, q;
int w[405] = {0}, v[405] = {0};
int vl[405] = {0}, vr[405] = {0}, c[405] = {0};
int a[405][405] = {0}, ans[405] = {0}, b[405] = {0};
int tim = 0;
int dfs(int x)
{
    vl[x] = tim;
    for (int i = 1; i <= m; i++)
    {
        if (vr[i] == tim)
            continue;
        int d = w[x] + v[i] - a[x][i];
        if (d == 0)
        {
            vr[i] = tim;
            if (!b[i] || dfs(b[i]))
            {
                b[i] = x;
                return 1;
            }
        }
        else
        {
            c[i] = min(c[i], d);
        }
    }
    return 0;
}
void km()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            w[i] = max(w[i], a[i][j]);
    for (int i = 1; i <= n; i++)
    {
        memset(c, inf, sizeof(c));
        tim += 1;
        if (dfs(i))
            continue;

        while (1)
        {
            int d = inf, y = 0;
            for (int j = 1; j <= m; j++)
                if (vr[j] != tim)
                    d = min(d, c[j]);

            for (int j = 1; j <= n; j++)
                if (vl[j] == tim)
                    w[j] -= d;

            for (int j = 1; j <= m; j++)
            {
                if (vr[j] == tim)
                    v[j] += d;
                else if (!(c[j] -= d))
                    y = j;
            }

            if (!b[y])
                break;

            int x = b[y];
            vl[x] = vr[y] = tim;
            for (int j = 1; j <= m; j++)
                c[j] = min(c[j], w[x] + v[j] - a[x][j]);
        }
        tim += 1;
        dfs(i);
    }
    ll ans1 = 0;
    for (int i = 1; i <= m; i++)
        ans1 += a[b[i]][i];
    printf("%lld\n", ans1);
    for (int i = 1; i <= m; i++)
    {
        if (a[b[i]][i])
            ans[b[i]] = i;
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", ans[i]);
}
int main()
{
    scanf("%d%d%d", &n, &m, &q);
    m = max(m, n);
    for (int i = 1; i <= q; i++)
    {
        int x, y, v;
        scanf("%d%d%d", &x, &y, &v);
        a[x][y] = v;
    }
    km();
}

Tarjan算法

Tarjan 算法及其应用

  1. 求割边
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
struct node
{
    int to, next;
};
node edge[200500] = {0};
int head[200500] = {0}, dfn[200500] = {0}, low[200500] = {0}, bridge[200500] = {0};
int cnt = 1, tot = 0;
void add_edge(int from, int to)
{
    edge[++cnt] = {to, head[from]};
    head[from] = cnt;
}
void tarjan(int x, int in_edge)
{
    dfn[x] = low[x] = ++tot;
    for (int i = head[x]; i; i = edge[i].next)
    {
        int y = edge[i].to;
        if (!dfn[y])
        {
            tarjan(y, i);
            low[x] = min(low[x], low[y]);
            if (low[y] > dfn[x])
                bridge[i] = bridge[i ^ 1] = 1; ///桥
        }
        else if (i != (in_edge ^ 1))
            low[x] = min(low[x], dfn[y]);
    }
}
int main()
{
    int n, m, from, to;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &from, &to);
        add_edge(from, to);
        add_edge(to, from);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!dfn[i])
            tarjan(i, 0);
    }
    for (int i = 2; i <= cnt; i += 2)
    {
        if (bridge[i])
        {
            printf("%d %d\n", edge[i ^ 1].to, edge[i].to);
        }
    }
}
  1. 缩点求将图转变为强连通图需要加边的数目

题目来源:POJ 2767

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
struct node
{
    int to, next;
};
node edge[200500] = {0};
int head[200500] = {0}, dfn[200500] = {0}, low[200500] = {0};
int stack1[200500] = {0}, vis[200500] = {0}, color[200500] = {0};
bool in[200500] = {0}, out[200500] = {0};
int cnt = 0, tot = 0, top = 0, color_num = 0;
void add_edge(int from, int to)
{
    edge[++cnt] = {to, head[from]};
    head[from] = cnt;
}
void tarjan(int now)
{
    stack1[++top] = now;
    vis[now] = 1;
    dfn[now] = low[now] = ++tot;
    for (int i = head[now]; i; i = edge[i].next)
    {
        int y = edge[i].to;
        if (!dfn[y])
        {
            tarjan(y);
            low[now] = min(low[now], low[y]);
        }
        else if (vis[y])
            low[now] = min(low[now], dfn[y]);
    }
    if (dfn[now] == low[now]) ///强连通块
    {
        color[now] = ++color_num;
        vis[now] = 0;
        while (stack1[top] != now)
        {
            color[stack1[top]] = color_num;
            vis[stack1[top--]] = 0;
        }
        vis[stack1[top]] = 0;
        top--;
    }
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, m, from, to;
        scanf("%d%d", &n, &m);
        for (int i = 0; i <= n + 1; i++)
            in[i] = out[i] = head[i] = dfn[i] = low[i] = stack1[i] = vis[i] = color[i] = 0;
        cnt = 0, tot = 0, top = 0, color_num = 0;
        for (int i = 1; i <= m; i++)
        {
            scanf("%d%d", &from, &to);
            add_edge(from, to);
        }
        for (int i = 1; i <= n; i++)
        {
            if (!dfn[i])
                tarjan(i);
        }
        if (color_num == 1)
        {
            printf("0\n");
            continue;
        }
        int in_num = color_num, out_num = color_num;
        for (int i = 1; i <= n; i++)
        {
            for (int j = head[i]; j; j = edge[j].next)
            {
                int to = edge[j].to;
                if (color[to] != color[i])
                {
                    if (!in[color[to]])
                    {
                        in_num--;
                        in[color[to]] = 1;
                    }
                    if (!out[color[i]])
                    {
                        out_num--;
                        out[color[i]] = 1;
                    }
                }
            }
        }
        printf("%d\n", max(out_num, in_num));
    }
}
  1. 求割点
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
struct node
{
    int to, next;
};
node edge[200500] = {0};
int head[200500] = {0}, dfn[200500] = {0}, low[200500] = {0}, cut[200500] = {0};
int cnt = 0, tot = 0;
void add_edge(int from, int to)
{
    edge[++cnt] = {to, head[from]};
    head[from] = cnt;
}
void tarjan(int now, int root)
{
    dfn[now] = low[now] = ++tot;
    int ct = 0;
    for (int i = head[now]; i; i = edge[i].next)
    {
        int y = edge[i].to;
        ct++;
        if (!dfn[y])
        {
            tarjan(y, root);
            low[now] = min(low[now], low[y]);
            if (now != root && low[y] >= dfn[now])
                cut[now] = 1;
            if (now == root && ct > 1)
                cut[now] = 1;
        }
        else
            low[now] = min(low[now], dfn[y]);
    }
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, m, from, to;
        scanf("%d%d", &n, &m);
        for (int i = 0; i <= n + 1; i++)
            head[i] = dfn[i] = low[i] = cut[i] = 0;
        cnt = 0, tot = 0;
        for (int i = 1; i <= m; i++)
        {
            scanf("%d%d", &from, &to);
            add_edge(from, to);
            add_edge(to, from);
        }
        for (int i = 1; i <= n; i++)
        {
            if (!dfn[i])
                tarjan(i, i);
        }
        for (int i = 1; i <= n; i++)
        {
            if (cut[i])
                printf("%d ", i);
        }
        printf("\n");
    }
}
/*
输入:
1
7 7
1 2
1 5
5 6
5 7
2 3
2 4
3 4
割点为:
1 2 5 
*/

树链剖分+线段树

https://oi-wiki.org/graph/hld/#_4

HLD

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll sum[400500] = {0}, lazy[400500] = {0};
ll dep[200500] = {0}, size1[200500] = {0}, son[200500] = {0}, f[200500] = {0}, id[200500] = {0}, top[200500] = {0};
struct node
{
    ll to, next;
};
node edge[400500] = {0};
ll head[400500] = {0};
ll num = 0, cnt = 0;
void add_edge(ll from, ll to)
{
    edge[++num] = {to, head[from]};
    head[from] = num;
}
void dfs1(ll now, ll fa)
{
    size1[now] = 1;
    for (ll i = head[now]; i; i = edge[i].next)
    {
        ll to = edge[i].to;
        if (to == fa)
            continue;
        f[to] = now;
        dep[to] = dep[now] + 1;
        dfs1(to, now);
        size1[now] += size1[to];
        if (size1[to] > size1[son[now]])
            son[now] = to;
    }
}
void dfs2(ll now, ll fa)
{
    id[now] = ++cnt;
    top[now] = fa;
    if (son[now])
        dfs2(son[now], fa);
    for (ll i = head[now]; i; i = edge[i].next)
    {
        ll to = edge[i].to;
        if (to == f[now] || to == son[now])
            continue;
        dfs2(to, to);
    }
}
void push_down(ll t, ll l, ll r)
{
    if (lazy[t] == 0)
        return;
    lazy[2 * t + 1] += lazy[t];
    lazy[2 * t] += lazy[t];
    ll mid = (l + r) / 2;
    sum[2 * t] += (mid - l + 1) * lazy[t];
    sum[2 * t + 1] += (r - mid) * lazy[t];
    lazy[t] = 0;
}
void push_up(ll t)
{
    sum[t] = sum[2 * t] + sum[2 * t + 1];
}
void update(ll t, ll l, ll r, ll L, ll R, ll add)
{
    if (l <= L && R <= r)
    {
        lazy[t] += add;
        sum[t] += add * (R - L + 1);
        return;
    }
    push_down(t, L, R);
    ll mid = (L + R) / 2;
    if (l <= mid)
        update(2 * t, l, r, L, mid, add);
    if (mid < r)
        update(2 * t + 1, l, r, mid + 1, R, add);
    push_up(t);
}
ll query(ll t, ll l, ll r, ll L, ll R)
{
    if (l <= L && R <= r)
        return sum[t];
    push_down(t, L, R);
    ll mid = (L + R) / 2;
    ll ans = 0;
    if (l <= mid)
        ans += query(2 * t, l, r, L, mid);
    if (mid < r)
        ans += query(2 * t + 1, l, r, mid + 1, R);
    return ans;
}
void update_chain(ll x, ll y)
{
    ll fx = top[x], fy = top[y];
    while (fx != fy) ///不在同一条重链上
    {
        if (dep[fx] < dep[fy])
            swap(x, y), swap(fx, fy);
        update(1, id[fx], id[x], 1, cnt, 1);
        x = f[fx], fx = top[x]; ///跳转到另一条重链
    }
    if (id[x] > id[y])
        swap(x, y);
    update(1, id[x] + 1, id[y], 1, cnt, 1);
}
ll query_chain(ll x, ll y)
{
    ll fx = top[x], fy = top[y], ans = 0;
    while (fx != fy) ///不在同一条重链上
    {
        if (dep[fx] < dep[fy])
            swap(x, y), swap(fx, fy);
        ans += query(1, id[fx], id[x], 1, cnt);
        x = f[fx], fx = top[x]; ///跳转到另一条重链
    }
    if (id[x] > id[y])
        swap(x, y);
    ans += query(1, id[x] + 1, id[y], 1, cnt);
    return ans;
}
int main()
{
    ll n, m, from, to;
    scanf("%lld%lld", &n, &m);
    for (ll i = 1; i <= n - 1; i++)
    {
        scanf("%lld%lld", &from, &to);
        add_edge(from, to);
        add_edge(to, from);
    }
    f[1] = 0, dep[1] = 1;
    dfs1(1, 0), dfs2(1, 1);
    char c[10];
    for (ll i = 1; i <= m; i++)
    {
        scanf("%s%lld%lld", c + 1, &from, &to);
        if (c[1] == 'P')
            update_chain(from, to);
        else
            printf("%lld\n", query_chain(from, to));
    }
}

分层最短路

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int N = 100000 + 5;
const int K = 10 + 5;
const ll inf = 0x3f3f3f3f3f3f3f3f;

vector< pii > e[N];

struct Info {
    int pos, num;
    ll val;
    inline Info(){}
    inline Info(int _pos, int _num, ll _val) {
        pos = _pos, num = _num, val = _val;
    }
    inline bool operator < (const Info & b) const {
        return val > b.val;
    }
};

ll f[N][K];
bool vis[N][K];
priority_queue<Info> q;

class TaskL {
public:
    void solve(std::istream& in, std::ostream& out) {
        int T;
        in >> T;
        while (T--) {
            int n, m, k;
            in >> n >> m >> k;
            while (q.size()) q.pop();
            for (int i = 1; i <= n; ++i) {
                e[i].clear();
                for (int j = 0; j <= k; ++j) {
                    f[i][j] = inf;
                    vis[i][j] = false;
                }
            }
            for (int i = 1, x, y, z; i <= m; ++i) {
                in >> x >> y >> z;
                e[x].push_back({y, z});
            }
            f[1][0] = 0;
            q.push(Info(1, 0, 0));
            while (q.size()) {
                Info now = q.top(); q.pop();
                if (vis[now.pos][now.num] == true) continue;
                vis[now.pos][now.num] = true;
                for (int i = 0; i < e[now.pos].size(); ++i) {
                    int to = e[now.pos][i].first, val = e[now.pos][i].second;
                    if (f[to][now.num] > f[now.pos][now.num] + val) {
                        f[to][now.num] = f[now.pos][now.num] + val;
                        q.push(Info(to, now.num, f[to][now.num]));
                    }
                    if (now.num < k && f[to][now.num + 1] > f[now.pos][now.num]) {
                        f[to][now.num + 1] = f[now.pos][now.num];
                        q.push(Info(to, now.num + 1, f[to][now.num + 1]));
                    }
                }
            }
            ll ans = inf;
            for (int i = 0; i <= k; ++i) {
                ans = min(ans, f[n][i]);
            }
            out << ans << endl;
        }
    }
};


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    TaskL solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}

LCT 动态树

参考链接:

https://www.luogu.com.cn/problem/P3690

https://www.cnblogs.com/zwfymqz/p/7896036.html#!comments

https://www.cnblogs.com/zzy2005/p/10312977.html

https://www.cnblogs.com/JeremyGJY/p/5921594.html

https://blog.csdn.net/qq_36551189/article/details/79152612

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[100500] = {0}, c[100500][2] = {0}, v[100500] = {0}, s[100500] = {0}, st[100500] = {0};
bool r[100500] = {0};
//判断节点是否为一个Splay的根
inline bool nroot(register ll x)
{
    return c[f[x]][0] == x || c[f[x]][1] == x;
    //原理为如果连的是轻边,他的父亲的儿子里没有它
}
//上传信息
inline void pushup(ll x)
{
    s[x] = s[c[x][0]] ^ s[c[x][1]] ^ v[x];
}
//翻转操作
inline void pushr(register ll x)
{
    register ll t = c[x][0];
    c[x][0] = c[x][1];
    c[x][1] = t;
    r[x] ^= 1;
}
//判断并释放懒标记
inline void pushdown(register ll x)
{
    if (r[x])
    {
        if (c[x][0])
            pushr(c[x][0]);
        if (c[x][1])
            pushr(c[x][1]);
        r[x] = 0;
    }
}
//一次旋转
inline void rotate(register ll x)
{
    register ll y = f[x], z = f[y], k = c[y][1] == x, w = c[x][!k];
    if (nroot(y))
        c[z][c[z][1] == y] = x;
    c[x][!k] = y;
    c[y][k] = w;
    if (w)
        f[w] = y;
    f[y] = x;
    f[x] = z;
    pushup(y);
}
//只传了一个参数,因为所有操作的目标都是该Splay的根
inline void splay(register ll x)
{
    register ll y = x, z = 0;
    st[++z] = y; //st为栈,暂存当前点到根的整条路径,pushdown时一定要从上往下放标记
    while (nroot(y))
        st[++z] = y = f[y];
    while (z)
        pushdown(st[z--]);
    while (nroot(x))
    {
        y = f[x];
        z = f[y];
        if (nroot(y))
            rotate((c[y][0] == x) ^ (c[z][0] == y) ? x : y);
        rotate(x);
    }
    pushup(x);
}
//访问
inline void access(register ll x)
{
    for (register ll y = 0; x; x = f[y = x])
        splay(x), c[x][1] = y, pushup(x);
}
//换根
inline void makeroot(register ll x)
{
    access(x);
    splay(x);
    pushr(x);
}
//找根(在真实的树中的)
inline ll findroot(register ll x)
{
    access(x);
    splay(x);
    while (c[x][0])
        pushdown(x), x = c[x][0];
    splay(x);
    return x;
}
//提取路径
inline void split(register ll x, register ll y)
{
    makeroot(x);
    access(y);
    splay(y);
}
//连边
inline void link(register ll x, register ll y)
{
    makeroot(x);
    if (findroot(y) != x)
        f[x] = y;
}
//断边
void cut(register ll x, register ll y)
{
    makeroot(x);
    if (findroot(y) == x && f[y] == x && !c[y][0])
    {
        f[y] = c[x][1] = 0;
        pushup(x);
    }
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) //给定 n 个点以及每个点的权值
        scanf("%d", &v[i]);
    for (int i = 1; i <= m; i++)
    {
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        if (opt == 0) //代表询问从 x 到 y 的路径上的点的权值的 xor 和。保证 x 到 y 是联通的。
        {
            split(x, y);
            printf("%d\n", s[y]);
        }
        else if (opt == 1) //代表连接 x 到 y,若 x 到 y 已经联通则无需连接。
        {
            link(x, y);
        }
        else if (opt == 2) //代表删除边 (x,y),不保证边 (x,y) 存在。
        {
            cut(x, y);
        }
        else if (opt == 3) //代表将点 x 上的权值变成 y。
        {
            splay(x);
            v[x] = y;
        }
    }
}

数据结构

树状数组前缀和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
ll a[100500]={0};
ll c[100500]={0};
ll lowbit(ll x)
{
    return x&(-x);
}
ll update(ll k,ll x)
{
    for(ll i=k;i<=n;i+=lowbit(i))
        c[i]+=x;
}
ll sum1(ll k)
{
    ll ans=0;
    for(ll i=k;i>=1;i-=lowbit(i))
        ans+=c[i];
    return ans;
}
int main()
{
    ll a1,b1,c1;
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=m;i++)
    {
        scanf("%lld%lld%lld",&a1,&b1,&c1);
        if(a1==0)
            update(b1,c1);
        else
            printf("%lld\n",sum1(c1)-sum1(b1-1));
    }
}

线段树维护区间和

#include <stdio.h>
using namespace std;
typedef long long ll;
ll num[100500]={0};
ll lazy[800500]={0};
ll sum[800500]={0};
void push_up(ll t)
{
    sum[t]=sum[2*t]+sum[2*t+1];
}
void push_down(ll t,ll l,ll r)
{
    if(lazy[t]==0)
        return ;
    lazy[2*t]+=lazy[t];
    lazy[2*t+1]+=lazy[t];
    ll mid=(l+r)/2;
    sum[2*t]+=lazy[t]*(mid-l+1);
    sum[2*t+1]+=lazy[t]*(r-mid);
    lazy[t]=0;
}
void build(ll t,ll l,ll r)
{
    if(l==r)
    {
        sum[t]=num[l];
        return ;
    }
    ll mid=(l+r)/2;
    build(2*t,l,mid);
    build(2*t+1,mid+1,r);
    push_up(t);
}
void update(ll t,ll l,ll r,ll L,ll R,ll add) ///l,r为更新区间,L,R为线段树区间
{
    if(l<=L&&r>=R)
    {
        sum[t]+=add*(R-L+1);
        lazy[t]+=add;
        return ;
    }
    push_down(t,L,R);
    ll mid=(L+R)/2;
    if(l<=mid)
        update(2*t,l,r,L,mid,add);
    if(mid<r)
        update(2*t+1,l,r,mid+1,R,add);
    push_up(t);
}
ll query_sum(ll t,ll l,ll r,ll L,ll R) ///l,r为更新区间,L,R为线段树区间
{
    if(l<=L&&r>=R)
    {
        return sum[t];
    }
    push_down(t,L,R);
    ll mid=(L+R)/2,sum=0;
    if(l<=mid)
        sum+=query_sum(2*t,l,r,L,mid);
    if(mid<r)
        sum+=query_sum(2*t+1,l,r,mid+1,R);
    return sum;
}
int main()
{
    ll n,m;
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&num[i]);
    build(1,1,n);
    char s[10];
    ll l,r,x;
    for(ll i=1;i<=m;i++)
    {
        scanf("%s%lld%lld",s,&l,&r);
        if(s[0]=='Q')
        {
            printf("%lld\n",query_sum(1,l,r,1,n));
        }
        else
        {
            scanf("%lld",&x);
            update(1,l,r,1,n,x);
        }
    }
}

划分树求中位数

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>

using namespace std;
int tree[20][100500]={0};
int to[20][100500]={0};
int num[100500]={0};
int sorted[100500]={0};
int build(int l,int r,int deep)
{
    if(l==r)
        return 0;
    int mid=(l+r)/2;
    int midd=sorted[mid];
    int suppose=mid-l+1;
    for(int i=l;i<=r;i++)
    {
        if(tree[deep][i]<midd)
            suppose--;
    }
    int sleft=l,sright=mid+1;
    for(int i=l;i<=r;i++)
    {
        if(i==l)
            to[deep][l]=0;
        else
            to[deep][i]=to[deep][i-1];
        if(tree[deep][i]<midd)
        {
            to[deep][i]++;
            tree[deep+1][sleft++]=tree[deep][i];
        }
        else if(tree[deep][i]==midd&&suppose>0)
        {
            suppose--;
            to[deep][i]++;
            tree[deep+1][sleft++]=tree[deep][i];
        }
        else
        {
            tree[deep+1][sright++]=tree[deep][i];
        }
    }
    build(l,mid,deep+1);
    build(mid+1,r,deep+1);
}
int query(int l,int r,int L,int R,int k,int deep)
{
    if(L==R)
        return tree[deep][L];
    int mid=(l+r)/2;
    int lef;
    int toleft;
    if(l==L)
        lef=0,toleft=to[deep][R];
    else
        lef=to[deep][L-1],toleft=to[deep][R]-lef;
    if(k<=toleft)
    {
        return query(l,mid,l+lef,l+toleft+lef-1,k,deep+1);
    }
    else
    {
        return query(mid+1,r,mid+L-l-lef+1,mid+R-l-toleft-lef+1,k-toleft,deep+1);
    }
}
int main()
{
    int n,m,summ=0;
    while(scanf("%d",&n)!=EOF)
    {
        summ++;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&num[i]);
            sorted[i]=num[i];
            tree[0][i]=num[i];
        }
        sort(sorted+1,sorted+n+1);
        build(1,n,0);
        printf("Case %d:\n",summ);
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            int a,b,c; /// a,b,c代表查询a到b区间内第c大的数
            scanf("%d%d",&a,&b);
            c=(b-a)/2+1;
            printf("%d\n",query(1,n,a,b,c,0));
        }
    }
}

单调栈

单调栈 是在栈的**先进后出**基础之上额外添加一个特性:**从栈顶到栈底**的元素是严格递增或递减。

为了维护栈的单调性,在进栈过程中需要进行判断,具体进栈过程如下:假设当前进栈元素为 e,

  • 对于单调递增栈,从栈顶开始遍历元素,把小于 e 或者等于 e 的元素弹出栈,直至遇见一个大于 e 的元素或者栈为空为止,然后再把 e 压入栈中,这样就能满足从栈顶到栈底的元素是递增的
  • 对于单调递减栈,则每次弹出的是大于 e 或者等于 e 的元素,直至遇见一个小于e的元素或者栈为空为止

单调栈的作用在于

  • 单调递增栈从栈顶到栈底是递增的,栈中保留的都是比当前入栈元素大的值,因此可以快速找到入栈元素左边比他大的元素
  • 单调递减栈从栈顶到栈底是递减的,栈中保留的都是比当前入栈元素小的值,因此可以快速找到入栈元素左边比他小的元素

单调栈求区间长度和区间最小值乘积最大值:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
    ll pos, val;
};
node s[2005000] = {0};
ll a[2005000] = {0};
int main()
{
    ll n, top = 0, ans = 0;
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for (int j = 1; j <= n + 1; j++)
    {
        if (top == 0)
        {
            s[++top] = {j, a[j]};
        }
        else
        {
            while (s[top].val > a[j]) ///递增栈
            {
                ll tmp = (j - s[top - 1].pos - 1) * s[top].val;
                ans = max(ans, tmp);
                top--;
            }
            s[++top] = {j, a[j]};
        }
    }
    printf("%lld\n", ans);
    return 0;
}

线性基

线性基求交,参考与:https://blog.csdn.net/qcwlmqy/article/details/97584411

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
const int maxn=50500;
typedef long long ll;
class Bit_Set
{
public:
    ll d[32];
    Bit_Set()
    {
        memset(d,0,sizeof(d));
    }
    Bit_Set(const Bit_Set& t)
    {
        for(int i=0; i<=31; i++)
            d[i]=t.d[i];
    }
    void clear()
    {
        memset(d,0,sizeof(d));
    }
    void insert(ll x)
    {
        for(int i=31; i>=0; i--)
        {
            if(x&(ll(1)<<i))
            {
                if(!d[i])
                {
                    d[i]=x;
                    return ;
                }
                x^=d[i];
            }
        }
    }
    bool check(ll x)
    {
        for(int i=31; i>=0; i--)
        {
            if(x&(ll(1)<<i))
            {
                if(!d[i])
                    return false;
                x^=d[i];
            }
        }
        return true;
    }
    void show()
    {
        for(int i=0; i<=31; i++)
            cout<<i<<' '<<d[i]<<endl;
    }
    friend Bit_Set operator + (const Bit_Set& a, const Bit_Set& b)
    {
        Bit_Set a_b(a),c,res;
        for(int i=31; i>=0; i--)
        {
            if(b.d[i])
            {
                ll x=b.d[i],k=ll(1)<<i;
                bool flag=true;
                for(int j=31; j>=0; j--)
                {
                    if(x & (ll(1) << j))
                    {
                        if(a_b.d[j])
                        {
                            x^=a_b.d[j];
                            k^=c.d[j];   //将用上的b元素计入k
                        }
                        else
                        {
                            flag=false; //若不能被a_b表示,将b[i]加入数组
                            a_b.d[j]=x;
                            c.d[j]^=k;   //将a_b中b元素标记
                            break;
                        }
                    }
                }
                if(flag)
                {
                    ll x=0;
                    for(int j=31; j>=0; j--)
                    {
                        if(k&(ll(1)<<j))
                            x^=b.d[j];
                        //将用上的b元素和本身的b[i]异或在一起,
                        //由(a[argv---]^b[argv---]^b[i]==0),所得即为V1的贡献
                    }
                    res.insert(x);
                }
            }
        }
        return res;
    }
};
Bit_Set tree[maxn<<2];
void build(ll t,ll l,ll r)
{
    if(l==r)
    {
        int k;
        ll x;
        scanf("%d",&k);
        while(k--)
        {
            scanf("%lld",&x);
            tree[t].insert(x);
        }
        return ;
    }
    int mid=(l+r)/2;
    build(2*t,l,mid);
    build(2*t+1,mid+1,r);
    tree[t]=tree[2*t]+tree[2*t+1];
}
int query(ll t,ll l,ll r,ll L,ll R,ll x)
{
    if(l<=L&&R<=r)
    {
        return tree[t].check(x);
    }
    int flag=1;
    int mid=(L+R)/2;
    if(l<=mid)
        flag&=query(2*t,l,r,L,mid,x);
    if(r>mid)
        flag&=query(2*t+1,l,r,mid+1,R,x);
    return flag;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    build(1,1,n);
    while(m--)
    {
        int l,r,x;
        scanf("%d%d%d",&l,&r,&x);
        if(query(1,l,r,1,n,x))
            puts("YES");
        else
            puts("NO");
    }
}

线性基基础

性质

对于一个数组,存在一些数构成该数组的线性基

线性基有三大很优美的性质

  • 数组中所有数均可以由线性基中部分数异或得到
  • 数组中所有数异或出来均不为0
  • 对于同一数组线性基个数唯一 例如2 ,4 , 5 , 6 ,由线性基1 , 2 , 4 1 , 2 , 4 数组所有数均可以由1,2,41,2,41 , 2 , 4 1 , 2 , 4 数组所有数均可以由1,2,41,2,4异或得到

线性基构造

数组每加入一个数,对线性基进行修改 令线性基为d[32] ,数组长度为max(a[i])的最大二进制(所有数均可以由$ 1 , 2 , 4 ⋯ ,2^n$ 表示)

void add(int x) {
    for(int i=31; i>=0; i--) {  //i为线性基下标
        if(x&(1<<i)) { 
            if(d[i])x^=d[i];    //若该二进制位已有值,异或寻找线性基能否表达x^d[i]
            else {
                d[i]=x;         //若二进制位没有值,说明x不能被线性基表达,令d[i]=x
                break;          //记得如果插入成功一定要退出
            }
        }
    }
}

构造合理性:

  • 若能插入x ,则将d[i] =x,x可以由线性基表达
  • 若不能插入x,则x最终异或为0,即可以由线性基表达

区间异或最大值

数组( L , R ) 内取若干个数,使这些数异或后得到的值最大

d [ 32 ] 数组表示线性基的值,p [ 32 ]p [ 32 ]p [ 32 ]p [ 32 ]数组表示线性基的位置(为了便于询问,位置尽量存偏右的)

int ask(int l,int r){
    int res=0;
    forint i=31;i>=0;i--
        if(p[i]>=l&&(res^d[i])>res)
            res^=d[i];
    return res;
}

贪心:高位能变成1,就变成1(高位1比低位都变成1都有价值)

区间异或第k大

先将线性基处理成$ 1 , 2 , 4 , ⋯ ,2^n$ 的二进制表达形式

去除为0的异或值,每一位d[i] =1 相当于可以表达的二进制位数增加一位

void work() {           //将线性基转化为2进制
    for(int i=1; i<=31; i++)
        for(int j=1; j<=i; j++)
            if(d[i]&(1<<(j-1)))
                d[i]^=d[j-1];
}
int k_th(int k) {
    if(k==1&&tot<n)return 0;   //特判一下,假如k=1,并且原来的序列可以异或出0,就要返回0,
                               //tot表示线性基中的元素个数,n表示序列长度
    if(tot<n)k--;       //类似上面,去掉0的情况,因为线性基中只能异或出不为0的解
    work();
    int ans=0;
    for(int i=0; i<=31; i++)
        if(d[i]!=0) {
            if(k&1)ans^=d[i];
            k>>=1;
        }
}

主席树

参考链接:

https://blog.csdn.net/zuzhiang/article/details/78173412

https://www.cnblogs.com/s1124yy/p/6258026.html

https://blog.csdn.net/tianwei0822/article/details/79439054

主席树维护区间第k大数

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
int L[3200500] = {0}, R[3200500] = {0}, sum[3200500] = {0};
int tot = 0;
int a[3200500] = {0}, hash1[3200500] = {0}, T[3200500] = {0};
int build(int l, int r)
{
    int root = ++tot;
    sum[root] = 0;
    if (l < r)
    {
        int mid = (l + r) / 2;
        L[root] = build(l, mid);
        R[root] = build(mid + 1, r);
    }
    return root;
}
int update(int pre, int l, int r, int pos)
{
    int root = ++tot;
    L[root] = L[pre];
    R[root] = R[pre];
    sum[root] = sum[pre] + 1;
    if (l < r)
    {
        int mid = (l + r) / 2;
        if (pos <= mid)
            L[root] = update(L[pre], l, mid, pos);
        else
            R[root] = update(R[pre], mid + 1, r, pos);
    }
    return root;
}
int query(int l1, int r1, int l, int r, int k) //参数分别为:两颗线段树根节点的编号,左右端点,第k大
{
    if (l >= r)
        return l;
    int mid = (l + r) / 2;
    int num = sum[L[r1]] - sum[L[l1]];
    if (num >= k)
        return query(L[l1], L[r1], l, mid, k);
    else
        return query(R[l1], R[r1], mid + 1, r, k - num);
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        tot = 0;
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]), hash1[i] = a[i];
        sort(hash1 + 1, hash1 + n + 1);
        int d = unique(hash1 + 1, hash1 + n + 1) - hash1 - 1;
        T[0] = build(1, d);
        for (int i = 1; i <= n; i++)
        {
            int pos = lower_bound(hash1 + 1, hash1 + d + 1, a[i]) - hash1;
            T[i] = update(T[i - 1], 1, d, pos);
        }
        for (int i = 1; i <= m; i++)
        {
            int l, r, k;
            scanf("%d%d%d", &l, &r, &k);
            int pos = query(T[l - 1], T[r], 1, d, k);
            printf("%d\n", hash1[pos]);
        }
    }
}

查询区间内小于等于给定的K的数的个数

题目链接:https://acm.hdu.edu.cn/showproblem.php?pid=4417

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
int L[3200500] = {0}, R[3200500] = {0}, sum[3200500] = {0};
int tot = 0;
int a[3200500] = {0}, hash1[3200500] = {0}, T[3200500] = {0};
int build(int l, int r)
{
    int root = ++tot;
    sum[root] = 0;
    if (l < r)
    {
        int mid = (l + r) / 2;
        L[root] = build(l, mid);
        R[root] = build(mid + 1, r);
    }
    return root;
}
int update(int pre, int l, int r, int pos)
{
    int root = ++tot;
    L[root] = L[pre];
    R[root] = R[pre];
    sum[root] = sum[pre] + 1;
    if (l < r)
    {
        int mid = (l + r) / 2;
        if (pos <= mid)
            L[root] = update(L[pre], l, mid, pos);
        else
            R[root] = update(R[pre], mid + 1, r, pos);
    }
    return root;
}
int query(int l1, int r1, int l, int r, int k)
{
    if (k < hash1[l])
        return 0;
    if (hash1[r] <= k)
        return sum[r1] - sum[l1];
    int mid = (l + r) / 2;
    if (k <= hash1[mid])
    {
        return query(L[l1], L[r1], l, mid, k);
    }
    else
    {
        int num = 0;
        num += sum[L[r1]] - sum[L[l1]];
        num += query(R[l1], R[r1], mid + 1, r, k);
        return num;
    }
}
int main()
{
    int t;
    scanf("%d", &t);
    for (int t1 = 1; t1 <= t; t1++)
    {
        tot = 0;
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]), hash1[i] = a[i];
        sort(hash1 + 1, hash1 + n + 1);
        int d = unique(hash1 + 1, hash1 + n + 1) - hash1 - 1;
        T[0] = build(1, d);
        for (int i = 1; i <= n; i++)
        {
            int pos = lower_bound(hash1 + 1, hash1 + d + 1, a[i]) - hash1;
            T[i] = update(T[i - 1], 1, d, pos);
        }
        printf("Case %d:\n", t1);
        for (int i = 1; i <= m; i++)
        {
            int l, r, k;
            scanf("%d%d%d", &l, &r, &k);
            int ans = query(T[l], T[r + 1], 1, d, k);
            printf("%d\n", ans);
        }
    }
}

ST表

ST 表是用于解决 可重复贡献问题 的数据结构。

可重复贡献问题 是指对于运算opt,满足x\quad opt\quad x = x ,则对应的区间询问就是一个可重复贡献问题。例如,最大值有max(x,x)=x,gcd 有gcd(x,x)=x ,所以 RMQ 和区间 GCD 就是一个可重复贡献问题。像区间和就不具有这个性质,如果求区间和的时候采用的预处理区间重叠了,则会导致重叠部分被计算两次,这是我们所不愿意看到的。另外, opt还必须满足结合律才能使用 ST 表求解。

一维ST表模板

#include <stdio.h>
#include <math.h>
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
using namespace std;
int a[50050] = {0}, dp_max[50050][30] = {0}, dp_min[50050][30] = {0};
int n, m;
void st()
{
    for (int i = 1; i <= n; i++)
        dp_max[i][0] = dp_min[i][0] = a[i];
    for (int j = 1; (1 << j) <= n; j++)
    {
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            dp_max[i][j] = max(dp_max[i][j - 1], dp_max[i + (1 << (j - 1))][j - 1]);
            dp_min[i][j] = min(dp_min[i][j - 1], dp_min[i + (1 << (j - 1))][j - 1]);
        }
    }
}
int query_max(int l, int r)
{
    int k = log2(r - l + 1);
    return max(dp_max[l][k], dp_max[r - (1 << k) + 1][k]);
}
int query_min(int l, int r)
{
    int k = log2(r - l + 1);
    return min(dp_min[l][k], dp_min[r - (1 << k) + 1][k]);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    st();
    while (m--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", query_max(l, r) - query_min(l, r));
    }
}

一维ST维护GCD模板

题目大意为给定长度为n的序列,后面又m次询问,询问满足区间gcd为给定数值的个数。

算法为二分+ST表,由于区间中不同GCD个数最多为log个,所以时间复杂度nlog(n)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100500] = {0}, dp[100500][30] = {0};
map<ll, ll> mp;
ll n, m, k;
void st()
{
    for (ll i = 1; i <= n; i++)
        dp[i][0] = a[i];
    for (ll j = 1; (1 << j) <= n; j++)
    {
        for (ll i = 1; i + (1 << j) - 1 <= n; i++)
        {
            dp[i][j] = __gcd(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
        }
    }
}
ll query(ll l, ll r)
{
    ll k = log2(r - l + 1);
    return __gcd(dp[l][k], dp[r - (1 << k) + 1][k]);
}
int main()
{
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    st();
    for (ll i = 1; i <= n; i++)
    {
        ll cur = i, gc = a[i];
        while (cur <= n)
        {
            ll l = cur, r = n;
            while (l < r)
            {
                ll mid = (l + r + 1) / 2;
                if (query(cur, mid) == gc)
                    l = mid;
                else
                    r = mid - 1;
            }
            if (mp.count(gc) == 0)
                mp[gc] = (l - cur + 1);
            else
                mp[gc] += (l - cur + 1);
            cur = l + 1;
            if (cur <= n)
                gc = __gcd(gc, a[cur]);
        }
    }
    scanf("%lld", &m);
    for (ll i = 1; i <= m; i++)
    {
        scanf("%lld", &k);
        printf("%lld\n", mp[k]);
    }
    return 0;
}

二维ST表模板

#include <bits/stdc++.h>
using namespace std;
int dp_max[300][300][20] = {0};
int dp_min[300][300][30] = {0};
int a[300][300] = {0};
int n, m;
void st()
{
    for (int i = 1; i <= n; i++)
    {
        for (int k = 0; (1 << k) <= m; k++)
        {
            for (int j = 1; j + (1 << k) - 1 <= m; j++)
            {
                if (k == 0)
                    dp_max[i][j][k] = dp_min[i][j][k] = a[i][j];
                else
                {
                    dp_max[i][j][k] = max(dp_max[i][j][k - 1], dp_max[i][j + (1 << (k - 1))][k - 1]);
                    dp_min[i][j][k] = min(dp_min[i][j][k - 1], dp_min[i][j + (1 << (k - 1))][k - 1]);
                }
            }
        }
    }
}
int query_max(int x, int y, int xx, int yy)
{
    int k = log2(yy - y + 1);
    int mm = 0;
    for (int i = x; i <= xx; i++)
        mm = max(mm, max(dp_max[i][y][k], dp_max[i][yy - (1 << k) + 1][