最近实在是太浪了
不一会还是发现了很多性质的，但是我考虑的越多，脑子越不知道往哪想，一直没有找到切入点（把自己搞懵比）。然后打了个模拟向上标记只有50分，开long long只有60分。
实际上从题意上就能找到突破口，既然要找lca，那么我们只要找到儿子与父亲的节点编号关系，用最裸的向上标记，就可以不断的从儿子向上翻，最多60层，可以不处理倍增数组（实际上是空间开不起）。
然后考虑这个父子关系，其实我在暴力建图的时候tmd也发现了，但我并没有再想用它做点什么。第i月出生的第j个兔子$num=fib[i-1]+j$，同时$1 \leq j \leq fib[i-2]$，非常好的一点在于j就是它的父亲，移项得j=num-fib[i-1]，然后我们就有了从儿子找到父亲的方法。$\Theta (60^2m)$ 有点极限。
只要找到第一个小于num的fib，满足单调性，直接二分。$\Theta (60log60 m)$
然后我们就省掉了建图的空间与时间，愉快地拿到了100分的好成绩（手舞足蹈.gif）。
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 #define ll long long 5 #define reg register 6 #define F(i,a,b) for(register int (i)=(a);(i)<=(b);++(i)) 7 using namespace std; 8 ll read(); 9 int m; 10 ll fib[66]; 11 inline ll ef(ll x) 12 { 13 int l=1,r=62,mid; 14 while(l<r) 15 { 16 mid=(l+r)>>1; 17 if(fib[mid]>=x) r=mid; 18 else l=mid+1; 19 } 20 return fib[l-1]; 21 } 22 int main() 23 { 24 // freopen("data.in","r",stdin); 25 m=read(); 26 ll x,y; 27 fib[0]=fib[1]=1; 28 F(i,2,62) fib[i]=fib[i-1]+fib[i-2]; 29 F(i,1,m) 30 { 31 x=read(); y=read(); 32 while(x!=y) 33 { 34 if(x>y) x^=y^=x^=y; 35 y-=ef(y); 36 } 37 printf("%lld\n",x); 38 } 39 return 0; 40 } 41 ll read() 42 { 43 ll x=0; 44 char tc=getchar(); 45 while(tc<‘0‘||tc>‘9‘) tc=getchar(); 46 while(tc>=‘0‘&&tc<=‘9‘) x=x*10+tc-48,tc=getchar(); 47 return x; 48 }
少开long long居然会TLE唔
我可能是高级数据结构学傻了。。。
考试的时候一看，这不莫队吗？还是带修的？可我不会啊！
然后还是自己YY了一个以每个修改为界限两边sort询问的TLE莫队，当时打完就觉得这板比T飞了，最坏情况是询问-修改-询问-修改-询问-修改-询问-修改然后死了，只有30分。
实际上能得70的算法：树套树（树状数组套主席树）(lnc)，真正的带修莫队（wd），分块（whs） 再加上两个特殊性质 90分到（别人）手
100%算法：
算法一：vector 聪明人算法（sdfz_dky）
查询：对每个颜色开vector，由于元素的个数一定，不会爆内存。col[i][k]，元素是排名第(k+1)个i颜色的兔子所在原序列的位置，维护col[i]有序，然后就可以二分做差得到答案了。
修改：如果不是相邻位置的颜色交换，算法一就失效了。因为是相邻位置，交换后它们相对于其他位置的相对大小都是不变的。结合算法一，就是我只要在col[a[x]]和col[a[x+1]]中二分找到x x+1位置所对应的col[]下标，然后交换他们的位置，发现没有改变col[]单调性，从而省去了nlogn的内部复杂度，完成了交换。
然后就拿到了75分的好成绩？
少了特判：如果a[x]==a[x+1]那么就不能修改，会破坏单调性。
算法二：主席树（pa）
发现每次修改只会改变两棵主席树（快忘了怎么写了，复习！）。然后就暴改这两棵树，常规查询即可。
1 #include<cstdio> 2 #include<vector> 3 #include<algorithm> 4 #define reg register 5 #define F(i,a,b) for(register int (i)=(a);(i)<=(b);++(i)) 6 using namespace std; 7 int read(); 8 const int N=300005; 9 int n,m; 10 int a[N]; 11 vector<int> col[N]; 12 int main() 13 { 14 n=read(); m=read(); 15 F(i,1,n) 16 { 17 a[i]=read(); 18 col[a[i]].push_back(i); 19 } 20 int opt,l,r,c; 21 F(i,1,m) 22 { 23 opt=read(); 24 if(opt==1) 25 { 26 l=read(); 27 r=read(); 28 c=read(); 29 int sum1=upper_bound(col[c].begin(),col[c].end(),l-1)-col[c].begin()-1; 30 int sum2=upper_bound(col[c].begin(),col[c].end(),r)-col[c].begin()-1; 31 printf("%d\n",sum2-sum1); 32 } 33 else 34 { 35 c=read(); 36 if(a[c]==a[c+1]) continue; 37 int x1=lower_bound(col[a[c]].begin(),col[a[c]].end(),c)-col[a[c]].begin(); 38 int x2=lower_bound(col[a[c+1]].begin(),col[a[c+1]].end(),c+1)-col[a[c+1]].begin(); 39 col[a[c]][x1]=c+1; 40 col[a[c+1]][x2]=c; 41 swap(a[c],a[c+1]); 42 } 43 } 44 return 0; 45 } 46 int read() 47 { 48 int x=0; 49 char tc=getchar(); 50 while(tc<‘0‘||tc>‘9‘) tc=getchar(); 51 while(tc>=‘0‘&&tc<=‘9‘) x=x*10+tc-48,tc=getchar(); 52 return x; 53 }
考试的时候想到了k==1的 $ \Theta (n^2) $ 贪心。就是倒序扫描直到出现矛盾开组。
常见的疑惑是 倒序更新最先保证的后面的字典序最小，但前面的答案对答案影响最大，后面的优先更新可能会导致前面不优。
实际上贪心是正确的：后面靠前，只会让前面原本不靠前的左端点到右端点之间的矛盾减少，所以左端点一定不会向后。换言之，答案不会更坏。
然后还是会T掉3个大点。
判断式：$ a+b ? x^2 $ 原来我们枚举b，验证x，但是b的数量多。我们可以转而枚举x，这样我们最多只有512的枚举量，然后用x^2-a看b是否出现过
未完。。。。
原文：https://www.cnblogs.com/hzoi-yzh/p/11297126.html
