树状数组-并查集_删除边 仍然联通的最大权值和

1.树状数组

给你一个序列a[1]~a[N],你需要找出每一个数a[i]，在区间[1, i - 1]有多少个数小于等于a[i]。

int lowbit(int x)
{
    return x&(-x);
}
void update(int x,int y)
{
    while(x<=n)
    {
        c[x]+=y;
        x+=lowbit(x);
    }
    //return;//重点
}
int sum(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}

给你一个初始全为0的序列a[1]~a[N]，有q次操作，每次操作有两种类型，第一种操作时区间翻转操作，将区间[l, r]进行翻转，也就是原来为0的数现在变为1，原来为1的数现在变为0.第二组是查询操作，查询位置loc的值是0还是1.

int lowbit(int x)
{
    return x&(-x);
}
void update(int l,int r)
{
    while(l>0)
    {
        w[l]+=1;
        l-=lowbit(l);
    }
    while(r>0)
    {
        w[r]+=1;
        r-=lowbit(r);
    }
}
int sum(int x)
{
    int sum=0;
    while(x<=N)
    {
        sum+=w[x];
        x+=lowbit(x);
    }
    return sum;
}

2.并查集

把这些柱子当成N个节点，编号为1~N，然后给你若干条边，每条边连接两个点，且每条边有一个权值。现在让你删去其中的若干条边，使得这N个节点相互连通。当然有很多种不同的删法，现在让你找出一种删法，使得删除的边的权值和最大，如果不存在删法，使得这N个节点相联通，输出-1，否则，输出删除的最大边权和。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct edge
{
    int u, v;
    int w;
    friend bool operator < (edge a, edge e)
    {
        return a.w<e.w;
    }
}e[1000000];
vector<edge> part;
vector<long> father(1000000, -1);
long findfather(long i)
{
    if (father[i] == -1) return i;
    else  return father[i] = findfather(father[i]);
}
void merge_union(long x, long y)
{
    long f1 = findfather(x);
    long f2 = findfather(y);
    father[f1] = f2;
}
long findmin(long n)
{
    sort(part.begin(), part.end());
    vector<edge> mst;
    long sum = 0;
    long x = 0;
    for (long i = 0; i<part.size(); i++)
    {
        if (findfather(part[i].u) == findfather(part[i].v)) continue;
        else
        {
            merge_union(part[i].u, part[i].v);
            sum += part[i].w;
            mst.push_back(part[i]);
        }
    }
    if (mst.size() != n - 1)  return -1;
    return sum;
}
int main()
{
    long N,M;
    long T;
    cin >> T;
    while (T--)
    {
        cin >> N >> M;
        long x,sum=0;
        for (long i = 0; i<M; i++)
        {
            edge ed;
            cin >> ed.u >> ed.v >> ed.w;
            part.push_back(ed);
            sum += ed.w;
        }
        x = findmin(N);
        if (x == -1) cout <<  x << endl;
        else
            cout << sum-x << endl;
        part.clear();
        father.clear();
        father.resize(1000000, -1);
    }
    return 0;
}