HDU 3726 Graph and Queries 平衡树+前向星+并查集+离线操作+逆向思维 数据结构大综合题

Graph and Queries

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

You are given an undirected graph with N vertexes and M edges. Every vertex in this graph has an integer value assigned to it at the beginning. You’re also given a sequence of operations and you need to process them as requested. Here’s a list of the possible operations that you might encounter:

1. Deletes an edge from the graph. The format is [D X], where X is an integer from 1 to M, indicating the ID of the edge that you should delete. It is guaranteed that no edge will be deleted more than once.

2. Queries the weight of the vertex with K-th maximum value among all vertexes currently connected with vertex X (including X itself). The format is [Q X K], where X is an integer from 1 to N, indicating the id of the vertex, and you may assume that K will always fit into a 32-bit signed integer. In case K is illegal, the value for that query will be considered as undefined, and you should return 0 as the answer to that query.

3. Changes the weight of a vertex. The format is [C X V], where X is an integer from 1 to N, and V is an integer within the range [-106, 106].

The operations end with one single character, E, which indicates that the current case has ended. For simplicity, you only need to output one real number - the average answer of all queries.

Input

There are multiple test cases in the input file. Each case starts with two integers N and M (1 <= N <= 2 * 104, 0 <= M <= 6 * 104), the number of vertexes in the graph. The next N lines describes the initial weight of each vertex (-106 <= weight[i] <= 106). The next part of each test case describes the edges in the graph at the beginning. Vertexes are numbered from 1 to N. The last part of each test case describes the operations to be performed on the graph. It is guaranteed that the number of query operations [Q X K] in each case will be in the range [1, 2 * 105], and there will be no more than 2 * 105 operations that change the values of the vertexes [C X V].
There will be a blank line between two successive cases. A case with N = 0, M = 0 indicates the end of the input file and this case should not be processed by your program.

Output

For each test case, output one real number – the average answer of all queries, in the format as indicated in the sample output. Please note that the result is rounded to six decimal places.

Sample Input

3
20
1 2
3
3
D 3
Q 1 2
Q 2 1
D 2
Q 3 2
C 1 50
Q 1 1
E
3
20
1 2
3
3
Q 1 1
Q 1 2
Q 1 3
E
0

Sample Output

Case 1: 25.000000
Case 2: 16.666667

【Hint】

For the first sample:
D 3 – deletes the 3rd edge in the graph (the remaining edges are (1, 2) and (2, 3))
Q 1 2 – finds the vertex with the second largest value among all vertexes connected with 1. The answer is 20.
Q 2 1 – finds the vertex with the largest value among all vertexes connected with 2. The answer is 30.
D 2 – deletes the 2nd edge in the graph (the only edge left after this operation is (1, 2))
Q 3 2 – finds the vertex with the second largest value among all vertexes connected with 3. The answer is 0 (Undefined).
C 1 50 – changes the value of vertex 1 to 50.
Q 1 1 – finds the vertex with the largest value among all vertex connected with 1. The answer is 50.
E – This is the end of the current test case. Four queries have been evaluated, and the answer to this case is (20 + 30 + 0 + 50) / 4 = 25.000.

For the second sample, caution about the vertex with same weight:
Q 1 1 – the answer is 20
Q 1 2 – the answer is 20
Q 1 3 – the answer is 10

题意

给出一张无向图，并在图中进行多种操作：

1.删除一条边；2.改变一个点的权值；3.询问x能够到达的所有点中，第k大的是多少

分析

花费了好多时间在这道题上，算是这段时间中做到的最综合的数据结构题了。

首先本题的无向图一开始就是个陷阱，如果单纯地从图的角度来考虑，每次询问都需要遍历全图来找第k大的值，这显然是不可取的，而中间又存在删边操作，图的连通性不是稳定的，结点的权值会变，而且可能多次改变，所以整个图是完全不稳定的，没办法用图论的方法来解决。

考虑倒过来操作，如果我们从做完所有操作之后最后的结果图出发，逆序回去，则原本的删边可以看成是将两个连通块连接到一起，询问第k值是在x点当前所属的连通块中进行，对点权的修改也是，而对于每一个独立的连通块，最后这两步可以用平衡树来实现。

所以算法的雏形就有了，询问连通块k值、修改连通块中点的点权操作——平衡树，维护点的连通性——并查集，保存点权的修改信息——前向星

完整过程：

