T1 密码
当时想到解法了，却依然认为自己不会做，我真是个人才。
结论：对于 $\forall i \in [1,n)$ ，满足密码不是 $a_i$ 的因数，且密码是 $a_k$ 的因数，设满足条件的最小值为 $g$ 则答案为 $\frac{n}{g}$。
一种最好想的做法：枚举 $\gcd(a_k,n)$ 的因数作为 $g$，并枚举 $i \in [1,n)$，判断是否整除 $a_i$，如果是就不能作为答案。
以上是 60pts 做法，复杂度 $O(f(\gcd(a_k,n)k)$，其中 $f(x)$ 表示 $x$ 的因数个数。
贴个代码(60pts)：
#define LL long long
LL n,k,a[250005];
LL gcd(LL x,LL y){return !y?x:gcd(y,x%y);}
bool check(LL x){
for(int i=1;i<k;i++)
if(a[i]%x==0)
return 0;
return 1;
}
int main(){
LL g=gcd(n,a[k]),i=1;
for(;i*i<=g;i++) if(g%i==0&&check(i)) return printf("%lld\n",n/i),0;
for(;i>=1;i--) if(g%i==0&&check(g/i)) return printf("%lld\n",n/(g/i)),0;
}
接下来考虑进行优化。
已知对于 $a_i$，只有小于 $\gcd(a_k,n)$ 的因数会影响答案判断。
所以我们可以枚举 $\gcd(a_i,a_k,n)$ 中的质因数，然后搜索枚举 $m_i$ 的因数（详见代码），记录下哪些答案是不行的。
中途碰到标记过的数时就直接 return，这样复杂度可以保证在 $O(k \log V+\sqrt{\gcd(a_k,n)}+f(\gcd(a_k,n)))$，就可以过了。
贴下代码(100pts)：
#define LL long long
map<LL,bool> mp;
LL n,k,cnt,pr[15],a[250005];
LL gcd(LL x,LL y){return !y?x:gcd(y,x%y);}
void dfs(LL x){
if(mp.count(x)) return;mp[x]=1;
for(int i=1;i<=cnt;i++) dfs(x/pr[i]);
}
int main(){
LL g=gcd(n,a[k]),tmp=g,i=1;
for(i=2;i*i<=tmp;i++){
if(tmp%i==0){
pr[++cnt]=i;
while(tmp%i==0) tmp/=i;
}
}
if(tmp>1) pr[++cnt]=tmp;
for(i=1;i<k;i++) dfs(gcd(g,a[i]));
for(i=1;i*i<=g;i++) if(g%i==0&&!mp[i]) return printf("%lld\n",n/i),0;
for(;i>=1;i--) if(g%i==0&&!mp[g/i]) return printf("%lld\n",n/(g/i)),0;
}
T2 牛牛的猜球游戏
大水题，用一个前缀数组记录操作到第 $i$ 项时的杯子的摆放情况。
然后对于每次询问根据 $a_{l-1}$ 的值得到从 $a_{l-1}$ 执行到 $a_r$ 后的摆放情况
不多说了，直接上代码(100pts)：
int n,m,a[100005][10],b[10];
int main(){
scanf("%d%d",&n,&m),iota(a[0],a[0]+10,0);
for(int i=1,x,y;i<=n;i++){
copy(a[i-1],a[i-1]+10,a[i]);
scanf("%d%d",&x,&y),swap(a[i][x],a[i][y]);
}
for(int i=1,l,r;i<=m;i++){
scanf("%d%d",&l,&r);
for(int j=0;j<10;j++) b[a[l-1][j]]=j;
for(int j=0;j<10;j++) printf("%d ",b[a[r][j]]);
printf("\n");
}
}
T3 牛牛的凑数游戏
可以想到一种很简单的单次 $O(n log n)$ 做法：
将数组从小到大排序，然后枚举 $i$ 如果 $a_i \leq sum+1$，就把 $a_i$ 加到 $sum$ 中。
根据这种想法可以延伸出一种莫队的解法，也就是我赛上最开始写的 30pts 做法：
先按莫队的板子将所有询问离线排序，然后我们考虑回滚莫队。
莫队时记录当前的 $ans$ 值，并维护一个小顶堆的优先队列。
向莫队中添加元素时，我们就直接将元素塞进优先队列里面，然后每次 while 循环是否满足 $top() \leq sum+1$，是就弹出堆顶并累加答案。
这种解法的期望复杂度应该是 $O(n \sqrt{n} \log n)$，但是会被卡，因为回滚时有可能出现每次都重新弹出 $n$ 个数的情况。
所以最坏的复杂度仍为 $O(nm \log n)$，与暴力相同。
但我赛场上没有想到这个点，一直在死磕莫队，浪费了多到无法想象的时间
贴一下莫队的代码(30pts)：
#define N 100005
#define LL long long
LL tmp,sum,ans[N];
int n,m,cnt,a[N],bel[N];
struct Node{int l,r,num;}s[N];
priority_queue<int,vector<int>,greater<int>> q,tq;
bool cmp(Node x,Node y){
if(bel[x.l]!=bel[y.l]) return bel[x.l]<bel[y.l];
return x.r<y.r;
}
void add(LL &sum,LL x,que &q){
q.push(x);
while(!q.empty()&&sum+1>=q.top()) sum+=q.top(),q.pop();
}
int main(){
scanf("%d%d",&n,&m);
int block=sqrt(n);
for(int i=1;i<=n;i++) scanf("%d",a+i),bel[i]=(i-1)/block+1;
for(int i=1,l,r;i<=m;i++){
scanf("%d%d",&l,&r);
if(bel[l]==bel[r]){
sum=0;while(!q.empty()) q.pop();
for(int j=l;j<=r;j++) add(sum,a[j],q);
ans[i]=sum+1;
}
else s[++cnt]={l,r,i};
}
sort(s+1,s+cnt+1,cmp);
for(int i=1,l,r;i<=cnt;i++){
if(bel[s[i].l]!=bel[s[i-1].l]){
r=bel[s[i].l]*block,sum=0;
while(!q.empty()) q.pop();
}
while(r<s[i].r) add(sum,a[++r],q);
l=bel[s[i].l]*block+1,tmp=sum,tq=q;
while(l>s[i].l) add(tmp,a[--l],tq);
ans[s[i].num]=tmp+1;
}
for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
}
后来我想通了，但只剩 1h 多一点时间了，虽然说这道题还是做出来了。
莫队不行于是考虑转变思路。
能够想到另外一种单次 $O(n \log V)$ 的解法：
使用树状数组维护对于任意 $x$，满足小于等于 $x$ 的数字和。
然后 while 循环每次加上所有小于等于当前 $sum+1$ 的数，没有就退出循环。
为什么复杂度是正确的呢？因为如果要加，$sum$ 最少都会翻倍，不加就退出了，自然是 log 的复杂度。
考虑怎么降低复杂度，有前面莫队的铺垫，应该会比较容易想到离线处理所有询问，至少我死磕莫队后脑子里就只剩离线了。
先把所有询问离线出来然后对于每次 while 循环，我们先记录下上一次循环后的答案，并把每次询问拆成 $[1,l)$ 和 $[1,r]$ 两个区间，前减后加。
接下来 for 循环扫一遍看有没有询问的答案发生过变化，没有就直接 break，复杂度 $O(n \log^2 n)$。
贴一下最后的代码(100pts)：
#define N 100005
#define LL long long
LL tr[N],lst[N],ans[N];
int n,m,tot,a[N],rk[N];
vector<pair<int,int>> v[N];
void update(int x,int y){while(x<=tot) tr[x]+=y,x+=x&(-x);}
LL query(int x,LL ans=0){while(x) ans+=tr[x],x-=x&(-x);return ans;}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",a+i),rk[i]=a[i];
sort(rk+1,rk+n+1),tot=unique(rk+1,rk+n+1)-rk-1;
for(int i=1;i<=n;i++) a[i]=lower_bound(rk+1,rk+tot+1,a[i])-rk;
for(int i=1,l,r;i<=m;i++){
scanf("%d%d",&l,&r);
v[l-1].push_back({i,-1}),v[r].push_back({i,1});
}
while(1){
for(int i=1;i<=n;i++) lst[i]=ans[i],ans[i]=tr[i]=0;
for(int i=1;i<=n;i++){
update(a[i],rk[a[i]]);
for(auto [x,y]:v[i]) ans[x]+=y*query(upper_bound(rk+1,rk+tot+1,lst[x]+1)-rk-1);
}
for(int i=1;i<=n;i++) if(lst[i]!=ans[i]) goto con;
break;con:;
}
for(int i=1;i<=m;i++) printf("%lld\n",ans[i]+1);
}
T4 牛牛的RPG游戏
先考虑一维做法，也就是 $\min(n,m) \leq 1$ 的部分分，设 $dp_i$ 表示走到第 $i$ 格的最大得分，得到转移式：
$
dp_i=max^{j \leq i}_{j=1}dp_j+buff_j*(i-j)+val_j
$
发现是斜率优化的经典转移，使用李超线段树优化即可。
关于我赛时 val 和 buf 输入反了这一件事，我的 20pts 啊！
一维部分分代码(20pts)：
#define N 100005
#define LL long long
int n,m;
LL val[N],buf[N],dp[N];
struct Lichao_Segment_Tree{
LL query(LL x)//查询x位置的最大值
void insert(LL k,LL b)//插入一条直线
}LCT;//李超模板代码就不放了
int main(){
for(int i=0;i<m;i++){
if(!i) LCT.insert(0,0);
else{
dp[i]=LCT.query(i)+val[i];
LCT.insert(buf[i],dp[i]-i*buf[i]);
if(val[i]<0) dp[i]-=val[i];
}
}
}
接下来我们考虑扩展到二维上。
设 $dp_{i,j}$ 表示走到 $i$ 行 $j$ 列时的最大得分，可以列出转移式：
$
dp_{i,j}=max^{u\leq i,v\leq j}{u=1,v=1}dp+buff_{i,j}*(u+v-i-j)+val_{i,j}
$
这个时候直接用李超来优化就不是很好做了。神犇zyx可以忽略这句话
观察可以发现 $u \leq i,v \leq j$ 是一个二维偏序，联想以前学过的知识，cdq 分治可以解决这类问题。
接下来就可以 cdq 套李超线段树，理论上可能会很毒瘤，但实际写着其实并不会，时间复杂度 $O(n \log^2 n)$。
贴下代码(100pts)：
#define N 100005
#define LL long long
int n,m,rt;
vector<LL> val[N],buf[N],dp[N];
struct Lichao_Segment_Tree{
void clear()//清空
LL query(LL x)//查询x位置的最大值
void insert(LL k,LL b)//插入一条直线
}LCT;//李超模板代码就不放了
void cdq(int l,int r){
if(l==r){
LCT.insert(0,0);
for(int i=1;i<=m;i++){
dp[l][i]=max(dp[l][i],LCT.query(i));
LCT.insert(buf[l][i],dp[l][i]-i*buf[l][i]+val[l][i]);
}
return LCT.clear();
}
int mid=(l+r)>>1;cdq(l,mid),LCT.insert(0,0);
for(int j=1;j<=m;j++){
for(int i=l;i<=mid;i++)
LCT.insert(buf[i][j],dp[i][j]-(i+j)*buf[i][j]+val[i][j]);
for(int i=mid+1;i<=r;i++) dp[i][j]=max(dp[i][j],LCT.query(i+j));
}
LCT.clear(),cdq(mid+1,r);
}
多介绍一种来自 zyx 的方法：对每一行开一个李超线段树，并以 $\min(n,m)$ 作为行，暴力做纵向转移，时间复杂度 $O(nm \sqrt{nm} \log n)$。
标签：gcd,int,题解,LL,long,becoder,8.30,复杂度,define From： https://www.cnblogs.com/tkdqmx/p/18395254