问题描述

There are holes and tunnels connecting them. The holes are labeled by . For all , a hole number i is connected by a tunnel to the hole number . Tunnels are all bidirectional.

Initially, all the tunnels are available. There will be m events happened in the tunnel system. The event will change the status of the tunnel between and . If this tunnel is available, it will become unavailable, and if this tunnel is unavailable, it will become available.

Please write a program to support these events, and report the number of pairs that holes are still connected after each event.

输入

The first line of the input contains an integer , denoting the number of test cases.

In each test case, there are two integers in the first line, denoting the number of holes and the number of events.

For the next m lines, each line contains an integer , denoting an event.

输出

For each test case, print m lines. The line contains an integer, denoting the number of connected pairs after the event.

样例输入

1
9 6
6
4
2
4
4
3

样例输出

28
13
7
13
7
5

解题思路

这是一个不那么好做的题，但仔细想想，还是简单的。

题目有点长，读下来，意思其实也很清晰。

由于他是个点，条边，所以很显然是一个简单图，还是一棵树。

继续读下去，你会发现，这不就是一个用数组存的完全二叉树（堆）吗。

堆

那我们观察下，看看联通是怎么计算的。

根据样例，如果把6号节点移除了，那么剩下还有28条联通对，那是哪28条呢？

观察规律，我们发现：
对于9号节点来说：

[9 - 4], [9 - 8], [9 - 2], [9 - 5], [9 - 1], [9 - 3], [9 - 7]

也就是有7对联通对
对于8号节点来说：

[8 - 4], [8 - 2], [8 - 5], ..., [8 - 7]

也就是除去[8 - 9]这对重复的，剩下来的6对。

规律发现了，也就是说，8个节点互相联通，那么联通对的数量是：，简单的来说，就是。

那么思路就来了，只要知道当前联通块的节点数，那么该联通块的联通对数就很容易算出了：。

有了这个概念，那么就直接暴力（也就嘛）一波走起了。

为了方便，我开两个数组a和b，分别记录下的子节点数（包括自身）和下的联通对数。

表格

建树

有了理论基础，那就用代码来对a和b数组初始化一下。

for (int i = n;i >= 1;i --)
{
    t = i * 2 + 1;
    if (t > n) t = 0;
    else t = a[t];
    a[i] = t;
    t = i * 2;
    if (t > n) t = 0;
    else t = a[t];
    a[i] += t + 1;
    b[i] = a[i] * (a[i] - 1) / 2;
}

由于数据最大是100000，所以b数组算出来最大有4999950000之大，得用long long了。

然后呢，我们用一个变量v来记录一下总共的联通块，以便后续操作之用。

long long v = b[1];

操作

剩下的，便是我们的操作。

根据题意，每一次操作都会翻转联通与否，所以我们还得记一笔联通情况。

int k[100010];
memset(k, -1, sizeof(k)); // -1代表，一开始都联通

因此我们可以开始读入：

for (int i = 0;i < m;i ++)
{
    scanf("%lld",&t);
    k[t] = !k[t];
    if (k[t]) add(t);
    else remove(t);
    printf("%lld\n",v);
}

这样，程序的主体便完成了。

那么我们来看看remove和add方法。

void add(long long i)
{
    v -= b[i];
    update(i);
}

void remove(long long i)
{
    v += b[i];
    update(i);
}

思路也很简单。

对于移除节点：先让总联通块数加上他自身的子联通块数（因为：一旦一个联通块失去联系，那么作为这个联通块本身也就独立了，所以只要让总数加上这个独立的联通对数），之后，再一步步更新上去即可；

对于添加节点：先让总联通块数减去他自身的子联通块数（因为：当一个独立的联通块恢复链接之后，那它原来加上去的子联通块数也没有用了，所以得减去），之后，再一步步更新上去即可。

到目前为止，就剩下如何更新了。

那么我们来更新吧（注释非常详细哦）。

