考试时不会做，所以借着特殊条件骗了60分，其实有些侥幸了吧qaq，不过总比以前想不出正解就无计可施强多了……
其实正解也是利用了特殊条件来优化，所以特殊条件有时候其实挺有提示性的
首先找一下规律，发现编号为\(2,3,4,5,6,7,8,9\cdots\)的兔子，祖先为\(1,1,1,2,1,2,3,1\cdots\)，这里的规律是：一个兔子的祖先是他的编号减去小于他编号的最大菲波那契数
范围是\(1e12\)，这个范围里的菲波那契数只有60个，所以打出表来，再二分查一下即可，写\(lower_bound\)似乎会被卡，所以以后多手写二分吧qaq
再有就是利用题里的特殊情况得到两个优化：（其实不加也是能过的）
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define N 75
ll fib[N],cnt=0;
ll m,a,b;
ll find(ll x)
{
ll l=1,r=cnt,m;
while(l<r)
{
m=(l+r)>>1;
if(fib[m]>=x)r=m;
else l=m+1;
}
return l;
}
ll tmp;
int main()
{
ll aa=0,bb=1,cc=0;
while(cc<1000000000000)
{
cc=aa+bb;
fib[++cnt]=cc;
aa=bb,bb=cc;
}
scanf("%lld",&m);
ll flag=0;
for(int i=1;i<=m;i++)
{
flag=0;
scanf("%lld%lld",&a,&b);
while(a!=b)
{
if(abs(a-b)<=1)
{
if(a==b)printf("%lld\n",a);
else printf("1\n");
flag=1;
break;
}
if(a<b)swap(a,b);
a=a-fib[find(a)-1];
}
if(!flag)printf("%lld\n",a);
}
return 0;
}
##T2 数颜色
###考场
联想到了上次的string，于是写起了线段树，然后发现复杂度不对，只有30分……
###正解
使用$vector$
查询：给每个颜色开一个$vector$，将颜色出现的位置插入其中，每次查询某个颜色就在这个颜色的$vector$里二分找出$l$的$lower_bound$和$r$的$upper_bound-1$，则答案为$r-l+1$
（$Ps:$其实插入的位置是有序的，所以可以放心二分）
修改：先找到两个位置在$vector$里的位置，然后直接修改，因为交换前后两个，所以前面++，后面--就行了
似乎是第一次碰到这样的题，之前都没怎么碰过$vector,map$之类的东西……似乎用这些有时会很方便，以后要多看看qaq
code：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define N 300005
ll n,m;
ll a[N];
vector<ll> g[N];
ll t,l,r,c,x;
int main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<=n;i++)g[a[i]].push_back(i);
for(int i=1;i<=m;i++)
{
scanf("%lld",&t);
if(t==1)
{
scanf("%lld%lld%lld",&l,&r,&c);
ll t1=lower_bound(g[c].begin(),g[c].end(),l)-g[c].begin();
ll t2=upper_bound(g[c].begin(),g[c].end(),r)-g[c].begin()-1;
printf("%lld\n",t2-t1+1);
}
else if(t==2)
{
scanf("%lld",&x);
if(a[x]!=a[x+1])
{
ll t1=lower_bound(g[a[x]].begin(),g[a[x]].end(),x)-g[a[x]].begin();
ll t2=lower_bound(g[a[x+1]].begin(),g[a[x+1]].end(),x+1)-g[a[x+1]].begin();
g[a[x]][t1]++;
g[a[x+1]][t2]--;
swap(a[x],a[x+1]);
}
}
}
return 0;
}
另外，这道题似乎还有主席树和一堆高级数据结构的方法，不过这次似乎被卡了……一方面有时间得学学这些东西，另一方面以后也不要过度依赖高级数据结构啊qaq
暴力，拿了40分……
其实也考虑过线段树？但是不会写……（后来学长说这题带修改可以用线段树）
感觉这题写暴力不应该，毕竟这个柿子窝完全可以推出来啊qaq
以后一定要勇于推柿子啊qaq
所求答案：
这两个柿子中，\(\sum_{i=1}^{n} m(i-1)\cdot R_i\)和\(\sum_{i=1}^{n} R_i\)这两部分都只与\(i\)有关，我们可以\(O(n)\)求出
对于\(S_i\)和\(R_i\)，因为乘法的先后对结果没有影响，所以直接离线乘起来
然后再对于每个\(j\)更新答案，注意随时取模（本题数据炸\(long\ long\)非常之容易，如果没取好会炸成44分，可只比暴力高4分啊qaq
code：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define N 1000005
#define mod 1000000007
ll R[N],S[N];
ll n,m,k;
char s[3];
ll x,y;
ll sum1=0;
ll sum2=0;
ll ans=0;
int main()
{
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1;i<=n;i++)R[i]=1;
for(int j=1;j<=m;j++)S[j]=1;
for(int i=1;i<=k;i++)
{
scanf("%s%lld%lld",s,&x,&y);
if(s[0]==‘R‘)R[x]=R[x]*y%mod;
else if(s[0]==‘S‘)S[x]=S[x]*y%mod;
}
for(int i=1;i<=n;i++)sum1=(sum1+m*(i-1)%mod*R[i]%mod)%mod;//cout<<sum1<<endl;
for(int i=1;i<=n;i++)sum2=(sum2+R[i])%mod;//cout<<‘ ‘<<sum2<<endl;
for(int j=1;j<=m;j++)ans=(ans+sum1*S[j]%mod)%mod;//cout<<" "<<ans<<endl;
for(int j=1;j<=m;j++)ans=(ans+j*S[j]%mod*sum2%mod)%mod;//cout<<" "<<ans<<endl;
printf("%lld",ans);
return 0;
}
可以发现询问的区间要变成优美区间必须让他最大最小值中间的数补齐，所以可以开一个线段树维护原数列的最大最小值
然后可以再开一个数组，记录\(i\)在原数列中的下标，由刚刚求到的最值可以得到一个区间，这个区间的最大最小值所代表的原数组中的区间就是补齐了原来缺的数，可以再开一个线段树来维护这个最值
但是，由于可能有其他的数加入，这个时候得到的区间可能并不是优美的，所以把这个区间再拿去重复处理，直到这段区间\(max-min=\)区间长度
这样可以拿到78分，由于最后反复扩展，这种方法在这时会效率很低（或许是平方的？
（有学长查区间最值用的是\(ST\)表，似乎能多得4分
78分code：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define N 100005
#define ls rt<<1
#define rs rt<<1|1
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
ll n,m,x,y,ttl,ttr;
ll a[N],b[N];
struct node
{
ll mx,mi;
}tr[2][N<<2];
void up(ll id,ll rt)
{
tr[id][rt].mx=max(tr[id][ls].mx,tr[id][rs].mx);
tr[id][rt].mi=min(tr[id][ls].mi,tr[id][rs].mi);
}
void build1(ll rt,ll l,ll r)
{
if(l==r)
{
tr[0][rt].mi=tr[0][rt].mx=a[l];
//cout<<tr[0][rt].mi<<‘ ‘;
return;
}
ll m=(l+r)>>1;
build1(lson);
build1(rson);
up(0,rt);
}
void build2(ll rt,ll l,ll r)
{
if(l==r)
{
tr[1][rt].mi=tr[1][rt].mx=b[l];
//cout<<tr[1][rt].mx<<‘ ‘;
return;
}
ll m=(l+r)>>1;
build2(lson);
build2(rson);
up(1,rt);
}
ll querymax(ll id,ll rt,ll l,ll r,ll nl,ll nr)
{
if(nl<=l&&r<=nr)
{
return tr[id][rt].mx;
}
ll m=(l+r)>>1;
ll res=0;
if(m>=nl)res=max(res,querymax(id,lson,nl,nr));
if(m<nr)res=max(res,querymax(id,rson,nl,nr));
return res;
}
ll querymin(ll id,ll rt,ll l,ll r,ll nl,ll nr)
{
if(nl<=l&&r<=nr)
{
return tr[id][rt].mi;
}
ll m=(l+r)>>1;
ll res=N;
if(m>=nl)res=min(res,querymin(id,lson,nl,nr));
if(m<nr)res=min(res,querymin(id,rson,nl,nr));
return res;
}
int main()
{
//freopen("owo.in","r",stdin);
scanf("%lld",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<=n;i++)b[a[i]]=i;
build1(1,1,n);//cout<<endl;
build2(1,1,n);//cout<<endl;
scanf("%lld",&m);
for(int i=1;i<=m;i++)
{
scanf("%lld%lld",&ttl,&ttr);
do{
x=querymin(0,1,1,n,ttl,ttr);
y=querymax(0,1,1,n,ttl,ttr);
ttl=querymin(1,1,1,n,x,y);
ttr=querymax(1,1,1,n,x,y);
}while(ttr-ttl+1!=querymax(0,1,1,n,ttl,ttr)-querymin(0,1,1,n,ttl,ttr)+1);
printf("%lld %lld\n",ttl,ttr);
}
return 0;
}
似乎有很多种，在补了在补了qwq
原文：https://www.cnblogs.com/zzzuozhe-gjy/p/13428175.html