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

typedef long long LL;
const int N=1e5+10,M=2e6+10;

int h[N],e[M],hs[N],ne[M],idx;
int dfn[N],low[N];
int stk[N],ins[N],c[N];
vector<int>scc[N];
int n,m,tot,num,top,cnt,mod;
unordered_set<int>S;


int f[N],g[N];

void add(int h[],int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++num;
    stk[++top]=x,ins[x]=1;

    for(int i=h[x];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[x]=min(low[x],low[j]);
        }
        else if(ins[j])
        {
            low[x]=min(low[x],dfn[j]);
        }
    }

    if(dfn[x]==low[x]){
        cnt++;
        int y;
        do{
            y=stk[top--],ins[y]=0;
            c[y]=cnt,scc[cnt].push_back(y);
        }while(x!=y);
    }

}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin>>n>>m>>mod;
    memset(h,-1,sizeof h);
    memset(hs,-1,sizeof hs);

    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(h,a,b);
    }

    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])tarjan(i);
    }

   unordered_set<LL> S;    // (u, v) -> u * 1000000 + v
    for (int i = 1; i <= n; i ++ )
        for (int j = h[i]; ~j; j = ne[j])
        {
            int k = e[j];
            int a = c[i], b = c[k];
            LL hash = a * 1000000ll + b;
            if (a != b && !S.count(hash))
            {
                add(hs, a, b);
                S.insert(hash);
            }
        }



     for (int i = cnt; i; i -- )
    {
        if (!f[i])
        {
            f[i] = scc[i].size();
            g[i] = 1;
        }
        for (int j = hs[i]; ~j; j = ne[j])
        {
            int k = e[j];
            if (f[k] < f[i] + scc[k].size())
            {
                f[k] = f[i] + scc[k].size();
                g[k] = g[i];
            }
            else if (f[k] == f[i] + scc[k].size())
                g[k] = (g[k] + g[i]) % mod;
        }
    }


     int maxf = 0, sum = 0;
    for (int i = 1; i <= cnt; i ++ )
        if (f[i] > maxf)
        {
            maxf = f[i];
            sum = g[i];
        }
        else if (f[i] == maxf) sum = (sum + g[i]) % mod;

    cout<<maxf<<endl<<sum<<endl;
    return 0;




}

暴力思路：
从后往前一个一个的寻找,每一次找到一个，就删除一个,时间复杂度O(n^2)，显然不对
像一个办法优化，构造一个一共n个数，每一个数都为1的虚拟数组,用树状数组表示这个数组的前缀和,表示1-n每一个数在开始的时候后还可以用一次,以后我们每一次找到一个数，就使用单点修改删掉这个数字,那么如何找到剩余的数字中第k个数字呢？
使用二分，刚才说前缀和表示在i之前还有多少个数字可以用，那么这个个数一定是单调递增的，我们只要找到一个最小的ask(r)使得ask(r)==k这样r就是我们要找的高度 时间复杂度为O(n*(log)^2)

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

const int N=1e5+10;

int a[N];
int n;
int ans[N];
int t[N];
int lowbit(int x)
{
    return x&-x;
}

void add(int x,int c)
{
    for(int i=x;i<=n;i+=lowbit(i))t[i]+=c;
}
int ask(int x)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i))res+=t[i];
    return res;
}
//a1,a2,a3,,,an  那么最后一头牛的身高就是an+1,考虑完一个牛后删去这个牛，那么导师第二头牛就是在剩下的n-1个数
//中排名an-1+1个数  初始的时候,我们用一个1到n全为1的数组来表示每一个数都可以用一次,每一次填进去一个数，我们就
//删掉一个数,用一个树状数组来表示这个数组的前缀和,这个前缀和表示的实际上是还有多少个数字可以用,
//你需要找到的是在剩下的这些数字里面排第k个的数是多少，其实就是在找一个最小的sum(i)使得sum(i)等于k
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin>>n;
    for(int i=2;i<=n;i++)cin>>a[i];

    for(int i=1;i<=n;i++)add(i,1);

    for(int i=n;i;i--)
    {
        int x=a[i]+1;

        int l=1,r=n;
        while(l<r)
        {
            int mid=l+r>>1;
            if(ask(mid)>=x)r=mid;
            else l=mid+1;
        }
        ans[i]=l;
        add(l,-1);

    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
    return 0;


}

