2015
09-17

Problem Description
but you know she is very lazy so that she wants you to help her write a program to complete this task. Surly
Zhanyl is able to solve this question, but you know, she is just lazy …
Here is the problem, you are given n numbers, each number i has a value Ai, initially they are in different set.
Following there are m operations/querys.
The following is 5 possible kinds of oprations/querys:
1 u v: Union the set u belongs to and the set v belongs to.
2 u v: Delete u from its original set and add it to the set v belongs to.
3 u x: change the value of u to x.  1<=x<=109
4 u: query how many numbers you can choose most in set which u belongs to, so no three numbers can form a triangle.
5 u l r: query the gcd of the numbers between [l,r] in the set u belongs to, if there is no number between [l,r],you can suppose the answer is -1.  1<=l<=r<=109
Because Zhanyl is a good person, so she guarantee 1<=u,v<=n above.
You need to tell Zhanyl the answer to each query.

Input
The first line of the input is a single integer T which is the number of test cases.Then comes the T test cases .
For each test case, the first line contains two integer n and m, n is the number of set initially, m is the number
of operations/querys.
Following line contains n integers, A1, A2, … , An, the value of i-th number.
Following m lines, each line is a operation or query.

Note that 1<=n,m<=105, 1<=Ai<=109

TLE持续中。。。。。
TLE持续中。。。。。

MD，爆粗口了。。。。。

233333333333333333333333333333

