解题思路：
第一种操作，用小集合暴力插入到大集合，可以证明总的时间复杂度O(n*logn);
第二种和第三种操作，每次操作O(logn)
第四种操作，因为任意3个数不能组成一个三角型，则是长边大于等于剩下的两边之和，和斐波那契数列类似，
所以对于10^9的数据范围来说只有几十个，用贪心的思路，从最小的开始，暴力二分查找即可。
第五种操作，因为一个区间的gcd值等于它的所有子区间的gcd值再gcd，所以在每个节点维护一个区间gcd值G，所以G[u]=gcd(val[u],gcd(G[lchild],G[rchlid]));
lchlid和rchlid表示u节点的左右两个孩子，后面用二分找到l,r的左右边界，用splay操作把这个区间旋转成一个子树，答案就是这个节点的G值了，整个过程接近O(logn).
代码如下：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 300010
#define MAXN 300010
const int INF=1<<30;
int tree[MAXN][2],pa[MAXN],cnt[MAXN],G[MAXN],val[MAXN];
int gcd(int a,int b){ return b==0?a:gcd(b,a%b);}
class splaytree
{
public:
int Root;
static int idx;
splaytree(){}
void init(){
Root=newnode(-INF);pa[Root]=0;
tree[Root][1]=newnode(INF);pa[tree[Root][1]]=Root;
update(tree[Root][1]);update(Root);
}
void update(int t)
{
//add your code;
cnt[t]=cnt[tree[t][0]]+cnt[tree[t][1]]+1;
G[t]=val[t];
if(tree[t][0]) G[t]=gcd(G[t],G[tree[t][0]]);
if(tree[t][1]) G[t]=gcd(G[t],G[tree[t][1]]);
}
int newnode(int v){
cnt[++idx]=1;val[idx]=G[idx]=v;
pa[idx]=tree[idx][0]=tree[idx][1]=0;
return idx;
}
static void clear()
{
memset(G,0,sizeof(G));
memset(pa,0,sizeof(pa));
memset(cnt,0,sizeof(cnt));
memset(tree,0,sizeof(tree));
}
//roate function that support left roate action and right roate action
void rotate(int t)
{
int p=pa[t];
int c=(tree[pa[t]][0]==t);
tree[p][!c]=tree[t][c];
if(tree[t][c]) pa[tree[t][c]]=p;
tree[t][c]=p; pa[t]=pa[p];
if(pa[p])tree[pa[p]][tree[pa[p]][1]==p]=t;
pa[p]=t;update(p);update(t);
}
//the important function that support splay action
void splay(int x,int &head)
{
int p,pp;
while(pa[x]&&x!=head){
p=pa[x];
if(p==head) rotate(x);
else {
pp=pa[p];
if((tree[pp][0]==p)==(tree[p][0]==x))
rotate(p),rotate(x);
else rotate(x),rotate(x);
}
}
if(!pa[x]) head=x;
}
//find node by a value in the tree that root is "head"
int findR(int v,int head)
{
int t;
if(head==0) return 0;
if(v==val[head]){
t=findR(v,tree[head][1]);
return (t==0||val[t]>val[head])?head:t;
}
else if(v>val[head]){
return findR(v,tree[head][1]);
}
else {
t=findR(v,tree[head][0]);
return t==0?head:t;
}
}
int findL(int v,int head){
int t;
if(head==0) return 0;
if(v<=val[head]){
return findL(v,tree[head][0]);
}
else {
t=findL(v,tree[head][1]);
return t==0?head:t;
}
}
int findk(int k,int head)
{
int t;
while(head){
t=cnt[tree[head][0]];
if(k==t+1) return head;
else if(k<t+1)
head=tree[head][0];
else {
k-=t+1; head=tree[head][1];
}
}
return 0;
}
void insertNode(int node,int &head)
{
int root=head,p=0,v;
v=val[node];
while(root){
p=root;
if(v<val[root])
root=tree[root][0];
else
root=tree[root][1];
}
if(!p) head=node;
else {
pa[node]=p; tree[p][v>=val[p]]=node;
splay(node,head);
}
}
//make a node by value v and insert it
int insert(int v,int &head)
{
int node=newnode(v);
insertNode(node,head);
return node;
}
//find a node that value is v and remove the node from the tree that root is "head"
void remove(int node,int &head)
{
int l;
if(node)
{
splay(node,head);l=cnt[tree[node][0]];
splay(findk(l,head),head); splay(findk(l+2,head),tree[head][1]);
tree[tree[head][1]][0]=0; update(tree[head][1]); update(head);
}
}
int fun(int a,int b,int &root){
int l,r,c=-1;
l=findL(a,root);r=findR(b,root);
splay(l,root);splay(r,tree[root][1]);
if(tree[r][0]) c=G[tree[r][0]];
if(val[r]<=b){
if(c==-1)
c=val[r];
else
c=gcd(c,val[r]);
}
return c;
}
void make(int t){
cnt[t]=1;G[t]=val[t];
pa[t]=tree[t][0]=tree[t][1]=0;
}
};
int splaytree::idx=0;
void debug(int root)
{
if(!root) return ;
debug(tree[root][0]); printf("%d(%d) ",val[root],root); debug(tree[root][1]);
}
int ST[N],addr[N],ID[N],A[N];
splaytree T[N];
void dfs(int rt){
if(tree[rt][0]) dfs(tree[rt][0]);
if(val[rt]!=-INF&&val[rt]!=INF)
A[++A[0]]=rt;
if(tree[rt][1]) dfs(tree[rt][1]);
}
void create(){
freopen("test.in","w",stdout);
printf("1\n100000 100000\n");
for(int i=1;i<=100000;i++) printf("%d ",i);
printf("\n");
for(int i=1;i<=100000;i++){
if(i%3==0) printf("1 %d %d\n",1,i+1);
else if(i%3==1)printf("5 %d %d %d\n",i,min(i,(i+5000-1)%100000+1),max(i,(i+5000-1)%100000+1));
else printf("4 1\n");
}
}
int main(){
int cass,cas,i,j,n,m,k,t,b,a;
//create();return 0;
//freopen("test.in","r",stdin);
//freopen("test.out","w",stdout);
scanf("%d",&cass);
for(cas=1;cas<=cass;cas++){
splaytree::idx=0;
splaytree::clear();
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++) T[i].init();
for(i=1;i<=n;i++){
scanf("%d",&k);
addr[i]=T[i].insert(k,T[i].Root);
ST[i]=i;ID[addr[i]]=i;
}
int u,v;
printf("Case #%d:\n",cas);
for(i=1;i<=m;i++){
scanf("%d",&t);
switch(t){
case 1:
scanf("%d%d",&u,&v);
if(ST[u]==ST[v]) break;
if(cnt[T[ST[u]].Root]>cnt[T[ST[v]].Root]) swap(u,v);
A[0]=0;dfs(T[ST[u]].Root);
for(j=1;j<=A[0];j++){
ST[ID[A[j]]]=ST[v];T[1].make(A[j]);
T[ST[v]].insertNode(A[j],T[ST[v]].Root);
}
break;
case 2:
scanf("%d%d",&u,&v);
if(ST[u]==ST[v]) break;
T[ST[u]].remove(addr[u],T[ST[u]].Root);
ST[u]=ST[v];T[1].make(addr[u]);
T[ST[v]].insertNode(addr[u],T[ST[v]].Root);
break;
case 3:
scanf("%d%d",&u,&v);
T[ST[u]].remove(addr[u],T[ST[u]].Root);
val[addr[u]]=v;T[1].make(addr[u]);
T[ST[u]].insertNode(addr[u],T[ST[u]].Root);
break;
case 4:
scanf("%d",&u);u=ST[u];
if(cnt[T[u].Root]<=4){ printf("%d\n",cnt[T[u].Root]-2); break;}
a=val[T[u].findk(2,T[u].Root)];k=2;
b=val[T[u].findk(3,T[u].Root)];v=a+b;
while(v<INF){
v=val[T[u].findR(v,T[u].Root)];
if(v<INF) k++; else break;
a=b;b=v;v=a+b;
}
printf("%d\n",k);
break;
case 5:
scanf("%d%d%d",&u,&a,&b);u=ST[u];
printf("%d\n",T[u].fun(a,b,T[u].Root));
break;
}
}
}
return 0;
}
版权声明：本文为laziercs原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。