题解 P1311 【选择客栈】

· · 题解

这道题可以用暴力枚举区间RMQ 的方式水过60分，我们选择树状树组（好写，而且常数小）

code60

#include<bits/stdc++.h>
using namespace std;
int a[500001],tree[500001],n,k,q,col[500001];
//a是当前客栈的最小花费
//tree维护rmq
//col是当前客栈的颜色
inline int lowbit(int x){return x&-x;}

inline void add(int x,int y)
{
    //添加函数（树状数组只支持末尾添加）
    while(x<=n)
    {
        if(tree[x]>y)
          tree[x]=y;
        x+=lowbit(x);
    }
}
inline int findd(int x,int y)
{
    //查找函数
    int ff=y,maxx=2147483647;
    while(ff>=x)
    {
        if(ff-lowbit(ff)>x)
        {
            maxx=min(maxx,tree[ff]);
            ff-=lowbit(ff);
        }
        else
        {
            maxx=min(maxx,a[ff]);
            ff--;
        }
    }
    return maxx;
}
int main()
{
    memset(tree,127,sizeof(tree));
    cin>>n>>k>>q;
    int ans=0;
    for(register int i=1;i<=n;i++)
      {
          cin>>col[i]>>a[i];
          add(i,a[i]);
      }
    for(register int i=1;i<=n;i++)
      for(register int j=i+1;j<=n;j++)
      {
          if(col[i]==col[j])
            if(findd(i,j)<=q)
              ans++;
       //暴力大枚举所有可能区间
      }
    cout<<ans<<endl;
    return 0;
}

但是这个算法明显不够优秀，我们考虑玄学优化！！

前缀和优化大法好！！

我们新建一个sum [i] [j],表示第i种颜色到j位置的客栈数量

则每次查找到一个区间之后再加上（j,n]这个区间的此颜色的客栈数量（此处不加证明，纯前缀和思想）

code100

#include<bits/stdc++.h>
using namespace std;
int a[500001],tree[500001],n,k,q,col[500001],sum[51][200001];

inline int lowbit(int x){return x&-x;}

inline void add(int x,int y)
{
    while(x<=n)
    {
        if(tree[x]>y)
          tree[x]=y;
        x+=lowbit(x);
    }
}
inline int findd(int x,int y)
{
    int ff=y,maxx=2147483647;
    while(ff>=x)
    {
        if(ff-lowbit(ff)>x)
        {
            maxx=min(maxx,tree[ff]);
            ff-=lowbit(ff);
        }
        else
        {
            maxx=min(maxx,a[ff]);
            ff--;
        }
    }
    return maxx;
}
int main()
{
    memset(tree,127,sizeof(tree));
    memset(sum,0,sizeof(sum));
    cin>>n>>k>>q;
    int ans=0;
    for(register int i=1;i<=n;i++)
      {
          cin>>col[i]>>a[i];
          add(i,a[i]);
      }
    for(int j=0;j<k;j++)
      for(int i=1;i<=n;i++)
          if(col[i]==j)
            sum[j][i]=sum[j][i-1]+1;
          else
            sum[j][i]=sum[j][i-1];
    for(register int i=1;i<=n;i++)
      for(register int j=i+1;j<=n;j++)
          if(col[i]==col[j]&&findd(i,j)<=q)
            {
                ans++;
                ans+=sum[col[i]][n]-sum[col[i]][j];
                //及时跳出，使我们的复杂度非常玄学，取决于数据的强弱
                //
                break;
            }
    cout<<ans<<endl;
    return 0;
}