友情提示一下，难度递增
by 一UNowen一 @ 2016-05-15 10:25:07
蒟蒻表示超难的
by 哒哒哒小A @ 2016-05-15 21:33:35
先恭喜AK的fjzzq2002同学，然后放题解。
T1：
啥都不说了，直接把区间的数拎出来排个序弄一下就行了，O(Qnlog(n))CLJ关于这个有论文可以做到O((n+q)\*n^0.5)的复杂度
T2:
首先可以发现f(f(g(i)))=g(f(f(i))，相对应的无论f(i)映射几次都可以满足F(g(i))=g(F(i))，然后我们就可以把对于一个f(i)，有最小的k满足f^k(i)=i的形式（我们姑且把它叫做i在一个长度为k的环里），那么最终的一定要满足g(i)所在的环的大小是一个f(i)所在环的大小的因子，那么我们把所有不同长度的环的最优解找出来贪心填一下就好了。因为不同环的长度有O(n^0.5)个，所以更新的规模是O(n)的，最后填进去和一开始的找环都是O(n)的，总复杂度O(n)（辣鸡出题人出原题）
T3：
先把问题变成f(i)在1-k之间的i有几个，考虑1-9中只有2、3、5、7，4种质因子，而且18位数字显然最多有18\*3个2，18\*2个3,18个5,18个7，所以我们可以暴力枚举这个东西，时间复杂度O(18^4\*6)，然后枚举这一位是1-9哪一个做一下背包，用记忆化搜索实现，注意当i位数和k位数相等时要按位做过去，总复杂度O(18^5\*6\*9)，实际上远远不到
by 一UNowen一 @ 2016-05-15 21:40:21
因为昨天有点意识模糊加上要回寝室了\_(:зゝ∠)\_改一下一些错误，T1CLJ的论文可做到O((n+q)\*n^(2/3))
T1标程
```c++
#include<cstdio>
#include<algorithm>
using namespace std;
int a[1005],tmp[1005];
int n,m,cnt;
inline int read(){
int ret=0;
char c=getchar();
while((c>'9')||(c<'0'))c=getchar();
while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ret;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=m;i++){
int flag=read(),x=read(),y=read();
if(flag==0){
cnt=0;
for(int j=x;j<=y;j++)tmp[++cnt]=a[j];
sort(tmp+1,tmp+1+cnt);
int ans=tmp[1],s=1,S=1;
for(int j=2;j<=cnt;j++)if(tmp[j]==tmp[j-1]){
s++;
if(s>S){S=s;ans=tmp[j];}
}else s=1;
printf("%d\n",ans);
}else a[x]=y;
}
}
```
T2标程
```c++
#include<cstdio>
#include<algorithm>
using namespace std;
int n,cnt;
int a[1000005],re[1000005],h[1000005];
struct ele{
int s,num;
}e[1005];
bool vis[1000005];
int b[1000005];
inline int read(){
int ret=0;
char c=getchar();
while((c>'9')||(c<'0'))c=getchar();
while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ret;
}
inline int find(int k){
int l=0,r=cnt+1;
while(r-l>1){
int mid=(l+r)>>1;
if(e[mid].s==k)return e[mid].num;
if(e[mid].s<k)l=mid;
else r=mid;
}
}
int main(){
n=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)if(!vis[i]){
vis[i]=true;
int s=1,k=a[i];
while(!vis[k]){
vis[k]=true;
s++;k=a[k];
}
h[i]=s;
if(re[s]==0)re[s]=i;
}
for(int i=1;i<=n;i++)if(re[i]){
cnt++;
e[cnt].s=i;
e[cnt].num=re[i];
}
for(int i=2;i<=cnt;i++)
for(int j=1;j<i;j++)if(e[i].s%e[j].s==0)e[i].num=min(e[i].num,e[j].num);
for(int i=1;i<=n;i++)if(!b[i]){
int k=find(h[i]),j=i;
while(!b[j]){
b[j]=k;
k=a[k];
j=a[j];
}
}
for(int i=1;i<=n;i++)printf("%d ",b[i]);
}
```
T3标程
```c++
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define ll long long
int f[20][60][40][20][20];
bool p[20][60][40][20][20];
int a[20],b[20],n,c[10][5];
int W(ll k){int n=0;while(k)++n,k/=10;return n;}
ll dfs(int z,int k1,int k2,int k3,int k4){
if(k1/3+k2/2+k3+k4>z)return 0;
if(z==0)return k1==0&&k2==0&&k3==0&&k4==0;
if(p[z][k1][k2][k3][k4])return f[z][k1][k2][k3][k4];
p[z][k1][k2][k3][k4]=1,f[z][k1][k2][k3][k4]=0;
for(int i=1;i<=9;++i)if(k1>=c[i][1]&&k2>=c[i][2]&&k3>=c[i][3]&&k4>=c[i][4])f[z][k1][k2][k3][k4]+=dfs(z-1,k1-c[i][1],k2-c[i][2],k3-c[i][3],k4-c[i][4]);
return f[z][k1][k2][k3][k4];
}
ll find(int z,int k1,int k2,int k3,int k4){
ll ans=0;
if(z==0)return k1==0&&k2==0&&k3==0&&k4==0;
for(int i=1;i<b[z];++i)
if(k1>=c[i][1]&&k2>=c[i][2]&&k3>=c[i][3]&&k4>=c[i][4])ans+=dfs(z-1,k1-c[i][1],k2-c[i][2],k3-c[i][3],k4-c[i][4]);
int i=b[z];
if(i)if(k1>=c[i][1]&&k2>=c[i][2]&&k3>=c[i][3]&&k4>=c[i][4])ans+=find(z-1,k1-c[i][1],k2-c[i][2],k3-c[i][3],k4-c[i][4]);
return ans;
}
ll two[60],three[40],five[20],seven[20];
ll calc(ll k){
if(k==0)return 0;
int n=W(k),n2=3*n,n3=2*n;
ll ans=0;
for(int i2=0;i2<=n2;++i2)
for(int i3=0;i3<=n3;++i3)
for(int i5=0;i5<=n;++i5)
for(int i7=0;i7<=n;++i7){
ll t=k;t/=two[i2],t/=three[i3],t/=five[i5],t/=seven[i7];
int z=W(t);if(!z)continue;
int o=0;ll kk=t;while(kk)b[++o]=kk%10,kk/=10;
ll tot=find(z,i2,i3,i5,i7);
for(int i=1;i<z;i++)tot+=dfs(i,i2,i3,i5,i7);
ans+=tot;
}
return ans;
}
int main(){
for(int i=1;i<=9;++i){
int t=i;
while(t%2==0)++c[i][1],t>>=1;
while(t%3==0)++c[i][2],t/=3;
while(t%5==0)++c[i][3],t/=5;
while(t%7==0)++c[i][4],t/=7;
}
ll l,r;
cin>>l>>r;if(l>r)swap(l,r);
int o=W(r);
two[0]=three[0]=five[0]=seven[0]=1;
for(int i=1;i<=3*o;++i)two[i]=two[i-1]<<1;
for(int i=1;i<=2*o;++i)three[i]=three[i-1]*3;
for(int i=1;i<=o;++i)five[i]=five[i-1]*5;
for(int i=1;i<=o;++i)seven[i]=seven[i-1]*7;
cout<<calc(r)-calc(l-1)<<endl;
}
```
by 一UNowen一 @ 2016-05-16 12:12:17
日萎掉了，都怪wyx口胡我
T1标程
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
int a[1005],tmp[1005];
int n,m,cnt;
inline int read(){
int ret=0;
char c=getchar();
while((c>'9')||(c<'0'))c=getchar();
while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ret;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=m;i++){
int flag=read(),x=read(),y=read();
if(flag==0){
cnt=0;
for(int j=x;j<=y;j++)tmp[++cnt]=a[j];
sort(tmp+1,tmp+1+cnt);
int ans=tmp[1],s=1,S=1;
for(int j=2;j<=cnt;j++)if(tmp[j]==tmp[j-1]){
s++;
if(s>S){S=s;ans=tmp[j];}
}else s=1;
printf("%d\n",ans);
}else a[x]=y;
}
}
```
by 一UNowen一 @ 2016-05-16 12:15:09
T2
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
int n,cnt;
int a[1000005],re[1000005],h[1000005];
struct ele{
int s,num;
}e[1005];
bool vis[1000005];
int b[1000005];
inline int read(){
int ret=0;
char c=getchar();
while((c>'9')||(c<'0'))c=getchar();
while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ret;
}
inline int find(int k){
int l=0,r=cnt+1;
while(r-l>1){
int mid=(l+r)>>1;
if(e[mid].s==k)return e[mid].num;
if(e[mid].s<k)l=mid;
else r=mid;
}
}
int main(){
n=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)if(!vis[i]){
vis[i]=true;
int s=1,k=a[i];
while(!vis[k]){
vis[k]=true;
s++;k=a[k];
}
h[i]=s;
if(re[s]==0)re[s]=i;
}
for(int i=1;i<=n;i++)if(re[i]){
cnt++;
e[cnt].s=i;
e[cnt].num=re[i];
}
for(int i=2;i<=cnt;i++)
for(int j=1;j<i;j++)if(e[i].s%e[j].s==0)e[i].num=min(e[i].num,e[j].num);
for(int i=1;i<=n;i++)if(!b[i]){
int k=find(h[i]),j=i;
while(!b[j]){
b[j]=k;
k=a[k];
j=a[j];
}
}
for(int i=1;i<=n;i++)printf("%d ",b[i]);
}
```
by 一UNowen一 @ 2016-05-16 12:21:16
明明把Tab全部换成空格了，但是，为什么会这样呢
T3
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define ll long long
int f[20][60][40][20][20];
bool p[20][60][40][20][20];
int a[20],b[20],n,c[10][5];
int W(ll k){int n=0;while(k)++n,k/=10;return n;}
ll dfs(int z,int k1,int k2,int k3,int k4){
if(k1/3+k2/2+k3+k4>z)return 0;
if(z==0)return k1==0&&k2==0&&k3==0&&k4==0;
if(p[z][k1][k2][k3][k4])return f[z][k1][k2][k3][k4];
p[z][k1][k2][k3][k4]=1,f[z][k1][k2][k3][k4]=0;
for(int i=1;i<=9;++i)if(k1>=c[i][1]&&k2>=c[i][2]&&k3>=c[i][3]&&k4>=c[i][4])f[z][k1][k2][k3][k4]+=dfs(z-1,k1-c[i][1],k2-c[i][2],k3-c[i][3],k4-c[i][4]);
return f[z][k1][k2][k3][k4];
}
ll find(int z,int k1,int k2,int k3,int k4){
ll ans=0;
if(z==0)return k1==0&&k2==0&&k3==0&&k4==0;
for(int i=1;i<b[z];++i)
if(k1>=c[i][1]&&k2>=c[i][2]&&k3>=c[i][3]&&k4>=c[i][4])ans+=dfs(z-1,k1-c[i][1],k2-c[i][2],k3-c[i][3],k4-c[i][4]);
int i=b[z];
if(i)if(k1>=c[i][1]&&k2>=c[i][2]&&k3>=c[i][3]&&k4>=c[i][4])ans+=find(z-1,k1-c[i][1],k2-c[i][2],k3-c[i][3],k4-c[i][4]);
return ans;
}
ll two[60],three[40],five[20],seven[20];
ll calc(ll k){
if(k==0)return 0;
int n=W(k),n2=3*n,n3=2*n;
ll ans=0;
for(int i2=0;i2<=n2;++i2)
for(int i3=0;i3<=n3;++i3)
for(int i5=0;i5<=n;++i5)
for(int i7=0;i7<=n;++i7){
ll t=k;t/=two[i2],t/=three[i3],t/=five[i5],t/=seven[i7];
int z=W(t);if(!z)continue;
int o=0;ll kk=t;while(kk)b[++o]=kk%10,kk/=10;
ll tot=find(z,i2,i3,i5,i7);
for(int i=1;i<z;i++)tot+=dfs(i,i2,i3,i5,i7);
ans+=tot;
}
return ans;
}
int main(){
for(int i=1;i<=9;++i){
int t=i;
while(t%2==0)++c[i][1],t>>=1;
while(t%3==0)++c[i][2],t/=3;
while(t%5==0)++c[i][3],t/=5;
while(t%7==0)++c[i][4],t/=7;
}
ll l,r;
cin>>l>>r;if(l>r)swap(l,r);
int o=W(r);
two[0]=three[0]=five[0]=seven[0]=1;
for(int i=1;i<=3*o;++i)two[i]=two[i-1]<<1;
for(int i=1;i<=2*o;++i)three[i]=three[i-1]*3;
for(int i=1;i<=o;++i)five[i]=five[i-1]*5;
for(int i=1;i<=o;++i)seven[i]=seven[i-1]*7;
cout<<calc(r)-calc(l-1)<<endl;
}
```
by 一UNowen一 @ 2016-05-16 12:22:53
惨
by lion0514 @ 2021-05-02 08:51:45