洛谷4755 Beautiful Pair （分治）

题目描述

小D有个数列 \(a\)，当一个数对 \((i,j)(i\le j)\) 满足\(a_i\)和\(a_j\)的积不大于 \(a_i \cdots a_j\) 中的最大值时，小D认为这个数对是美丽的.请你求出美丽的数对的数量。

输入格式：

第一行输入一个整数 \(n\)，表示元素个数。第二行输入 \(n\) 个整数 \(a_1,a_2,a_3,\cdots,a\)，为所给的数列。

输出格式：

输出一个整数，为美丽的数字对数。

其中\(m\le 10^5，a_i \le 10^9\)

这个题，看到题的第一想法就是QwQ，一看就是dp或者一些恶心的数据结构题，但是想了一会dp，发现不太可行。那么我们可以考虑通过**分治** 来解决这个问题

我们考虑，对于一个区间\([l,r]\)，我们可以通过这个区间的\(mx\)（表示最大的\(a_i\)）来解决，因为要求乘积不能大于区间的最大值，所以我们在计算区间的时候，\(mx\)一般情况下是不能和别的数进行组合的。所以说，按照mx来分组，那么当前区间的答案就是\([l,mx-1]\)的答案加上\([mx+1,r]\)，然后加上两个区间产生的贡献。

QwQ那么怎么求左右区间产生的贡献呢

我们考虑，对于一个固定的左端点\(l\)，我们需要在\([mx+1,r]\)区间找出，小于\(\lfloor \frac{mx}{a_l} \rfloor\)的数的个数

然后我们枚举所有的左端点，然后数一数，最后考虑\(mx\)这个端点可以不可以跟左边的这个区间进行组合

那么我们应该怎么求一个区间内小于等于一个数的个数呢

QwQ

呀，BIT！树状数组嗯！

我们考虑将每个数进行离散化，然后维护一个权值树状数组，然后我们每次只需要\(query(find(\lfloor \frac{mx}{a_l} \rfloor))\)就可以，其中\(find\)的函数的作用是，找到这个值离散化后的小于等于它的最大的值，其实可以直接\(lower_bound\)

记得离散化！

还有一些人会问，这个算法的时间复杂度可以保证吗？QwQ具体的证明我也不是很会呀，不过可以感性l理解

如果我们每次挑选的\(mx\)，都选择比较中间的，那么我们可以大致理解是\(O(nlogn)\)的

直接上代码

dfs版的分治

非常理解，个人敢接

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#include<unordered_map>

using namespace std;

inline int read()

{

  int x=0,f=1;char ch=getchar();

  while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}

  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

  return x*f;

}

const int maxn =  1e5+1e2;

int c[maxn];

int a[maxn];

int b[maxn];

int n,m;

int dp[maxn][23];

int p[maxn];

int tmp = 0;

unordered_map<int,int> mp;

struct Node{

    int id,val;

};

Node g[maxn];

int lowbit(int x)

{

    return (-x) & x;

}

void update(int x,int p)

{

    for (int i=x;i<=n;i+=lowbit(i)) c[i]+=p;

}

long long query(int x)

{

    long long ans=0;

    for (int i=x;i;i-=lowbit(i)) ans+=(long long)c[i];

    return ans;

}

int find(int x)

{

    if (x>p[n]) return tmp;

    return g[upper_bound(p+1,p+1+n,x)-p-1].id;

}

bool cmp(Node a,Node b)

{

    return a.val<b.val;

}

int countmax(int x,int y)

{

    int k = log2(y-x+1);

    return max(dp[x][k],dp[y-(1 <<k)+1][k]);

}

void init()

{

    for (int j=1;j<=21;j++)

      for (int i=1;i<=n;i++)

      {

      	 if (i+(1 << j)-1<=n)

      	 {

      	 	dp[i][j]=max(dp[i][j-1],dp[i+(1 << (j-1))][j-1]);

           }

      }

}

long long solve(int l,int r)

{

    if (l>r) return 0;

    if (l==r)  {

      if (a[l]==1)return 1;

      else return 0;

    }

    long long cnt=0;

    int mid = (l+r) >> 1;

    int mx = countmax(l,r),pos=0;

    for (int i=l;i<=r;i++)

    {

        if (a[i]==mx) {

           if (!pos || abs(mid-i)<abs(mid-pos)) pos=i;

        }

    }

    cnt+=solve(l,pos-1);

    cnt+=solve(pos+1,r);

    for (int i=pos+1;i<=r;i++) update(b[i],1);

    for (int i=l;i<=pos;i++) cnt=cnt+(query(find(mx/a[i])));

    for (int i=pos+1;i<=r;i++) update(b[i],-1);

    //cout<<l<<" "<<r<<" "<<cnt<<endl;

    for (int i=l;i<=pos-1;i++) update(b[i],1);

     cnt=cnt+(query(find(mx/a[pos])));

    for (int i=l;i<=pos-1;i++) update(b[i],-1);

    //out<<l<<" "<<r<<" "<<cnt<<endl;

    if (a[pos]==1) cnt++;

    return cnt;

}

int main()

{

  n=read();

  for (int i=1;i<=n;i++) a[i]=read(),g[i].id=i,g[i].val=a[i],dp[i][0]=a[i];

  init();

  sort(g+1,g+1+n,cmp);

  for (int i=1;i<=n;i++)

  {

  	 if (g[i].val!=g[i-1].val) tmp++;

  	 b[g[i].id]=tmp;

  	 mp[a[g[i].id]]=tmp;

  }

  //for (int i=1;i<=n;i++) cout<<b[i]<<" ";

  memset(g,0,sizeof(g));

  for (int i=1;i<=n;i++) p[i]=a[i],g[i].val=a[i],g[i].id=b[i];

  sort(g+1,g+1+n,cmp);

  sort(p+1,p+1+n);

  //cout<<endl;

  long long ans=solve(1,n);

  cout<<ans;

  return 0;

}

巴特西

洛谷4755 Beautiful Pair （分治）

最新文章

热门文章