洛谷4755 Beautiful Pair (分治)
题目描述
小D有个数列 ,当一个数对 满足和的积 不大于 中的最大值时,小D认为这个数对是美丽的.请你求出美丽的数对的数量。
输入格式:
第一行输入一个整数 ,表示元素个数。 第二行输入 个整数 ,为所给的数列。
输出格式:
输出一个整数,为美丽的数字对数。
其中
这个题,看到题的第一想法就是QwQ,一看就是dp或者一些恶心的数据结构题,但是想了一会dp,发现不太可行。那么我们可以考虑通过分治 来解决这个问题
我们考虑,对于一个区间,我们可以通过这个区间的(表示最大的)来解决,因为要求乘积不能大于区间的最大值,所以我们在 计算区间的时候,一般情况下是不能和别的数进行组合的。所以说,按照mx来分组,那么当前区间的答案就是的答案加上,然后加上两个区间产生的贡献。
QwQ那么怎么求左右区间产生的贡献呢
我们考虑,对于一个固定的左端点,我们需要在区间找出,小于的数的个数
然后我们枚举所有的左端点,然后数一数,最后考虑这个端点可以不可以跟左边的这个区间进行组合
那么我们应该怎么求一个区间内小于等于一个数的个数呢
QwQ
呀,BIT!树状数组 嗯!
我们考虑将每个数进行离散化,然后维护一个权值树状数组,然后我们每次只需要就可以,其中的函数的作用是,找到这个值离散化后的小于等于它的最大的值,其实可以直接
记得离散化!
还有一些人会问,这个算法的时间复杂度可以保证吗?QwQ具体的证明我也不是很会呀,不过可以感性l理解
如果我们每次挑选的,都选择比较中间的,那么我们可以大致理解是的
直接上代码
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;
}
上一篇: IOC,DIP,DI,DI容器
下一篇: 值类型和引用类型在内存上的存储区域
推荐阅读
-
洛谷P2664 树上游戏(点分治)
-
洛谷:P1226 【模板】快速幂||取余运算(分治,数学)
-
三维偏序(陌上花开)---洛谷P3810&&BZOJ3262(cdq分治--归并排序+树状数组)
-
CDQ分治简介(洛谷P3810、BZOJ3262)
-
洛谷P3810 陌上花开(CDQ分治)
-
洛谷P3810(陌上花开)(三维偏序,cdq分治)
-
洛谷 - P3810 【模板】三维偏序(陌上花开)(CDQ分治套树状数组)
-
洛谷 P3810 【模板】三维偏序(陌上花开)【cdq 分治】【树状数组】
-
【题解】洛谷P3810【模板】三维偏序(陌上花开)cdq分治+树状数组
-
洛谷P3810 【模板】三维偏序(陌上花开)【CDQ分治、树套树】