A.
找规律题。儿子的编号减去 小于它编号的最大的fibonacci数 即可得到它父亲的编号。
然后两个节点都暴力上跳就好了。预处理一下fibonacci数，每次二分查找即可。
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; int m; ll fib[65]; void pre() { fib[0]=fib[1]=1; for(int i=2;i<=59;i++) fib[i]=fib[i-1]+fib[i-2]; } int pos(ll x) { return lower_bound(fib+1,fib+60,x)-fib; } int main() { pre(); scanf("%d",&m); for(int i=1;i<=m;i++) { ll a,b; scanf("%lld%lld",&a,&b); while(a!=b) { if(a>b)a-=fib[pos(a)-1]; else b-=fib[pos(b)-1]; } cout<<a<<endl; } return 0; }
B.
专治学树锯结垢学傻的我，对每个颜色开一个vector存放出现位置，询问时在相应颜色的vector中二分查找大于等于l与大于r的两个位置，作差即可得到中间有几个位置。
至于修改，如果x与x+1位置的颜色相同就什么都不管，因为换了之后对vector内部没有影响。
如果颜色不同，直接在内部修改坐标信息，然后把颜色和在各自颜色中的相对位置互换。
#include<cstdio> #include<iostream> #include<cstring> #include<vector> #include<algorithm> using namespace std; const int N=300005; int n,m,a[N],rk[N]; vector<int> col[N]; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*f; } void work() { int op=read(); if(op==1) { int l=read(),r=read(),c=read(); int posl=lower_bound(col[c].begin(),col[c].end(),l)-col[c].begin(), posr=upper_bound(col[c].begin(),col[c].end(),r)-col[c].begin(); int res=posr-posl; printf("%d ",res); } else { int x=read(); if(a[x]==a[x+1])return ; col[a[x]][rk[x]]=x+1; col[a[x+1]][rk[x+1]]=x; swap(rk[x],rk[x+1]); swap(a[x],a[x+1]); } } int main() { n=read();m=read(); for(int i=1;i<=n;i++) { a[i]=read(); col[a[i]].push_back(i); rk[i]=col[a[i]].size()-1; } while(m--)work(); return 0; }
C.
对于$K=1$的情况，直接贪心从右往左扫，让断点尽量靠前。由于$max a[i]$为131072，所以两种颜色之和最大为$262144=512^2$。
那么我们只需要记录一下目前在组里出现过的数，判断是否要断就直接从512开始枚举j，看$j*j-a[i]$是否在组里就行了。切断后记得清空之前出现的数，循环到上个断点即可。
$K=2$呢？也是一个道理。像关押罪犯那道题一样利用扩展域并查集维护敌对关系，即一个集合和一个敌对集合。判断到冲突时，看两个数在不在同一集合。在的话被迫断开，不在就维护敌对关系，即将对方的敌对域与自己的己域合并。
但是对于$2*a[i]=x^2$的情况，我们需要进行特判。如果这样的$a[i]$目前只出现了两次，且组里没有它的其它敌对元素，就可以先不设置断点。否则立刻断开清空。
#include<cstdio> #include<iostream> #include<cstring> #include<vector> using namespace std; const int N=132000; int n,K,a[N],app[N<<1]; int st[N]; void work1() { for(int i=n;i>=1;i--) { bool div=0; for(int j=512;j>=1&&j*j>a[i];j--) if(app[j*j-a[i]]) { div=1;break; } if(div) { st[++st[0]]=i; for(int j=i+1;j<=(st[0]==1?n:st[st[0]-1]);j++) app[a[j]]=0; //continue; } app[a[i]]++; } if(!st[0]) { puts("1"); printf(" "); return ; } printf("%d ",st[0]+1); while(st[0]) printf("%d ",st[st[0]]),st[0]--; } int fa[N],rev[N]; int findf(int x) { if(fa[x]==x)return x; return fa[x]=findf(fa[x]); } void work2() { int top=1; for(int i=1;i<=N-20;i++) fa[i]=i; st[0]=n; for(int i=n;i>=1;i--) { for(int j=512;j>=2&&j*j>a[i];j--) { int ene=j*j-a[i];//puts("YOUSA"); if(app[j*j-a[i]]==top) { if(a[i]==ene) { if(rev[a[i]]) { for(int k=i;k<=st[top-1];k++) fa[a[k]]=a[k],rev[a[k]]=0; st[top++]=i; break; } else rev[a[i]]=ene; } else { if(findf(a[i])==findf(ene)||rev[ene]==ene) { for(int k=i;k<=st[top-1];k++) fa[a[k]]=a[k],rev[a[k]]=0; st[top++]=i; break; } if(rev[a[i]]) { int fx=findf(rev[a[i]]),fy=findf(ene); fa[fx]=fy; } else rev[a[i]]=ene; if(rev[ene]) { int fx=findf(a[i]),fy=findf(rev[ene]); fa[fx]=fy; } else rev[ene]=a[i]; } } } app[a[i]]=top; } printf("%d ",top); for(int i=top-1;i>=1;i--) printf("%d ",st[i]); printf(" "); return ; } int main() { scanf("%d%d",&n,&K); for(int i=1;i<=n;i++) scanf("%d",&a[i]); if(K==1)work1(); else work2(); return 0; }