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

· · 个人记录

考试情况

题目编号 分数
T1 100
T2 100
T3 100
T4 100
T5 100
T6 10
T7 60
T8 10

总分数:580 本来如果T6不把暴力改成逆序对可以多拿50pts,那么这样直接number1--->630pts

T6 P4378 [USACO18OPEN] Out of Sorts S

考场代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
int c[N],n,m,a[N],b[N];
//bool cmp(int a,int b)
//{
//  return a>b;
//}
int lowbit(int x)
{
    return x&-x;
}
int get_ans(int x)
{
    int res=0;
    while(x)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
void modify(int x,int val)
{
    while(x<=n)
    {
        c[x]+=val;
        x+=lowbit(x);
    }
    return ;
}
map<int,int> mp;
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];
//  int cnt=0;
//  bool flag=0;
//  while(!flag)
//  {
//      flag=1;
//      cnt++;
//      for(int i=1;i<n;i++)
//      {
//          if(a[i+1]<a[i])
//          {
//              swap(a[i+1],a[i]);
//              flag=0;
//          }
//      }
//  }
//  cout<<cnt;
    int sum=0,cnt=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++)
    {
        if(b[i]!=b[i-1])mp[b[i]]=++cnt;
    }
    for(int i=n;i>=1;i--)
    {
        sum+=get_ans(mp[a[i]]-1);
        modify(mp[a[i]],1);
    }
    cout<<sum;
    return 0;
}

考场错误

想到了逆序对，可是逆序对是任意两个点，但是本题的要求是说必须是两个相邻的数。

正确思路

其实可以用结构体+sort解决

我们可以观察伪代码，是从小到大排序，那么我们的cmp函数首先可以先写出这个步骤x.num<y.num

但是只用这一个判断只能得到80pts,所以我们再观察题目，由于本题一个数会出现多次，所以我们在排序时，还要再判断等于的情况，若等于则要让原位置后的位置排序时前

然后排完序后，因为在最后一次修改后,sorted的值依然是0 .所以要再刷一次,也就是说答案要+1。

AC代码

#include<bits/stdc++.h>
#define int long long   
using namespace std;
const int N=1e6+5;
struct node
{
    int id,num;
}a[N];
bool cmp(node x,node y)
{
    return x.num<y.num||(x.num==y.num&&x.id<y.id);
}
signed main()
{
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].num;
        a[i].id=i;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)ans=max(ans,a[i].id-i);
    cout<<ans+1;
    return 0;
}

T7 P4085 [USACO17DEC] Haybale Feast G

考场代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int a[N],b[N];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
    int minn=1e18;
    for(int i=1;i<=n;i++)
    {
        int sum=0,ans=0;
        for(int j=i;j<=n;j++)
        {
            sum+=a[j];
            ans=max(ans,b[j]);
            if(sum>=m)
            {
                minn=min(minn,ans);
                break;
            }
        }
    }
    cout<<minn;
    return 0;
}

其实是用暴力写的，所以没什么值得调的，直接将正确思路

正确思路

二分答案

这道题目使用瞪眼法可以发现，其实具有单调性，我们可以用check来查找连续的一段区间能否满足M,

AC代码

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