树状数组的扩展应用，支持多点修改，多点查询，多点修改和上一个题目一样，只要维护一个查分数组的前缀和，多点查询，在这里通过变换以后，可以表示成一个前缀和之间运算的形式
我们在这个过程中只要多维护一个数组t2[]数组表示i*b[i]的前缀和,

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

const int N=1e5+10,M=1000000000;

int a[N],t[N],t2[N];
int n,m;
int lowbit(int x)
{
    return x&-x;
}
void add(int i,int x,int t[])
{
    for(i;i<=n;i+=lowbit(i))t[i]+=x;
}
int ask(int x)
{
    int ans=0;
    for(int i=x;i;i-=lowbit(i))ans+=t[i];

    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        cin>>a[i];
        add(i,a[i]-a[i-1],t);
        add(i,a[i],t2);
    }



    while(m--)
    {
        char op;
        int l,r,d;
        cin>>op;
        if(op=='C')
        {
            cin>>l>>r>>d;
            add(l,d);
            add(r+1,-d);
        }
        else 
        {
            cin>>l;
            cout<<ask(l)<<endl;
        }
    }
    return 0;

}

正常的树状数组支持 单点修改，区间查询,这个要我们实现区间修改，单点查询，区间修改，使用差分数组，将原来维护的正常数组变成差分数组，我们要修改某一段的时候，只要修改两个点，修改踩组是logn的,要查询某一个点的时候，只要查询差分数组的前缀和就可以得到这个点了

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

const int N=1e5+10,M=1000000000;
typedef long long LL;
int a[N],t[N];
int n,m;
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int c)
{
    for(int i=x;i<=n;i+=lowbit(i))t[i]+=c;
}
int ask(int x)
{
    int ans=0;
    for(int i=x;i;i-=lowbit(i))ans+=t[i];

    return ans;
}
int main()
{

   scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i ++ ) add(i, a[i] - a[i - 1]);



   while (m -- )
    {
        char op[2];
        int l, r, d;
        scanf("%s%d", op, &l);
        if (*op == 'C')
        {
            scanf("%d%d", &r, &d);
            add(l, d), add(r + 1, -d);
        }
        else
        {
           cout<<ask(l)<<endl;
        }
    }
    return 0;

}

树状数组的第一道题
树状数组可以这么理解,和原来的前缀和比较相似，只不过原来的前缀和s[i]就是确定覆盖1-i-1这些数字的和,现在的t[i]是表示以i为根节点的所有覆盖的树上子节点的和，这样在树上走就可以把时间爱你复杂度由O(n)变为O(logn),两个基本操作
查询：由原来的每一次减去1变为减去lowbit(i)，这样会得到几个不相交区间的和，就是前缀和
添加:和差分思想有点相似,给一个数加上x,要把所有覆盖范围中包含这个点的都改变

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

const int N=200000+10;
typedef long long LL;
int n;
int a[N],t[N];

LL lower[N],Greater[N];
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int y)
{
    for(int i=x;i<=n;i+=lowbit(i))t[i]+=y;
}
LL ask(int x)
{
    LL ans=0;
    for(int i=x;i;i-=lowbit(i))ans+=t[i];

    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);


    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];

    for(int i=1;i<=n;i++)
    {
        int y=a[i];
        lower[i]=ask(y-1);
        Greater[i]=(ask(n)-ask(y));
        add(y,1);
    }
    memset(t,0,sizeof t );
    LL cntA=0,cntV=0;


    for(int i=n;i;i--)
    {
        int y=a[i];
        cntA+=(lower[i]*ask(y-1));
        cntV+=(Greater[i]*(ask(n)-ask(y)));
        add(y,1);
    }

    cout<<cntV<<" "<<cntA;

    return 0;


}

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

