8-6 ST表与树状数组测试总结

· · 个人记录

question Expected score Actual score
T1 100 100
T2 100 100
T3 100 100
T4 100 100
T5 100 88
T6 100 10
T7 100 40
T8 0 0

错题总结

T5:

思路

我们可以用ST表来维护前缀和。

我们先来看下这段代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+5;
int n,lg[N],m,f[N][30],a[N],ans,sum[N];
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
sum[i]=sum[i-1]+a[i];
f[i][0]=sum[i];
}
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+a[i];
f[i][0]=sum[i];
}
for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
for(int j=1;j<=25;j++){
for(int i=0;i+(1<<j)-1<=n;i++){
f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
}
for(int i=1;i<=n;i++){
int l;
if(i<=m)l=0;
else l=i-m;
int len=i-l+1;
int j=lg[len];
int mi=min(f[l][j],f[i-(1<<j)+1][j]);
ans=max(ans,sum[i]-mi);
}cout<<ans;
return 0;
}

看这段代码，是不是感觉能AC？但实际上：

第九个测试点竟然WA了！！！

然后我们下载测试点看一看：

in:

5
-1 -1 -1 -1 -1

out:

-1

然而，我们上面的那段代码输出的是0，那么我们可以面向数据编程，在最后输出ans改成：

if(ans==0)
cout<<-1;
else cout<<ans;

开个玩笑，下面才是正经的。

我们来思考一下：

题目要求：1\le k \le m，也就是小Z必须要吃。而上面的代码是可以选择不吃的，所以会输出0。

所以，我们要加上一段：

bool flag=0;
int maxn=-1e18;
for(int i=1;i<=n;i++){
if(a[i]>=0){
flag=1;
break;
}
maxn=max(maxn,a[i]);
}
if(flag==0){
cout<<maxn;
return 0;
}

这段代码是什么意思？如果这些蛋糕的幸运值都小于0，但必须要吃，所以就选择吃幸运值大的那一块，不然吃多块蛋糕，幸运值会越来越小。

AC code


#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+5;
int n,lg[N],m,f[N][30],a[N],ans,sum[N];
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
    cin>>a[i];
    sum[i]=sum[i-1]+a[i];
    f[i][0]=sum[i];
}
bool flag=0;
int maxn=-1e18;
for(int i=1;i<=n;i++){
    if(a[i]>=0){
        flag=1;
        break;
    }
    maxn=max(maxn,a[i]);
}
if(flag==0){
    cout<<maxn;
    return 0;
}
for(int i=1;i<=n;i++){
    sum[i]=sum[i-1]+a[i];
    f[i][0]=sum[i];
}
for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
for(int j=1;j<=25;j++){
    for(int i=0;i+(1<<j)-1<=n;i++){
        f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
    }
}
for(int i=1;i<=n;i++){
    int l;
    if(i<=m)l=0;
    else l=i-m;
    int len=i-l+1;
    int j=lg[len];
    int mi=min(f[l][j],f[i-(1<<j)+1][j]);
    ans=max(ans,sum[i]-mi);
}cout<<ans;
return 0;

}

## T6:
### 思路
>维护树状数组，计算每个区间的逆序对个数，然后取最大值。
>
>注意：是最大值，不是求和！！！（~~样例要不要这么水呀~~）
### AC code
```cpp
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+5;
int n,m,sum[N],ans,cnt;
int b[N],a[N];
map<int,int>mp;
int lowbit(int x){
    return x & -x;
}
int get_sum(int x){
    int res=0;
    while(x){
        res+=sum[x];
        x-=lowbit(x);
    }
    return res;
}
void modify(int x,int val){
    while(x<=n){
        sum[x]+=val;
        x+=lowbit(x);
    }
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    int idx=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++){
        int x=lower_bound(b+1,b+idx+1,a[i])-b;
        ans=max(ans,get_sum(idx)-get_sum(x));
        modify(x,1);
    }cout<<ans+1;
    return 0;
}

T7:

考试结束还差11min的时候想到了二分+ST表，于是在最后2min的时候写出了下面的代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+5;
int n,m,sumf[N],sums[N],f[N][25],lg[N];
struct node{
int f,s;
}a[N];
int ans=1e18;
bool check(int l,int r){
int fr=sumf[r],fl=sumf[l-1];
if(fr-fl>=m)return 1;
return 0;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i].f>>a[i].s;
sumf[i]=sumf[i-1]+a[i].f;
f[i][0]=a[i].s;
}
for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
for(int j=1;j<=20;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]);
}
}
for(int i=1;i<=n;i++){
int l=1,r=i,mid;
while(l<=r){
mid=l+r>>1;
if(check(l,r)){
l=mid+1;
int len=i-mid+1,j=lg[len];
ans=min(ans,max(f[l][j],f[i-(1<<j)+1][j]));
}
else r=mid-1;
}
}cout<<ans;
return 0;
}

样例也过了，结果只有40分。

但其实，这题只是一道二分答案的题目。

AC code

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+5;
int f[N],s[N],n,m;
bool check(int x){
int sum=0;
for(int i=1;i<=n;i++){
if(s[i]>x)sum=0;
else sum+=f[i];
if(sum>=m)return 1;
}return 0;
}
int ma,ans;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>f[i]>>s[i];
for(int i=1;i<=n;i++)ma=max(ma,s[i]);
int l=1,r=ma,mid;
while(l<=r){
mid=l+r>>1;
if(check(mid)){
r=mid-1;
ans=mid;
}
else l=mid+1;
}cout<<ans;
return 0;
}