8.6晚 st表+树状数组
P3865 【模板】ST 表 && RMQ 问题
错误代码如下```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+10;
int n,m;
int f[maxn][25];
int a[maxn];
int lg[maxn];
void q(){
for(int i=1;i<=n;i++){
f[i][0]=a[i];
}
for(int i=2;i<=n;i++){
lg[i]=lg[i/2]+1;
}
for(int j=1;(1<<j)<=n;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
return ;
}
int get_ans(int l,int r){
int len=r-l+1;
int k=lg[len];
return max(f[l][k],f[r-(1<<k)+1][k]);
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
q();
for(int i=1;i<=m;i++){
int l,r;
cin>>l>>r;
cout<<get_ans(l,r)<<'\n';
}
return 0;
} 错因
总的来说就是忘记加上题目给的快读输入
如果您认为您的代码时间复杂度正确但是 TLE，可以尝试使用快速读入：
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
或者也忘记加关闭同步流了
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);P3374 【模板】树状数组 1
AC了 板子题
P2412 查单词
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=5e4+10;
int n,m;
string f[maxn][25];
string a[maxn],b[maxn];
int lg[maxn];
string daxiao(string s){
int len=s.size();
for(int i=0;i<len;i++){
if(s[i]>='a'&&s[i]<='z'){
s[i]-=32;
}
}
return s;
}
void q(){
for(int i=1;i<=n;i++){
f[i][0]=a[i];
}
for(int i=2;i<=n;i++){
lg[i]=lg[i/2]+1;
}
for(int j=1;(1<<j)<=n;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
if(daxiao(f[i][j-1])<=daxiao(f[i+(1<<(j-1))][j-1])){
f[i][j]=f[i+(1<<(j-1))][j-1];
}else{
f[i][j]=f[i][j-1];
}
}
}
return ;
}
string get_ans(int l,int r){
int len=r-l+1;
int k=lg[len];
if(f[l][k]<=f[r-(1<<k)+1][k]){
return f[r-(1<<k)+1][k];
}
else return f[l][k];
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
string s;
cin>>s;
a[i]=s;
}
q();
for(int i=1;i<=m;i++){
int l,r;
cin>>l>>r;
cout<<get_ans(l,r)<<'\n';
}
return 0;
} 错因
string get_ans(int l,int r){
int len=r-l+1;
int k=lg[len];
if(f[l][k]<=f[r-(1<<k)+1][k]){
return f[r-(1<<k)+1][k];
}
else return f[l][k];
}最后得到答案还需要最后一次比较
我的f数组是存最大的原字符串 大小写敏感
最后应该判断需要统一大小写 再输出
改后
string get_ans(int l,int r){
int len=r-l+1;
int k=lg[len];
if(daxiao(f[l][k])<=daxiao(f[r-(1<<k)+1][k])){//问题所在
return f[r-(1<<k)+1][k];
}
else return f[l][k];
}