并查集(二刷)，总结一下。

并查集：

一般有两种操作：
(1)合并两个集合
(2)查询某个元素的祖宗节点

一般会维护两个东西：
(1)维护每个集合的大小size（绑定到根节点上）
(2)维护每个点到根节点的距离d（绑定到每个元素上,通过前缀和的思想来维护东西）


一般有三种并查集：
(1)普通并查集

(2)带权并查集（用相对关系的思想，一般维护每个点到根节点的距离d，通过 % 来表示该点和根节点的关系）
    只要两个点有关系(不管是不是同类)，他们就在一个集合里，然后通过边权d[]来维护之间的关系。

(3)拓展域并查集（用枚举的思想，枚举这个东西属于哪一类，然后怎么样...）
    比如分成不同的条件(1 ~ n) (n+1 ~ 2n) (2n+1 ~ 3n)...，然后：
    如果在同一个集合里：  判断矛盾时，想可能产生矛盾的所有情况
    如果不在同一个集合里：合并的时候要考虑所有的合法情况

具体题目：
AcWing 239. 奇偶游戏
https://www.acwing.com/activity/content/code/content/1645633/

AcWing 240. 食物链
https://www.acwing.com/activity/content/code/content/1430103/

二维树状数组

1. 主函数中注意初始时每个位置都要update
2. 查询时要用二维前缀和形式：
    query(x2,y2) - query(x2,y1-1) - query(x1-1,y2) + query(x1-1,y1-1);

3. 时间复杂度：
    由于初始化每个点都要update，每次update/query都是O((logn)^2)
    所以是O(n^2 * (logn)^2);
    时间复杂度还是比较高的...

4. 写起来十分方便，用于查询动态查询矩阵和


int a[maxn][maxn];
int tr[maxn][maxn];
int n,m;

//单点修改（在a[x][y]加上v）
void update(int x,int y,int v)
{
    for(int i=x;i<=n;i+=lowbit(i))
        for(int j=y;j<=n;j+=lowbit(j))
            tr[i][j] += v;
}

//矩阵前缀和查询（[1,1] ~ [x,y]的矩阵和）
int query(int x,int y)
{
    int ans = 0;
    for(int i=x;i;i-=lowbit(i))
        for(int j=y;j;j-=lowbit(j))
            ans += tr[i][j];
    return ans;
}

二维线段树

/*
二维线段树学习：
别用结构体写了，又乱空间复杂度又高...

理解二维线段树的关键：
1. 每个一维线段树的节点都包含着一颗二维线段树；
2. 在合并一维线段树的区间时，二维线段树也要同时合并(对应合并)
    u_x.u_y.v = lu_x.u_y.v + ru_x.u_y.v ;

注意线段树开4倍空间！！！
时间复杂度O(m*logn*logn)

最终板子（单点修改 + 区间查询最值/矩阵和）
*/

ll a[maxn][maxn];
ll tr_max[maxn * 4][maxn * 4];  //最大值二维线段树
ll tr_min[maxn * 4][maxn * 4];  //最小值二维线段树
ll tr_sum[maxn * 4][maxn * 4];  //求和二维线段树
int n, m;
ll sum, mx, mn; //查询的答案

void pushup_x(int u_x, int u_y) //对一维pushup
{
    tr_max[u_x][u_y] = max(tr_max[u_x << 1][u_y], tr_max[u_x << 1 | 1][u_y]);
    tr_min[u_x][u_y] = min(tr_min[u_x << 1][u_y], tr_min[u_x << 1 | 1][u_y]);
    tr_sum[u_x][u_y] = tr_sum[u_x << 1][u_y] + tr_sum[u_x << 1 | 1][u_y];
}

void pushup_y(int u_x, int u_y) //对二维pushup
{
    tr_max[u_x][u_y] = max(tr_max[u_x][u_y << 1], tr_max[u_x][u_y << 1 | 1]);
    tr_min[u_x][u_y] = min(tr_min[u_x][u_y << 1], tr_min[u_x][u_y << 1 | 1]);
    tr_sum[u_x][u_y] = tr_sum[u_x][u_y << 1] + tr_sum[u_x][u_y << 1 | 1];
}