1.首先从完整图出发，读入所有操作，记录删掉的边，按顺序记录点权的变化情况，记录其他信息；

2.用删边信息建立终图的连通性，并查集维护，对于每一个独立的连通块，建立一个独立的平衡树（这里我用的是SBT，网上题解搜出来好多人用的Splay，我其实有点不太理解，感觉这里没有需要用到Splay特殊结构的地方，单纯的维护平衡树的话Splay的稳定性和效率应该是不如SBT的。有大神路过看到这个的话，希望能交流下~~~）；

3.从最后一条操作开始逆序回来：

i. 询问，则在x所属的平衡树中找第k值；

ii. 修改，则在x所属的平衡树中删掉原始的值，插入新值，这里对点权的顺序维护我用了前向星，要保证点权的操作也是要有序的；

iii.删边，在这里就是如果两个点属于两个不同的连通块，则将两个连通块连起来，并查集合并，同时平衡树合并。平衡树合并的时候只能把小的那棵树一个一个加到大的树中去，貌似Splay有个启发式合并，用了finger search神马的东西，可以把合并在O（nlogn）内完成，不会写，ORZ。

后记

写这道题的时候，SBT模板改了两次，-_-///，然后中间有SBT结合并查集结合前向星的，代码里面就是数组套数组套数组套数组……好多地方写着写着就写乱了，教训是如果能简单，一定不要往复杂了写。

然后并查集的教训：father[]绝对不能直接引用，必须调用getfather（）

