题目大义
有一张n结点m条边的无向图，每个结点都有一个权值，你的任务是执行一系列操作，共3种。
1、D X 删除ID为x的边
2、Q X k 计算与x相连的边的第k大权值，如果不存在输出0
3、C X V 把X的权值改为V
题目链接什么的还是给一个 https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3032
本体实际上就是一个名次树+离线算法
离线算法：先读入所有的操作，删除所有边得到最终的图，然后反过来操作，在适合的时候加上边，在适合的时候改变点的权值，然后用名次树来维护每个连通分量，加边的时候就用并查集判一下就可以了，然后再将两棵树合并
名次树：实际上就是treap tree这种平衡树加上了一个名次功能（其他平衡树好像感觉也可以，但我弱鸡写不来）
都说到这里了就来顺便说一下treap tree吧，前面说过了，treap tree就是一种平衡树，而且应该是最简单也最方便的平衡树了，虽然不一定最快，但插入和删除都只有一种情况，写起来很舒服，它的基本操作就是基本的3种：旋转，插入，删除
旋转：旋转和其他的都差不多了，就是左旋右旋，想象成你的手去提一下就好了，然后再稍微做个小手术，让它还是保持二叉平衡树的基本性质就可以了
插入：实际上二叉平衡树的插入无论如何都只有一种，问题就在于插入后如何去平衡，treap tree采用的是随机数平衡法，再插入每个点的时候给每个点一个随机数，然后让这些随机数通过旋转保持大根堆的性质，这样来随机平衡它，实际效果很好
删除：删除的话子树处理是最大的问题，如果要删除的结点只有一颗子树就非常好办了，直接用那棵子树覆盖掉要删除的结点就好了，如果有多棵子树就将随机数较大的子树旋转上来，然后递归去删除即可，虽然要删除的结点在对立面会不满足大根堆的性质，但其它的节点都是满足的，所以删除后整棵树还是满足treap tree的基本性质
然后就是这道题相当金典，可以好好去推敲一下，我的代码在下面，因为网各种炸，vj和la都叫不上去，就不交了，样例过了，但不保证一定会对，同时附上刘汝佳的代码，我也是看了他的书的
我的代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<stack>
#define N 20005
#define M 60005
using namespace std;
struct tree2
{
tree2 *son[2];
int num,n,r;
int com(int x)
{
if(x==n)return -1;
return x>n?1:0;
}
}*root[N],dizhi[N],*null;
int d[N],t,tt;
int fa[M];
int n,m,kase;
int edge1[M],edge2[M],b[M];
int tot=0,cnt=0;
void update(tree2 *&tree)
{
tree->num=tree->son[0]->num+tree->son[1]->num+1;
}
void rotate(tree2 *&tree,int d)//d=0左旋 d=1右旋
{
tree2 *k=tree->son[d^1];
tree->son[d^1]=k->son[d];
k->son[d]=tree;
update(tree);
update(k);
tree=k;
}
int insert(tree2 *&tree,int x)
{
if(tree==null)
{
tree=&dizhi[t++];
tree->n=x;
tree->r=rand();
tree->num=1;
tree->son[0]=tree->son[1]=null;
update(tree);
return 1;
}
int d=tree->com(x);
if(d==-1)d=1;
insert(tree->son[d],x);
if(tree->son[d]->r>tree->r)rotate(tree,d^1);
update(tree);
return 1;
}
int remove(tree2 *&tree,int x)
{
if(tree==null||tree==NULL)return -1;
int d=tree->com(x);
if(d==-1)
{
if(tree->son[0]==null)tree=tree->son[1];
else if(tree->son[1]=null)tree=tree->son[0];
else
{
int d2=tree->son[0]->r>tree->son[1]->r?1:0;
rotate(tree,d2);
remove(tree->son[d2],x);
}
return 1;
}
remove(tree->son[d],x);
}
bool find(tree2 *tree,int x)
{
if(tree==null||tree==NULL)return 0;
int d=tree->com(x);
if(d==-1)return 1;
return (tree->son[d],x);
}
int kth(tree2 *tree,int k)
{
if(tree==null||tree==NULL)return 0;
if(k>tree->num||k<0)return 0;
int s=tree->son[1]->num;
if(k==s+1)return tree->n;
if(k<=s)return kth(tree->son[1],k);
return kth(tree->son[0],k-s-1);
}
void mergeto(tree2 *&tree1,tree2 *&tree2)//将tree1全部插入tree2
{
if(tree1->son[0]!=null)mergeto(tree1->son[0],tree2);
if(tree1->son[1]!=null)mergeto(tree1->son[1],tree2);
insert(tree2,tree1->n);
tree1=null;
}
int get_fa(int x)
{
return x==fa[x]?x:fa[x]=get_fa(fa[x]);
}
void addedge(int x)
{
int s=edge1[x],v=edge2[x];
int fa1=get_fa(s),fa2=get_fa(v);
if(fa1==fa2)return ;
if(root[s]->num>root[v]->num)
{
mergeto(root[v],root[s]);
fa[v]=fa[s];
return ;
}
mergeto(root[s],root[v]);
fa[s]=fa[v];
}
void change_v(int x,int v)
{
int f=get_fa(x);
remove(root[f],d[x]);
d[x]=v;
insert(root[f],d[x]);
}
#include<ctime>
int main()
{
while(scanf("%d%d",&n,&m)==2)
{
memset(dizhi,0,sizeof(dizhi));
memset(b,0,sizeof(b));
t=0;
null=&dizhi[t++];
null->num=0;
if(n==0&&m==0)return 0;
for(int i=1;i<=n;i++)root[i]=null;
stack<int>num1,num2,type;
for(int i=1;i<=n;i++)scanf("%d",&d[i]);
for(int i=1;i<=m;i++)
scanf("%d%d",&edge1[i],&edge2[i]);
for(;;)
{
char c;
scanf("%c",&c);
if(c=='E')break;
if(c=='D')
{
int x;
scanf("%d",&x);
b[x]=1;
type.push(1);
num1.push(x);
num2.push(0);
continue;
}
if(c=='Q')
{
int x,k;
scanf("%d%d",&x,&k);
type.push(2);
num1.push(x);
num2.push(k);
continue;
}
if(c=='C')
{
int x,v;
scanf("%d%d",&x,&v);
type.push(3);
num1.push(x);
num2.push(d[x]);
d[x]=v;
}
}
for(int i=1;i<=n;i++)
insert(root[i],d[i]);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++)
if(!b[i])addedge(i);
int p=0;
tot=0,cnt=0;
while(!type.empty())
{
int temp=type.top();type.pop();
int n1=num1.top();num1.pop();
int n2=num2.top();num2.pop();
if(temp==1)addedge(n1);
if(temp==2)
{
cnt++;
tot+=kth(root[get_fa(n1)],n2);
}
if(temp==3)change_v(n1,n2);
}
printf("Case %d %.6lf\n",++kase,tot/(double)cnt);
}
return 0;
}
刘汝佳代码：
// LA5031/UVa1479 Graph and Queries
// Rujia Liu
#include<cstdlib>
struct Node {
Node *ch[2]; // 左右子树
int r; // 随机优先级
int v; // 值
int s; // 结点总数
Node(int v):v(v) { ch[0] = ch[1] = NULL; r = rand(); s = 1; }
int cmp(int x) const {
if (x == v) return -1;
return x < v ? 0 : 1;
}
void maintain() {
s = 1;
if(ch[0] != NULL) s += ch[0]->s;
if(ch[1] != NULL) s += ch[1]->s;
}
};
void rotate(Node* &o, int d) {
Node* k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o;
o->maintain(); k->maintain(); o = k;
}
void insert(Node* &o, int x) {
if(o == NULL) o = new Node(x);
else {
int d = (x < o->v ? 0 : 1); // 不要用cmp函数，因为可能会有相同结点
insert(o->ch[d], x);
if(o->ch[d]->r > o->r) rotate(o, d^1);
}
o->maintain();
}
void remove(Node* &o, int x) {
int d = o->cmp(x);
int ret = 0;
if(d == -1) {
Node* u = o;
if(o->ch[0] != NULL && o->ch[1] != NULL) {
int d2 = (o->ch[0]->r > o->ch[1]->r ? 1 : 0);
rotate(o, d2); remove(o->ch[d2], x);
} else {
if(o->ch[0] == NULL) o = o->ch[1]; else o = o->ch[0];
delete u;
}
} else
remove(o->ch[d], x);
if(o != NULL) o->maintain();
}
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxc = 500000 + 10;
struct Command {
char type;
int x, p; // 根据type, p代表k或者v
} commands[maxc];
const int maxn = 20000 + 10;
const int maxm = 60000 + 10;
int n, m, weight[maxn], from[maxm], to[maxm], removed[maxm];
// 并查集相关
int pa[maxn];
int findset(int x) { return pa[x] != x ? pa[x] = findset(pa[x]) : x; }
// 名次树相关
Node* root[maxn]; // Treap
int kth(Node* o, int k) { // 第k大的值
if(o == NULL || k <= 0 || k > o->s) return 0;
int s = (o->ch[1] == NULL ? 0 : o->ch[1]->s);
if(k == s+1) return o->v;
else if(k <= s) return kth(o->ch[1], k);
else return kth(o->ch[0], k-s-1);
}
void mergeto(Node* &src, Node* &dest) {
if(src->ch[0] != NULL) mergeto(src->ch[0], dest);
if(src->ch[1] != NULL) mergeto(src->ch[1], dest);
insert(dest, src->v);
delete src;
src = NULL;
}
void removetree(Node* &x) {
if(x->ch[0] != NULL) removetree(x->ch[0]);
if(x->ch[1] != NULL) removetree(x->ch[1]);
delete x;
x = NULL;
}
// 主程序相关
void add_edge(int x) {
int u = findset(from[x]), v = findset(to[x]);
if(u != v) {
if(root[u]->s < root[v]->s) { pa[u] = v; mergeto(root[u], root[v]); }
else { pa[v] = u; mergeto(root[v], root[u]); }
}
}
int query_cnt;
long long query_tot;
void query(int x, int k) {
query_cnt++;
query_tot += kth(root[findset(x)], k);
}
void change_weight(int x, int v) {
int u = findset(x);
remove(root[u], weight[x]);
insert(root[u], v);
weight[x] = v;
}
int main() {
int kase = 0;
while(scanf("%d%d", &n, &m) == 2 && n) {
for(int i = 1; i <= n; i++) scanf("%d", &weight[i]);
for(int i = 1; i <= m; i++) scanf("%d%d", &from[i], &to[i]);
memset(removed, 0, sizeof(removed));
// 读命令
int c = 0;
for(;;) {
char type;
int x, p = 0, v = 0;
scanf(" %c", &type);
if(type == 'E') break;
scanf("%d", &x);
if(type == 'D') removed[x] = 1;
if(type == 'Q') scanf("%d", &p);
if(type == 'C') {
scanf("%d", &v);
p = weight[x];
weight[x] = v;
}
commands[c++] = (Command){ type, x, p };
}
// 最终的图
for(int i = 1; i <= n; i++) {
pa[i] = i; if(root[i] != NULL) removetree(root[i]);
root[i] = new Node(weight[i]);
}
for(int i = 1; i <= m; i++) if(!removed[i]) add_edge(i);
// 反向操作
query_tot = query_cnt = 0;
for(int i = c-1; i >= 0; i--) {
if(commands[i].type == 'D') add_edge(commands[i].x);
if(commands[i].type == 'Q') query(commands[i].x, commands[i].p);
if(commands[i].type == 'C') change_weight(commands[i].x, commands[i].p);
}
printf("Case %d: %.6lf\n", ++kase, query_tot / (double)query_cnt);
}
return 0;
}大概就是这个样子，如果有什么问题，或错误，请在评论区提出，谢谢。