void update(long long i)
{
    long long c1 = 0, c2 = 0;
    i /= 2; // 首先强制更新进行过add/remove操作的父节点的状态
    long long h = 0; // 开一个变量用于记录
    if (i * 2 <= n && k[i * 2]) c1 = a[i * 2]; // 如果a[i]有左节点联通，那就记录下他左节点的子节点数
    if (i * 2 + 1 <= n && k[i * 2 + 1]) c2 = a[i * 2 + 1]; // 如果a[i]有右节点联通，那就记录下他右节点的子节点数
    a[i] = c1 + c2 + 1; // 求和并+1来更新自己的子节点数（包括a[i]自己，所以+1）
    h = b[i]; // 记录下更新之前的子联通块数
    b[i] = a[i] * (a[i] - 1) / 2; // 用之前找规律所得的公式来更新b[i]
    while (k[i]) // 如果a[i]上面继续联通着父亲节点，那就一路更新上去吧
    {
        i /= 2;
        c1 = c2 = 0;
        if (i * 2 <= n && k[i * 2]) c1 = a[i * 2];
        if (i * 2 + 1 <= n && k[i * 2 + 1]) c2 = a[i * 2 + 1];
        a[i] = c1 + c2 + 1;
        h = b[i];
        b[i] = a[i] * (a[i] - 1) / 2;
    }
    v -= h; // 最后更新全局所有联通块数v，先减去先前的b[i]，也就是先前操作的这个联通块之前的联通对数
    v += b[i]; // 更新成现在的
}

最后，来一个动画解释一波。

移除

添加

代码

好吧，老规矩，还是给一个ac代码吧。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <vector>
#include <list>
#include <set>
#include <utility> // pair
#include <map>
#include <iostream>
#include <sstream>
#include <algorithm> // sort
#include <string>
#include <stack>
#include <queue>
#include <fstream>

using namespace std;

#define ll long long
#define uchar unsigned char
#define ushort unsigned short
#define uint unsigned int
#define ulong unsigned long
#define ull unsigned long long

#define pi acos(-1)

#define mx(a,b) (a) > (b) ? (a) : (b)
#define mn(a,b) (a) < (b) ? (a) : (b)
#define mem(a,b) memset(a,b,sizeof(a))
#define fre(a) freopen(a,"r",stdin)

#define itn int
#define nit int
#define inr int
#define mian main
#define ednl endl
#define fro for
#define fir for
#define reutrn return
#define retunr return

ll a[100010];
ll b[100010];
int k[100010];

ll v;
int n,m;

void update(ll i)
{
    ll c1 = 0, c2 = 0;
    i /= 2;
    ll h = 0;
    if (i * 2 <= n && k[i * 2]) c1 = a[i * 2];
    if (i * 2 + 1 <= n && k[i * 2 + 1]) c2 = a[i * 2 + 1];
    a[i] = c1 + c2 + 1;
    h = b[i];
    b[i] = a[i] * (a[i] - 1) / 2;
    while (k[i])
    {
        i /= 2;
        c1 = c2 = 0;
        if (i * 2 <= n && k[i * 2]) c1 = a[i * 2];
        if (i * 2 + 1 <= n && k[i * 2 + 1]) c2 = a[i * 2 + 1];
        a[i] = c1 + c2 + 1;
        h = b[i];
        b[i] = a[i] * (a[i] - 1) / 2;
    }
    v -= h;
    v += b[i];
}

void add(ll i)
{
    v -= b[i];
    update(i);
}

void remove(ll i)
{
    v += b[i];
    update(i);
}

int main()
{
    int T;
    scanf("%d",&T);
    ll t;
    while (T --)
    {
        scanf("%d %d",&n,&m);
        mem(k,-1);
        k[0] = 0;
        k[1] = 0;
        for (int i = n;i >= 1;i --)
        {
            t = i * 2 + 1;
            if (t > n) t = 0;
            else t = a[t];
            a[i] = t;
            t = i * 2;
            if (t > n) t = 0;
            else t = a[t];
            a[i] += t + 1;
            b[i] = a[i] * (a[i] - 1) / 2;
        }
        v = b[1];
        for (int i = 0;i < m;i ++)
        {
            scanf("%lld",&t);
            k[t] = !k[t];
            if (k[t]) add(t);
            else remove(t);
            printf("%lld\n",v);
        }
    }
    return 0;
}