T1
本次考试最水的一道题，然而我sb，前一个小时，找了一大堆跟题目无关的性质，干脆打了个20pts的表，然后就走了，最后几分钟才看出来，匆匆码出来，结果段错误，然后考试就结束了。
好吧，段错误是UB，返回值的原因，%%%TLEer，加个return就好了。
就是找规律，\(fa_{now}=now-f_{i}\) ，其中 \(f_{i} < now\le f_{i+1}\) 即第一个比 \(now\) 小的斐波那契数，然后就没啥了，记得开long long。
Code
#include<cstdio>
#include<algorithm>
#define re register
#define int long long
namespace OMA
{
int m;
int f[65]={0,1,1};
inline int read()
{
int s=0,w=1; char ch=getchar();
while(ch<‘0‘||ch>‘9‘){ if(ch==‘-‘)w=-1; ch=getchar(); }
while(ch>=‘0‘&&ch<=‘9‘){ s=s*10+ch-‘0‘; ch=getchar(); }
return s*w;
}
int LCA(int a,int b)
{
if(a==1||b==1)
{ return 1; }
if(a==b)
{ return a; }
int temp1 = std::lower_bound(f+1,f+61,a)-f-1;
int temp2 = std::lower_bound(f+1,f+61,b)-f-1;
while(a-f[temp1]>=b)
{ a -= f[temp1],temp1 = std::lower_bound(f+1,f+temp1,a)-f-1; }
while(b-f[temp2]>=a)
{ b -= f[temp2],temp2 = std::lower_bound(f+1,f+temp2,b)-f-1; }
if(a==1||b==1)
{ return 1; }
if(a==b)
{ return a; }
return LCA(a-f[temp1],b-f[temp2]);
}
signed main()
{
f[0]=0;
m = read();
for(re int i=3; i<=60; i++)
{ f[i] = f[i-1]+f[i-2]; }
for(re int i=1; i<=m; i++)
{ int a=read(),b = read(); printf("%lld\n",LCA(a,b)); }
return 0;
}
}
signed main()
{ return OMA::main(); }
T2
暴力拿了30pts，后来时限开大，拿了60pts。
正解很多，这里是二分。
首先按照颜色和位置排序，然后考虑题目中的两个操作。
第一个询问操作，只需要对排序后的数组二分查找，下标差即是答案。
第二个修改操作，因为修改并不会改变同种颜色的相对顺序，所以只需要找到位置并进行修改就好了。其实也是挺水的
线段树做法
Code
#include<cstdio>
#include<algorithm>
#define MAX 300001
#define re register
namespace OMA
{
int n,m;
int a[MAX];
struct node
{
int c;
int pos;
friend bool operator <(const node &x,const node &y)
{ return (x.c!=y.c)?x.c<y.c:x.pos<y.pos; }
}col[MAX];
inline int read()
{
int s=0,w=1; char ch=getchar();
while(ch<‘0‘||ch>‘9‘){ if(ch==‘-‘)w=-1; ch=getchar(); }
while(ch>=‘0‘&&ch<=‘9‘){ s=s*10+ch-‘0‘; ch=getchar(); }
return s*w;
}
inline void swap(int &a,int &b)
{ int t=a; a=b; b=t; }
signed main()
{
n = read(),m = read();
for(re int i=1; i<=n; i++)
{ a[i] = col[col[i].pos = i].c = read(); }
std::sort(col+1,col+1+n);
for(re int i=1; i<=m; i++)
{
int opt = read();
if(opt==1)
{
int l = read(),r = read(),c = read();
int L = std::lower_bound(col+1,col+1+n,node{c,l})-col;
int R = std::upper_bound(col+1,col+1+n,node{c,r})-col-1;
printf("%d\n",R-L+1);
}
if(opt==2)
{
int x = read();
if(a[x]==a[x+1])
{ continue; }
col[std::lower_bound(col+1,col+1+n,node{a[x],x})-col].pos = x+1;
col[std::lower_bound(col+1,col+1+n,node{a[x+1],x+1})-col].pos = x;
swap(a[x],a[x+1]);
}
}
return 0;
}
}
signed main()
{ return OMA::main(); }
T3
Code