已完成2/9（要准备中考啊QwQ）
T1
考虑对所有数分解质因数，其中因子>sqrt(100000)的因子最多有一个，于是我们可以暴力维护<sqrt(100000)的因子个数的前缀和。
剩下的就是判区间里一个数出现的次数。我写了主席树。。。
code
#include <bits/stdc++.h>
using namespace std;
int tot,i,j,k,n,m,x,y,t,cas,prime1[],prime2[],b[],num1[],num2[],tt,c[],s[][];
inline int read(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>''){f=ch=='-'?-f:f;ch=getchar();}
while (ch>=''&&ch<=''){x=x*+ch-;ch=getchar();}
return x*f;
}
inline void pre(){
tot=;
for (register int i=;i<=;i++)
if (!b[i]){
b[i]=;prime2[i]=++tot;
if (i<)prime1[tot]=i,tt=tot;
for (register int j=i;j<=;j+=i)b[j]=;
}
}
int rt[],l[],r[],size[],num;
inline void Build(int &rt,int L,int R){if (!rt)rt=++num;if (L==R)return;Build(l[rt],L,L+R>>);Build(r[rt],(L+R>>)+,R);}
inline void Insert(int &rt,int la,int L,int R,int v){
if (!rt)rt=++num;
if (L==R){size[rt]=size[la]+;return;}
l[rt]=l[la];r[rt]=r[la];
int mid=L+R>>;
if (v<=mid){l[rt]=;Insert(l[rt],l[la],L,mid,v);}else {r[rt]=;Insert(r[rt],r[la],mid+,R,v);}
}
inline int calc(int rt,int L,int R,int x){
if (!rt)return ;
if (L==R)return size[rt];int mid=L+R>>;
if (x<=mid)return calc(l[rt],L,mid,x);else return calc(r[rt],mid+,R,x);
}
int V[];
int main(){
cas=read();pre();
while (cas--){
n=read();m=read();
for (register int i=;i<=n;i++){
x=read();y=x;V[i]=x;
for (register int j=;j<=tt;j++)s[i][j]=s[i-][j];
for (register int j=;j<=tt;j++){while (x%prime1[j]==)s[i][j]++,x/=prime1[j];if (x==)break;}
c[i]=x;
}
memset(rt,,sizeof rt);
memset(l,,sizeof l);
memset(r,,sizeof r);
memset(size,,sizeof size);
num=;Build(rt[],,tot);
for (register int i=;i<=n;i++)Insert(rt[i],rt[i-],,tot,prime2[c[i]]);
while (m--){
int L=read(),R=read();x=read();
memset(num1,,sizeof num1);
memset(num2,,sizeof num2);
for (register int j=;j<=tt;j++){while (x%prime1[j]==)x/=prime1[j],num2[j]++;if (x==)break;}
for (register int j=;j<=tt;j++)num1[j]=s[R][j]-s[L-][j];
bool bo=;
for (register int j=;j<=tt;j++)if (num1[j]<num2[j]){puts("No");bo=;break;}
if (!bo)continue;
if (x==){puts("Yes");continue;}
if (calc(rt[R],,tot,prime2[x])-calc(rt[L-],,tot,prime2[x])<)puts("No");else puts("Yes");
}
}
return ;
}
T1
T2
考虑DP，f[i][j][x][y]表示走到i,j，并且路径上有x个没选，并在前i-1行以及第i行前j-1个里选了y个的最优值。ans显然等于max(f[n][m][i][i])0<=i<=t
然后转移。
f[i][j][x][y]可以直接转移到f[i][j+1][x][y]以及f[i][j+1][x+1][y]（i,j+1不选）
再考虑往下转移，(i+1,j)也可以选或不选，然后，再在(i,j+1)~(i,m)以及(i+1,1)~(i+1,j-1)中选最大的k个，转移给f[i+1][j][x+(1 or 0)][y+k]
code
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define RI register int
using namespace std;
typedef long long ll;
int i,j,k,n,m,x,y,t,T,b[][][];
ll f[][][][],a[][];
int read(){
int x=,f=;
char ch=getchar();
while (ch<''||ch>''){f=ch=='-'?-f:f;ch=getchar();}
while (ch>=''&&ch<=''){x=x*+ch-;ch=getchar();}
return x*f;
}
inline int max(int x,int y){return x>y?x:y;}
int main(){
T=read();
while (T--){
n=read();m=read();x=read();
for (RI i=;i<=n;i++)for (RI j=;j<=m;j++)scanf("%lld",&a[i][j]);;
memset(b,,sizeof b);
for (RI i=;i<n;i++)
for (RI j=;j<=m;j++){
for (RI k=j+;k<=m;k++)b[i][j][++b[i][j][]]=a[i][k];
for (RI k=;k<j;k++)b[i][j][++b[i][j][]]=a[i+][k];
sort(b[i][j]+,b[i][j]++b[i][j][]);
}
memset(f,-,sizeof f);
f[][][][]=a[][];f[][][][]=;
for (RI i=;i<=n;i++)
for (RI j=;j<=m;j++)
for (RI k=;k<=x;k++)
for (RI t=;t<=x;t++)
if (f[i][j][k][t]>-){
if (j<=m){
f[i][j+][k][t]=max(f[i][j+][k][t],f[i][j][k][t]+a[i][j+]);
if (k<x)f[i][j+][k+][t]=max(f[i][j+][k+][t],f[i][j][k][t]);
}
if (i<n){
ll p=;
for (RI h1=;h1+t<=x;h1++){
p+=b[i][j][b[i][j][]-h1+];
f[i+][j][k][t+h1]=max(f[i+][j][k][t+h1],f[i][j][k][t]+p+a[i+][j]);
if (k<x){f[i+][j][k+][t+h1]=max(f[i+][j][k+][t+h1],f[i][j][k][t]+p);}
}
}
}
ll ans=;for (RI i=;i<=x;i++)ans=max(ans,f[n][m][i][i]);
printf("%lld\n",ans);
}
return ;
}
T2