2015
02-21

# Graph and Queries

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.

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.

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.

3 3
10
20
30
1 2
2 3
1 3
D 3
Q 1 2
Q 2 1
D 2
Q 3 2
C 1 50
Q 1 1
E

3 3
10
20
20
1 2
2 3
1 3
Q 1 1
Q 1 2
Q 1 3
E

0 0

Case 1: 25.000000
Case 2: 16.666667

HintFor 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 �C the answer is 20
Q 1 2 �C the answer is 20
Q 1 3 �C the answer is 10



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

#define KT ch[ch[root][1]][0]
#define LC ch[x][0]
#define RC ch[x][1]
#define N 61001
#define M 61000
#define Q 500000
using namespace std;

int fa[N];
int ch[N][2];
int sz[N];
int top1;
int top2;
int ss[N];
int que[N];
int nodque[N],top3;
int val[N];
int nodbelong[N];
int ini[N];
const int inf=1e9;
vector<int> g[N];
struct SplayTree{
int root;
void rotate(int x,bool f){
int y=fa[x];
int z=fa[y];
pushdown(y);
pushdown(x);
ch[y][!f]=ch[x][f];
fa[ch[x][f]]=y;
fa[x]=z;
if (z) {
ch[z][ch[z][1]==y] = x;
}
ch[x][f] = y;
fa[y]=x;
pushup(y);
}
void splay(int x, int g) {
int y = fa[x];
pushdown(x);
while(y!=g){
int z= fa[y];
bool f = (ch[y][0]==x);
if(z != g && f == (ch[z][0]==y)){
rotate(y,f);
}
rotate(x,f);
y=fa[x];
}
pushup(x);
if(g==0) root = x;
}
void rotateTo(int k,int g) {
int x=root;
pushdown(x);
while(sz[LC] != k){
if(k<sz[LC]){
x=LC;
}else{
k -= sz[LC] + 1;
x = RC;
}
pushdown(x);
}
splay(x,g);
}
void build(int l,int r,int f){
if(l>r){
return ;
}
int x = (l + r) >> 1;
LC = (x - 1 >= l)? (x - 1 + l)>> 1 :0;
RC = (r >= x + 1)? (x + 1 + r)>> 1 :0;
fa[x] = f;
build(l,x - 1,x);
build(x + 1,r,x);
pushup(x);
}
void erase(int x){
if(x==0)
return;
int father= fa[x];
}
}
}
ch[father][ch[father][1]==x]=0;
pushup(father);
}
void makeTree(int &x, int l, int r, int f ,vector<int>& g){
if(l > r){
return;
}
int m=(l+r)>>1;
newNode(x, ini[g[m]],g[m]);
makeTree(LC,l,m-1,x,g);
makeTree(RC,m+1,r,x,g);
fa[x]=f;
pushup(x);
}
void treaval(int x){
if (x) {
pushdown(x);
treaval(LC);
printf("@%d",val[x]);

//ans[cnt++]=val[x];
treaval(RC);
}
}
void dfs(int x){
if (x) {
pushdown(x);
dfs(LC);
nodque[top3++]=x;
dfs(RC);
}
}
void newNode(int &x,int c,int id){
if(id){
x=id;//直接另节点号一致
}
else if(top2){
x = ss[--top2];
} else {
x = ++top1;//top1从n+1，开始
}
LC = 0;
RC = 0;
fa[x] =0;
sz[x] = 1;

val[x]=c;
}
void pushdown(int x){

}
void pushup(int x){
sz[x]=1+sz[LC]+sz[RC];
}

void debug(){
treaval(root);
cout<<endl;
}
void cutTo(int l,int r,int c){
rotateTo(l-1,0);
rotateTo(r+1,root);
int tmp=KT;
KT=0;
pushup(ch[root][1]);
pushup(root);

rotateTo(c,0);
rotateTo(c+1,root);
fa[tmp]=ch[root][1];
KT=tmp;
pushup(ch[root][1]);
pushup(root);
}