const int N=30000+10;
int p[N],s[N],d[N];
int T;

int find(int x)
{
    if(x!=p[x])
    {
        int root=find(p[x]);
        d[x]+=d[p[x]];
        p[x]=root;
 //在路径压缩把x直接指向树根的同时，我们把d[x]更新为从x到树根的路径上所有的边权之和       
    }
    return p[x];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    for(int i=1;i<N;i++)
    {
        p[i]=i;
        s[i]=1;
    }
    cin>>T;
    while(T--)
    {
        char op;
        int a,b;
        cin>>op>>a>>b;
        if(op=='M')
        {
            int pa=find(a),pb=find(b);
            d[pa]=s[pb];
            s[pb]+=s[pa];
            p[pa]=pb;
        }
        else
        {
            int pa=find(a),pb=find(b);
            if(pa!=pb)cout<<-1<<endl;
            else cout<<(max(abs(d[a]-d[b])-1,0))<<endl;
        }
    }
    return 0;
}

不用保序的离散化，直接使用unordered_map就可以

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

const int N=2000000+10;
unordered_map<int,int>S;
int p[N];
int n,m;
struct Querry
{
    int x,y,e;
}querry[N];

int get(int x)
{
    if(S.count(x) == 0)S[x]=++n;
    return S[x];

}


int find(int x)
{
    if(x!=p[x])p[x]=find(p[x]);
    return p[x];
}
// int get(int x)
// {
//     if (S.count(x) == 0) S[x] = ++ n;
//     return S[x];
// }

// int find(int x)
// {
//     if (p[x] != x) p[x] = find(p[x]);
//     return p[x];
// }
int T;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin>>T;

    while(T--)
    {

        int m;
        cin>>m;
        S.clear();
        n=0;
        for(int i=0;i<m;i++)
        {
            int x,y,e;
            cin>>x>>y>>e;
            x=get(x),y=get(y);
            querry[i]={x,y,e};
        }
        //初始化并查集
        for(int i=1;i<=n;i++)p[i]=i;

        for(int i=0;i<m;i++)
        {
          if(querry[i].e==1)
          {
              int pa=find(querry[i].x),pb=find(querry[i].y);
              p[pa]=pb;
          }
        }
        bool has_conflict=false;
        for(int i=0;i<m;i++)
        {
          if(querry[i].e==0)
          {
              int pa=find(querry[i].x),pb=find(querry[i].y);
                if(pa==pb)
                {
                    has_conflict=true;
                    break;
                }
          }
        }

        if(has_conflict)cout<<"NO"<<endl;
        else cout<<"YES"<<endl;

    }



    return 0;

}

题目意思是说买一个东西必须把这一类的东西都给买了，这一类就组成了一个连通块,然后对于这一类，每一类只有买和不买两种情况，这就构成了一个01背包问题，这样对所有的代表节点求一遍01背包就可以,在合并集合的过程中要维护每一个集合的体积还有数量

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

const int N=10000+10;

int v[N],w[N];

int p[N];
int f[N];
int n,m,W;
int  find(int x)
{
    if(x!=p[x])p[x]=find(p[x]);
    return p[x];
}
int main()
{
    cin>>n>>m>>W;
    for(int i=1;i<=n;i++)p[i]=i;

    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];


    while(m--)
    {
        int a,b;
        cin>>a>>b;
        int pa=find(a),pb=find(b);

        if(pa!=pb)
        {
            v[pb]+=v[pa];
            w[pb]+=w[pa];
            p[pa]=pb;
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(p[i]==i)
        {
            for(int j=W;j>=v[i];j--)
             f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }

    cout<<f[W]<<endl;
    return 0;
}