/* ***********************************************
MYID    : Chen Fan
LANG    : G++
PROG    : HDU3726
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAXN 20010

typedef struct enod
{
    int p,q;
    bool enable;
} enode;
enode e[60010];

typedef struct qnod
{
    int x,k;
} qnode;
qnode lisq[200010];

typedef struct nod
{
    int no,value,time;
} node;
node lis[300010];

int sons[MAXN][2],size[MAXN],data[MAXN],sbt[MAXN],sbttail;
int lisd[60010],taild,tailq,tail,tailtot,lisc[200010],tailc=0;
int start[MAXN],num[MAXN],father[MAXN];
char listot[500010];

void rotate(int &t,int w) //rotate(&node,0/1)
{
    int k=sons[t][1-w];
    if (!k) return ;
    sons[t][1-w]=sons[k][w];
    sons[k][w]=t;
    size[k]=size[t];
    size[t]=size[sons[t][0]]+size[sons[t][1]]+1;
    t=k;
}

void maintain(int& t,bool flag) //maintain(&node,flag)
{
    if (!t) return ;
    if (!flag)
        if (size[sons[sons[t][0]][0]]>size[sons[t][1]]) rotate(t,1);
        else if (size[sons[sons[t][0]][1]]>size[sons[t][1]]) 
        {
            rotate(sons[t][0],0);
            rotate(t,1);
        } else return ;
    else
        if (size[sons[sons[t][1]][1]]>size[sons[t][0]]) rotate(t,0);
        else if (size[sons[sons[t][1]][0]]>size[sons[t][0]])
        {
            rotate(sons[t][1],1);
            rotate(t,0);
        } else return ;
    
    maintain(sons[t][0],false);
    maintain(sons[t][1],true);
    maintain(t,false);
    maintain(t,true);
}

void insert(int& t,int v,int pos) //insert(&root,value)
{
    if (!size[t])
    {
        if (!pos)
        {
            sbttail++;
            pos=sbttail;
        }
        data[pos]=v;
        size[pos]=1;
        sons[pos][0]=0;
        sons[pos][1]=0;
        t=pos;
    } else 
    {
        size[t]++;
        if (v<data[t]) insert(sons[t][0],v,pos);
        else insert(sons[t][1],v,pos);
        maintain(t,v>=data[t]);
    }
}

int last;
int del(int& t,int v) //node=del(&root,key)
{
    size[t]--;
    if (v==data[t]||(v<data[t]&&sons[t][0]==0)||(v>data[t]&&sons[t][1]==0))
    {
        int ret=data[t];
        if (sons[t][0]==0||sons[t][1]==0) 
        {
            last=t;
            t=sons[t][1]+sons[t][0];
        }
        else data[t]=del(sons[t][0],data[t]+1);
        return ret;
    } else
    if (v<data[t]) return del(sons[t][0],v);
    else return del(sons[t][1],v);
}

int select(int t,int k)
{
    if (k==size[sons[t][0]]+1) return t;
    if (k<=size[sons[t][0]]) return select(sons[t][0],k);
    else return select(sons[t][1],k-1-size[sons[t][0]]);
}

void clean_father(int n)
{
    for (int i=1;i<=n;i++)
    {
        father[i]=i;
        sbt[i]=i;
    }
} 

int getfather(int x)
{
    if (father[x]!=x) father[x]=getfather(father[x]);
    return father[x];
}

void link(int x,int y)
{
    int xx=getfather(x),yy=getfather(y);
    if (size[sbt[xx]]>size[sbt[yy]]) 
    {
        father[yy]=xx;
        while(size[sbt[yy]]>0) 
        {
            int temp=del(sbt[yy],data[sbt[yy]]);
            insert(sbt[xx],temp,last);    
        }
    }
    else 
    {
        father[xx]=yy;
        while(size[sbt[xx]]>0) 
        {
            int temp=del(sbt[xx],data[sbt[xx]]);
            insert(sbt[yy],temp,last);
        }
    }
}

bool op(node a,node b)
{
    if (a.no==b.no) return a.time<b.time;
    else return a.no<b.no;
}

int main()
{
    freopen("3726.txt","r",stdin);
    
    int n,m,tt=0;
    while(scanf("%d%d",&n,&m)==2&&(n+m>0))
    {
        for (int i=1;i<=n;i++)
        {
            lis[i].no=i;
            lis[i].time=i;
            scanf("%d",&lis[i].value);
        }
        for (int i=1;i<=m;i++)
        {
            scanf("%d%d",&e[i].p,&e[i].q);
            e[i].enable=true;
        }
        taild=0;tailq=0;tailc=0;tail=n;tailtot=0;
        bool doit=true;
        while(doit)
        {
            char c=getchar();
            while(c!='D'&&c!='Q'&&c!='C'&&c!='E') c=getchar();
            tailtot++;
            listot[tailtot]=c;
            switch(c)
            {
                case 'D':
                    taild++;
                    scanf("%d",&lisd[taild]);
                    e[lisd[taild]].enable=false;
                    break;
                case 'Q':
                    tailq++;
                    scanf("%d%d",&lisq[tailq].x,&lisq[tailq].k);
                    break;
                case 'C':
                    tail++;
                    lis[tail].time=tail;
                    scanf("%d%d",&lis[tail].no,&lis[tail].value);
                    tailc++;
                    lisc[tailc]=lis[tail].no;
                    break;
                default:
                    doit=false;
            }
        }

        sort(&lis[1],&lis[tail+1],op);
        int o=0;
        memset(num,0,sizeof(num));
        for (int i=1;i<=tail;i++)
        {
            if (o!=lis[i].no)
            {
                o=lis[i].no;
                start[o]=i;
            }
            num[o]++;
        }

        clean_father(n);
        sbttail=0;
        memset(size,0,sizeof(size));
        for (int i=1;i<=n;i++) insert(sbt[i],lis[start[i]+num[i]-1].value,0);
        for (int i=1;i<=m;i++)
        if (e[i].enable)
        if (getfather(e[i].p)!=getfather(e[i].q)) 
        link(e[i].p,e[i].q);

        int ansq=tailq;
        double ans=0;
        for (int i=tailtot-1;i>=1;i--)
        switch(listot[i])
        {
            case 'Q':
                if (lisq[tailq].k>0&&size[sbt[getfather(lisq[tailq].x)]]>=lisq[tailq].k) 
                    ans+=data[select(sbt[getfather(lisq[tailq].x)],size[sbt[getfather(lisq[tailq].x)]]-lisq[tailq].k+1)];
                tailq--;
                break;
            case 'D':
                if (getfather(e[lisd[taild]].p)!=getfather(e[lisd[taild]].q))
                    link(e[lisd[taild]].p,e[lisd[taild]].q);
                taild--;
                break;
            case 'C':
                num[lisc[tailc]]--;
                del(sbt[getfather(lisc[tailc])],lis[start[lisc[tailc]]+num[lisc[tailc]]].value);
                insert(sbt[getfather(lisc[tailc])],lis[start[lisc[tailc]]+num[lisc[tailc]]-1].value,last);
                tailc--;
        }
        tt++;
        printf("Case %d: %.6f\n",tt,ans/ansq);
    }

    return 0;
}