void init(vector<int>&g){

root=0;
int n=g.size();
newNode(root,inf,0);
newNode(ch[root][1],-inf,0);
fa[ch[root][1]]=root;
//for(int i=1;i<=n;i++)scanf("%d",&num[i]);
makeTree(KT,0,n-1,ch[root][1],g);
pushup(ch[root][1]);
pushup(root);
}
int size(){
return sz[root]-2;
}
int find(int x,int v,int cur){
if(val[x]>=v){
cur=x;
return RC?find(RC,v,cur):cur;
}else{
return LC?find(LC,v,cur):cur;
}
//        if(val[LC]<v){
//            return find(LC,v);
//        }else if(val[RC]>v){
//            return find(RC,v);
//        }else
//            return val[x]<v?LC:RC;
}
void insert(int y){//将y节点插入splay
int x=find(root,val[y],root);
splay(x,0);
int s=sz[LC]+1;
rotateTo(s,root);
fa[y]=ch[root][1];
ch[y][0]=0;
ch[y][1]=0;
KT=y;
sz[y]=1;
pushup(ch[root][1]);
pushup(root);
}
void merge(SplayTree spt){
top3=0;
spt.dfs(spt.root);
rotateTo(1,0);
int tmp=nodbelong[root];
for(int i=1;i<top3-1;i++){
insert(nodque[i]);
nodbelong[nodque[i]]=tmp;
}
}
void change(int x,int k){
splay(x,0);
int s=sz[LC];
rotateTo(s-1,0);
rotateTo(s+1,root);

KT=0;
pushup(ch[root][1]);
pushup(root);

val[x]=k;
insert(x);
}
int query(int k){
if(k>size()||k<=0)return 0;
rotateTo(k,0);
return val[root];
}

}spt[N];

struct edge{
int flag;
int to;
int next;
}e[M<<1];
e[num].flag=0;
e[num].to=v;
}
}
struct Ques{
char op;
int x,k;
void set(char o,int xx,int kk){
op=o;
x=xx;
k=kk;
}
}questa[Q];
int top4;
int vis[N];

void dfs(int x,int id){
vis[x]=1;
nodbelong[x]=id;
dfs(e[i].to,id);
}
}
int cmp(int i,int j){
return ini[i]>ini[j];
}
void init(int n,int m){
num=top4=0;
top1=n;top2=0;
memset(vis,0,sizeof(int)*(n+1));
}
void solve( int n,int m){

int u,v;
int x,k;
char op[10];

init(n,m);
for(int i=1;i<=n;i++){
scanf("%d",&ini[i]);
}
for(int i=0;i<m;i++){
scanf("%d%d",&u,&v);
}
top4=0;
while(scanf("%s",op),op[0]!='E'){
if(op[0]=='D'){
scanf("%d",&x);
int id=(x-1)*2;
questa[top4++].set(op[0],e[id].to,e[id^1].to);
e[id].flag=1;
e[id^1].flag=1;
}else if(op[0]=='Q'){
scanf("%d%d",&x,&k);
questa[top4++].set(op[0],x,k);
}else{
scanf("%d%d",&x,&k);
questa[top4++].set(op[0],x,ini[x]);
ini[x]=k;
}
}
int cnt=0;
for(int i=1;i<=n;i++)if(!vis[i]){
dfs(i,cnt++);
}
for(int i=1;i<=n;i++){
g[nodbelong[i]].push_back(i);
}
for(int i=0;i<cnt;i++){
sort(g[i].begin(),g[i].end(),cmp);
//        for(int j=g[i].size()-1;j>=0;j--){
//            cout<<g[i][j]<<" ";
//        }
//        cout<<endl;
}
for(int i=0;i<cnt;i++){
spt[i].init(g[i]);
}
//    for(int i=0;i<cnt;i++)
//        cout<<spt[i].size()<<endl;
double ans=0;
int ret=0;
while(top4--){
char op=questa[top4].op;
x=questa[top4].x;k=questa[top4].k;
if(op=='D'){
int id1=nodbelong[x];
int id2=nodbelong[k];
int sz1=spt[id1].size();
int sz2=spt[id2].size();
if(id1==id2)continue;
if(sz1>sz2){
spt[id1].merge(spt[id2]);
}else{
spt[id2].merge(spt[id1]);
}
}else if(op=='C'){
int id=nodbelong[x];

spt[id].change(x,k);
}else{
int id=nodbelong[x];
//spt[id].debug();
//int t=spt[id].query(k);
ans+=spt[id].query(k);
//cout<<t<<endl;
ret++;
}
}
printf("%.6lf\n",(double)ans/ret);
for(int i=0;i<cnt;i++)g[i].clear();
}
int main()
{
int n,m;

int cas=1;
while(scanf("%d%d",&n,&m),n||m){
printf("Case %d: ",cas++);
solve(n,m);
}
return 0;
}


1. #include <cstdio>
#include <algorithm>

struct LWPair{
int l,w;
};

int main() {
//freopen("input.txt","r",stdin);
const int MAXSIZE=5000, MAXVAL=10000;
LWPair sticks[MAXSIZE];
int store[MAXSIZE];
int ncase, nstick, length,width, tmp, time, i,j;
if(scanf("%d",&ncase)!=1) return -1;
while(ncase– && scanf("%d",&nstick)==1) {
for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
for(time=-1,i=0;i<nstick;++i) {
tmp=sticks .w;
for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
if(j==time) { store[++time]=tmp; }
else { store[j+1]=tmp; }
}
printf("%dn",time+1);
}
return 0;
}

2. #include <cstdio>

int main() {