考场上发现了一个性质：一个节点的父节点=该节点编号-上一个fibonacci数
所以求父亲节点代码
int fa(int x) { for(int i=mx;i;i--) if(fi[i]<x) return x-fi[i]; }
然后我只想到了建树的70%代码，数组越界了又少了30分QAQ
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<queue>
6 #define int long long
7 using namespace std;
8 inline int read()
9 {
10 int f=1,x=0;char ch=getchar();
11 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}
12 while(ch<=‘9‘&&ch>=‘0‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();}
13 return f*x;
14 }
15 const int mx=65;
16 const int maxn=1000000;
17 int fi[mx+10];
18 int d[maxn+5];
19 int f[maxn+5][25];
20 struct node{
21 int v,nxt;
22 }e[maxn];int h[maxn],nu;
23 void add(int x,int y)
24 {
25 e[++nu].v=y;
26 e[nu].nxt=h[x];
27 h[x]=nu;
28 }
29 int gfa(int x)
30 {
31 for(int i=mx;i;i--)
32 if(fi[i]<x)
33 return x-fi[i];
34 }
35 void bfs()
36 {
37 queue<int>q;
38 d[1]=1;
39 q.push(1);
40 while(q.size())
41 {
42 int x=q.front();q.pop();
43 for(int i=h[x];i;i=e[i].nxt)
44 {
45 int y=e[i].v;
46 if(d[y])continue;
47 d[y]=d[x]+1;
48 f[y][0]=x;
49 for(int j=1;j<=21;j++)
50 f[y][j]=f[f[y][j-1]][j-1];
51 q.push(y);
52 }
53 }
54 }
55 int lca(int x,int y)
56 {
57 if(d[x]>d[y])swap(x,y);
58 for(int i=21;i>=0;i--)
59 if(d[f[y][i]]>=d[x])
60 y=f[y][i];
61 if(y==x)return x;
62 for(int i=21;i>=0;i--)
63 if(f[x][i]!=f[y][i])
64 x=f[x][i],y=f[y][i];
65 return f[x][0];
66 }
67 signed main()
68 {
69 //freopen("fibonacci2.in","r",stdin);
70 int m=read(),mxx;
71 fi[0]=fi[1]=1;
72 for(int i=2;i<=mx;i++)
73 fi[i]=fi[i-1]+fi[i-2];
74 for(int i=2;i<=maxn;i++)
75 {
76 int fa=gfa(i);
77 add(fa,i);
78 }
79 bfs();
80 for(int i=1;i<=m;i++)
81 {
82 int x=read(),y=read();
83 printf("%lld\n",lca(x,y));
84 }
85 }
86 /*
87 g++ 1.cpp -o 1
88 ./1
89
90 */
可是考完才发现暴力既好写，又能A
对于输入的两个节点x,y将其中一个向上遍历，并把经过的路径都存入一个vector
然后另一个向上翻，如果在vector中能找到，那此时的y就是答案
时间复杂度O（玄学）
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<queue>
6 #include<vector>
7 #define int long long
8 using namespace std;
9 inline int read()
10 {
11 int f=1,x=0;char ch=getchar();
12 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}
13 while(ch<=‘9‘&&ch>=‘0‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();}
14 return f*x;
15 }
16 const int mx=65;
17 int fi[mx+10];
18 int fa(int x)
19 {
20 for(int i=mx;i;i--)
21 if(fi[i]<x)
22 return x-fi[i];
23 }
24 signed main()
25 {
26 //freopen("data","r",stdin);
27 int m=read();
28 fi[0]=fi[1]=1;
29 for(int i=2;i<=mx;i++)
30 fi[i]=fi[i-1]+fi[i-2];
31 vector<int>v;
32 for(int i=1;i<=m;i++)
33 {
34 int x=read(),y=read();
35 v.clear();
36 while(x>1)
37 {
38 v.push_back(x);
39 x=fa(x);
40 }
41 while(y>1)
42 {
43 vector<int>::iterator res=find(v.begin(),v.end(),y);
44 if(res!=v.end()) break;
45 y=fa(y);
46 }
47 printf("%lld\n",y);
48 }
49 }
50 /*
51 g++ 1.cpp -o 1
52 ./1
53
54 */
vector中查找元素:
vector<int>::iterator res=find(v.begin(),v.end(),y);//在v中查找y if(res!=v.end()) //找到了
考场上只想到了$O(nm)$的纯暴力，
然而以上的这些都能拿到不少的部分分，更有主席树，树套树的高超方法，我却什么都搞不出来
正解：
将（颜色，位置）按照二元组排序，对于查询操作，使用结构体lower_bound二分查找
对于修改操作，暴力修改结构体的pos，
注意若两个颜色不同，那么修改不会改变每个颜色块里的顺序
若相同，不用修改
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define mid ((l+r)>>1) 6 using namespace std; 7 const int maxn=3e5+5; 8 inline int read() 9 { 10 int f=1,x=0;char ch=getchar(); 11 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} 12 while(ch<=‘9‘&&ch>=‘0‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();} 13 return f*x; 14 } 15 int n,sum[maxn],jl[maxn]; 16 struct node{ 17 int pos,da; 18 }a[maxn]; 19 bool cmp(node x,node y){return (x.da==y.da)?x.pos<y.pos:x.da<y.da;} 20 int main() 21 { 22 // freopen("data","r",stdin); 23 n=read();int Q=read(),mc=0; 24 for(int i=1;i<=n;i++) 25 { 26 a[i].da=read(),a[i].pos=i; 27 sum[a[i].da]++; 28 mc=max(mc,a[i].da); 29 jl[i]=a[i].da; 30 } 31 for(int i=1;i<=mc;i++) 32 sum[i]+=sum[i-1]; 33 sort(a+1,a+n+1,cmp); 34 while(Q--) 35 { 36 int opt=read(); 37 if(opt==1) 38 { 39 int L=read(),R=read(),col=read(); 40 node l,r; 41 l.da=col,l.pos=L; 42 r.da=col,r.pos=R; 43 int ll=lower_bound(a+sum[col-1]+1,a+sum[col]+1,l,cmp)-a; 44 int rr=upper_bound(a+sum[col-1]+1,a+sum[col]+1,r,cmp)-a; 45 printf("%d\n",rr-ll); 46 } 47 if(opt==2) 48 { 49 int i=read(); 50 int x=i,y=i+1; 51 if(jl[x]==jl[y])continue; 52 node xx,yy; 53 xx.pos=x,xx.da=jl[x];int c1=jl[x]; 54 yy.pos=y,yy.da=jl[y];int c2=jl[y]; 55 int xp=lower_bound(a+sum[c1-1]+1,a+sum[c1]+1,xx,cmp)-a; 56 int yp=lower_bound(a+sum[c2-1]+1,a+sum[c2]+1,yy,cmp)-a; 57 a[xp].pos=y,a[yp].pos=x; 58 jl[x]=yy.da,jl[y]=xx.da; 59 } 60 } 61 } 62 /* 63 g++ 2.cpp -o 2 64 ./2 65 66 */
结构体lower_bound:
bool cmp(node x,node y){return (x.da==y.da)?x.pos<y.pos:x.da<y.da;}
int ll=lower_bound(a+1,a+n+1,l,cmp)-a;//a中查找l返回下标ll
原文：https://www.cnblogs.com/casun547/p/11295672.html