/* **********************************************
Author      : wuyiqi
Created Time: 2013-8-16 8:24:44
File Name   : hdu 4680.cpp
*********************************************** */
#include <cstring>
#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
#define L x->c[0]
#define R x->c[1]
#define KT  root->c[1]->c[0]
const int  maxn = 300010;
const int lim = 1000000000;
int GCD(int a,int b) {
if(a<0||a>lim) return b;
if(b<0||b>lim) return a;
return !b ? a : GCD(b,a%b);
}
struct node {
struct node *c[2] , *fa;
int id;
int sz;
int gcd;
int val;
int who;
bool d() {
return fa->c[0] == this;
}
void setc(int d,node *s) {
c[d] = s;
s->fa = this;
}
void up() {
sz = c[0]->sz + c[1]->sz + 1;
gcd = GCD(c[0]->gcd,c[1]->gcd);
gcd = GCD(gcd,val);
}
void clear(node *null) {
c[0] = c[1] = null;
}
}NODE[maxn] , *null = &NODE[0];
node* Q[maxn];
node* ID[maxn];
int Type;
int n;
int top;
struct _x_x_{
int type;
node* root;
void Rotate(node *x,int f){
node *y = x->fa;
y->setc(!f,x->c[f]);
x->fa = y->fa;
if(y->fa != null) y->fa->setc(!y->d(),x);
x->setc(f,y);
y->up();
}
void Splay(node *x,node *goal) {
while(x->fa!=goal) {
if(x->fa->fa == goal) Rotate(x,x->d());
else {
int f = x->fa->d();
x->d() == f ? Rotate(x->fa,f) : Rotate(x,!f);
Rotate(x,f);
}
}
x->up();
if(goal == null)  {
root = x;
}
}
void RTO(int k,node *goal) {
node *x = root;
while(L->sz + 1 != k) {
if(k < L->sz + 1) x = L;
else {
k -= L->sz + 1;
x = R;
}
}
Splay(x,goal);
}
node* new_node(node *fa,int v) {
node *x = &NODE[++top];
x->id = top;
x->c[0] = x->c[1] = null;
x->sz = 1;
x->val = v;
x->gcd = v;
x->fa = fa;
ID[top] = x;
return x;
}
void init(int v) {
root = new_node(null,v);
type = ++Type;
root->who = type;
}
void Del_root() {
node *t = root;
if(t->c[1] != null) {
root = t->c[1];
RTO(1,null);
root->c[0] = t->c[0];
if(root->c[0] != null)
root->c[0]->fa = root;
} else  {
root = root->c[0];
}
root->fa = null;
if(root != null) root->up();
}
void Delete(node *x) {
Splay(x,null);
Del_root();
}
void Insert(node *x) {
x->clear(null);     //插入一个节点前不能忘记清空它的左右儿子
insert(root,x);
Splay(x,null);
x->who  = type;
}
void insert(node* &x,node *y) {
if(x == null) {
x = y;
return ;
}
if(y->val <= x->val) {
insert(x->c[0],y);
x->c[0]->fa = x;
} else {
insert(x->c[1],y);
x->c[1]->fa = x;
}
x->up();
}
void Change(int u,int v) {
node *tmp = ID[u+2*n];
Splay(tmp,null);
Del_root();
tmp->val = v;
Insert(tmp);
}
node *find_succ(node *x,int v) {  // equal or bigger than v
if(x == null) return x;
if(x->val == v) return x;
else if(x->val > v) {
node *tmp = find_succ(x->c[0],v);
return tmp == null ? x : tmp;
}else {
return find_succ(x->c[1],v);
}
}
node *find_pre(node *x,int v) {  // strictly less than v
if(x == null) return x;
if(x->val < v) {
node *tmp = find_pre(x->c[1],v);
return tmp == null ? x : tmp;
} else {
return find_pre(x->c[0],v);
}
}
int Gao() {
if(root->sz <= 4)  return root->sz - 2;
RTO(2,null);
int a = root->val;
RTO(3,null);
int b = root->val;
int ans = 2;
while(true){
if(a + b > lim) break;
int c = find_succ(root,a+b)->val;
if(c > lim || c == -1) break;
a = b; b = c;
ans++;
}
return ans;
}
int Solve(int l,int r) {
node *pre = find_pre(root,l);
node *succ = find_succ(root,r+1);
Splay(pre,null);
Splay(succ,root);
return KT->gcd;
}
void Merge(_x_x_ &tree) {
int head = 0, tail = 0;
tree.RTO(1,null);
tree.RTO(tree.root->sz,tree.root);
Q[++tail] = tree.KT;
if(fr->c[0] != null) Q[++tail] = fr->c[0];
if(fr->c[1] != null) Q[++tail] = fr->c[1];
Insert(fr);//此处吐血了一整天，上面的改回来了，这里却没改insert(root,fr);
fr->who = type;
}
tree.KT = null;
tree.root->c[1]->up();
tree.root->up();
}
}spt[maxn];
void prepare() {
null->id = 0;
null->c[0] = null->c[1] = null->fa = NULL;
null->sz = null->val = 0;
null->gcd = -1;
Type = 0;
top = 0;
}
int main()
{
int t,m,ca=1,op,u,v,l,r,x;
scanf("%d",&t);
while(t--) {
prepare();
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++){
spt[i].init(-1);
node *tmp =  spt[i].new_node(null,lim+1);
spt[i].Insert(tmp);
}
for(int i = 1,a; i <= n; i++) {
scanf("%d",&a);
node *tmp = spt[i].new_node(null,a);
spt[i].Insert(tmp);
}
int tot = 0;
printf("Case #%d:\n",ca++);
while(m--) {
scanf("%d",&op);
if(op == 1) {
scanf("%d%d",&u,&v);
node *tmp1 = ID[u+2*n] , *tmp2 = ID[v+2*n];
int tree1 = tmp1->who;
int tree2 = tmp2->who;
if(tree1 == tree2) continue;
int sz1 = spt[tree1].root->sz;
int sz2 = spt[tree2].root->sz;
if(sz1 > sz2) {
spt[tree1].Merge(spt[tree2]);
} else {
spt[tree2].Merge(spt[tree1]);
}
} else if(op == 2) {
scanf("%d%d",&u,&v);
node *tmp1 = ID[u+2*n] , *tmp2 = ID[v+2*n];
int tree1 = tmp1->who;
int tree2 = tmp2->who;
spt[tree1].Delete(tmp1);
spt[tree2].Insert(tmp1);
} else if(op == 3) {
scanf("%d%d",&u,&x);
node *tmp = ID[u+2*n];
int tree = tmp->who;
spt[tree].Change(u,x);
}  else if(op == 4) {
scanf("%d",&u);
node *tmp = ID[u+2*n];
int tree = tmp->who;
printf("%d\n",spt[tree].Gao());
} else {
scanf("%d%d%d",&u,&l,&r);
node *tmp = ID[u+2*n];
int tree = tmp->who;
printf("%d\n",spt[tree].Solve(l,r));
}
}
}
return 0;
}