void build_y(int u_x, int u_y, int l, int r, int flag)  //第二维线段树，注意flag标记
{
    if (l == r)
    {
        if (flag != -1) 
tr_max[u_x][u_y] = tr_min[u_x][u_y] = tr_sum[u_x][u_y] = a[flag][l];
        else pushup_x(u_x, u_y);
        return;
    }

    int mid = l + r >> 1;
    build_y(u_x, u_y << 1, l, mid, flag);
    build_y(u_x, u_y << 1 | 1, mid + 1, r, flag);

    pushup_y(u_x, u_y);
}

void build_x(int u_x, int l, int r)
{
    if (l == r) //一维走到叶子节点对二维建树
    {
        build_y(u_x, 1, 1, n, l);
        return;
    }

    int mid = l + r >> 1;
    build_x(u_x << 1, l, mid);
    build_x(u_x << 1 | 1, mid + 1, r);

    build_y(u_x, 1, 1, n, -1);  //每个一维节点的二维线段树也要更新
}

void update_y(int u_x, int u_y, int l, int r, int y, int val, int flag) //第一维线段树的修改，注意flag标记
{
    if (l == r)
    {
        if (flag) //注意读清楚题意，看是单点修改值还是单点加值
            tr_max[u_x][u_y] = tr_min[u_x][u_y] = tr_sum[u_x][u_y] = val;
        else pushup_x(u_x, u_y);

        return;
    }

    int mid = l + r >> 1;
    if (y <= mid) update_y(u_x, u_y << 1, l, mid, y, val, flag);
    else update_y(u_x, u_y << 1 | 1, mid + 1, r, y, val, flag);

    pushup_y(u_x, u_y);
}

void update_x(int u_x, int l, int r, int x, int y, int val) //第一维线段树的修改
{
    if (l == r)
    {
        update_y(u_x, 1, 1, n, y, val, 1);
        return;
    }

    int mid = l + r >> 1;
    if (x <= mid) update_x(u_x << 1, l, mid, x, y, val);
    else update_x(u_x << 1 | 1, mid + 1, r, x, y, val);

    update_y(u_x, 1, 1, n, y, val, 0);  //每个一维节点的二维线段树也要更新
}

void query_y(int u_x, int u_y, int l, int r, int y1, int y2)    //第二维线段树的查询
{
    if (l >= y1 && r <= y2)
    {
        mx = max(mx, tr_max[u_x][u_y]);
        mn = min(mn, tr_min[u_x][u_y]);
        sum += tr_sum[u_x][u_y];
        return;
    }

    int mid = l + r >> 1;
    if (y1 <= mid) query_y(u_x, u_y << 1, l, mid, y1, y2);
    if (y2 > mid) query_y(u_x, u_y << 1 | 1, mid + 1, r, y1, y2);
}

void query_x(int u_x, int l, int r, int x1, int x2, int y1, int y2) //第一维线段树的查询
{
    if (l >= x1 && r <= x2)
    {
        query_y(u_x, 1, 1, n, y1, y2);
        return;
    }

    int mid = l + r >> 1;
    if (x1 <= mid) query_x(u_x << 1, l, mid, x1, x2, y1, y2);
    if (x2 > mid) query_x(u_x << 1 | 1, mid + 1, r, x1, x2, y1, y2);
}

int main()
{
    scanf("%d", &n);    //n*n的矩阵
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%lld", &a[i][j]);

    build_x(1, 1, n);   //一维建树

    scanf("%d", &m);    //m个询问
    while (m--)
    {
        string op;
        cin >> op;

        if (op == "c")      //修改
        {
            int x, y, v;
            scanf("%d %d %d", &x, &y, &v);

            //对一维操作（这里注意一些修改的变形操作）
            update_x(1, 1, n, x, y, v);
        }
        else if (op == "q") //查询
        {
            //注意初始化
            mx = -INF; mn = INF; sum = 0;

            int x1, x2, y1, y2; //注意从0开始，还是从1开始
            scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
            query_x(1, 1, n, x1, x2, y1, y2);       //对一维操作

            printf("%lld %lld %lld\n", mx, mn,sum);
        }
    }
    return 0;
}