A.
找规律题。儿子的编号减去 小于它编号的最大的fibonacci数 即可得到它父亲的编号。
然后两个节点都暴力上跳就好了。预处理一下fibonacci数，每次二分查找即可。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int m;
ll fib[];
void pre()
{
fib[]=fib[]=;
for(int i=;i<=;i++)
fib[i]=fib[i-]+fib[i-];
}
int pos(ll x)
{
return lower_bound(fib+,fib+,x)-fib;
}
int main()
{
pre();
scanf("%d",&m);
for(int i=;i<=m;i++)
{
ll a,b;
scanf("%lld%lld",&a,&b);
while(a!=b)
{
if(a>b)a-=fib[pos(a)-];
else b-=fib[pos(b)-];
}
cout<<a<<endl;
}
return ;
}
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=;
int n,m,a[N],rk[N];
vector<int> col[N];
int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return x*f;
}
void work()
{
int op=read();
if(op==)
{
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\n",res);
}
else
{
int x=read();
if(a[x]==a[x+])return ;
col[a[x]][rk[x]]=x+;
col[a[x+]][rk[x+]]=x;
swap(rk[x],rk[x+]);
swap(a[x],a[x+]);
}
}
int main()
{
n=read();m=read();
for(int i=;i<=n;i++)
{
a[i]=read();
col[a[i]].push_back(i);
rk[i]=col[a[i]].size()-;
}
while(m--)work();
return ;
}
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=;
int n,K,a[N],app[N<<];
int st[N];
void work1()
{
for(int i=n;i>=;i--)
{
bool div=;
for(int j=;j>=&&j*j>a[i];j--)
if(app[j*j-a[i]])
{
div=;break;
}
if(div)
{
st[++st[]]=i;
for(int j=i+;j<=(st[]==?n:st[st[]-]);j++)
app[a[j]]=;
//continue;
}
app[a[i]]++;
}
if(!st[])
{
puts("");
printf("\n");
return ;
}
printf("%d\n",st[]+);
while(st[])
printf("%d ",st[st[]]),st[]--;
}
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=;
for(int i=;i<=N-;i++)
fa[i]=i;
st[]=n;
for(int i=n;i>=;i--)
{
for(int j=;j>=&&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-];k++)
fa[a[k]]=a[k],rev[a[k]]=;
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-];k++)
fa[a[k]]=a[k],rev[a[k]]=;
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\n",top);
for(int i=top-;i>=;i--)
printf("%d ",st[i]);
printf("\n");
return ;
}
int main()
{
scanf("%d%d",&n,&K);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
if(K==)work1();
else work2();
return ;
}