这份代码这样写在test6会输出chong
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
template<typename T>inline void read(T &x){
x=0;int f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
x*=f;
}
int T,n,mxb,s,ans,a[N],idx;
int mp[N<<2];
int t[N],f;
inline void add(int x,int y){
for(;x<=mxb;x+=x&-x) t[x]=max(t[x],y);
}
inline int query(int x){
int ans=0;
for(;x;x-=x&-x) ans=max(ans,t[x]);
return ans;
}
int main(){
read(T),read(n),read(mxb),read(s);
while(T--){
idx=0;
for(int i=1;i<=n;++i){
read(a[i]);
if(mp[a[i]]){
cout<<"chong";
return 0;
}
}
for(int i=1;i<=n;++i){
if(!mp[a[i]]) ++idx,mp[a[i]]=1;
}
if(s>=idx){
printf("%d\n",idx);
continue;
}
ans=0;
memset(t,0,sizeof(t));
for(int j=1;j<=s;++j)
for(int i=1;i<=n;++i){
f=query(a[i]-1)+1;
ans=max(ans,f);
add(a[i],f);
}
printf("%d\n",ans);
memset(mp,0,sizeof(mp));
}
return 0;
}
但是吧memset放前面就A了
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
template<typename T>inline void read(T &x){
x=0;int f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
x*=f;
}
int T,n,mxb,s,ans,a[N],idx;
int mp[N<<2];
int t[N],f;
inline void add(int x,int y){
for(;x<=mxb;x+=x&-x) t[x]=max(t[x],y);
}
inline int query(int x){
int ans=0;
for(;x;x-=x&-x) ans=max(ans,t[x]);
return ans;
}
int main(){
read(T),read(n),read(mxb),read(s);
while(T--){
idx=0;
memset(mp,0,sizeof(mp));
for(int i=1;i<=n;++i){
read(a[i]);
if(mp[a[i]]){
cout<<"chong";
return 0;
}
}
for(int i=1;i<=n;++i){
if(!mp[a[i]]) ++idx,mp[a[i]]=1;
}
if(s>=idx){
printf("%d\n",idx);
continue;
}
ans=0;
memset(t,0,sizeof(t));
for(int j=1;j<=s;++j)
for(int i=1;i<=n;++i){
f=query(a[i]-1)+1;
ans=max(ans,f);
add(a[i],f);
}
printf("%d\n",ans);
}
return 0;
}