C 给出一个m 此时有 四个数 分别为x k*x k*k*x k*k*k*x k大于1 x大于等于1 要求求出来一个最小的值n 使其满足 这四个数中的最大值小于n 这四个数可能的组数为m
可以看出这四个数递增 所以最大值必定是第四个
所以我们二分n 需要注意的是longlong可以定义到1e18 初始应当是l小于等于可能的最小值(0) r大于等于可能的最大值(1e18) 如果初始范围就定义错误的话 二分不会出现正确答案
在这里由于控制l=mid+1或者r=mid-1 这一类的时候 容易丢失mid 造成一些麻烦 所以采用了一种看起来比较暴力的写法 当满足judge==m时直接break出来 然后while控制变小
因为如果满足过judge 就一定不是-1
需要注意的是避免i*i*i爆int 提前初始化省时间
时间复杂度是二分(最大64 )*1e6
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<math.h>
#include<queue>
using namespace std;
long long n,m;
long long a[1000050];
void init()
{
for(long long i=1;i<=1000000;i++)
{
a[i]=i*i*i;
}
}
long long judge(long long z)
{
long long res=0;
for(int i=2;i<=1000000;i++)
{
if(z/a[i]==0)
return res;
res+=(z/a[i]);
}
return res;
}
int main()
{
while(~scanf("%lld",&m))
{
init();
long long l=0;
long long r= 1e18+50000000;
long long mid;
while(l<=r)
{
mid=(l+r)>>1;
long long z=judge(mid);
if(z>m)
{
r=mid-1;
}
else if(z<m)
{
l=mid+1;
}
else break;
}
if(judge(mid)==m)
{
while(true)
{
mid--;
if(judge(mid)==m){
continue;
}
else {
printf("%lld\n",mid+1);
break;
}
}
}
else printf("-1\n");
}
}
D 给出两个数组 求出满足条件的l r组数 max第一组a[l-r] = min第二组b[l-r]
比赛的时候去掉了线段树莫队rmq 因为如果抽象询问的话 最后是n*(n+1)/2次询问 n是2e5 太大
也想到过二分 因为看起来应该采用nlogn的办法 然而因为二分需要满足稳定的递增 就排除了
赛后看题解..居然真的是二分+rmq 记得那场cf感觉奇难 AB打完一个小时就过去了 怎么可能想出来二分+数据结构这种神奇的办法
这个算法里面 rmq的预处理是nlogn的 查询是1的 二分的查询也是常数的 所以总体是nlogn的
http://blog.csdn.net/Miracle_ma/article/details/51860149 这道题的思想和rmq模板都来自于这个博客
每次我们枚举i 以i作为左区间枚举右区间 满足max-min=0
第一次我们得到的是 最左的不满足的 第二次得到的是 最右的满足的 相减就是i做左区间的右区间范围
需要注意的是ans可能爆int
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<queue>
#include<iostream>
#include<vector>
using namespace std;
int a[200050];
int b[200050];
int aa[200050][25];
int bb[200050][25];
int n;
void rmq_inita()
{
for(int i=0; i<n; i++) aa[i][0]=a[i];
for(int j=1; (1<<j)<=n; j++)
{
for(int i=0; i+(1<<j)-1<n; i++)
{
aa[i][j]=max(aa[i][j-1],aa[i+(1<<(j-1))][j-1]);
}
}
}
void rmq_initb()
{
for(int i=0; i<n; i++) bb[i][0]=b[i];
for(int j=1; (1<<j)<=n; j++)
{
for(int i=0; i+(1<<j)-1<n; i++)
{
bb[i][j]=min(bb[i][j-1],bb[i+(1<<(j-1))][j-1]);
}
}
}
int rmqa(int L,int R)
{
int k=0;
while((1<<(k+1))<=R-L+1) k++;
return max(aa[L][k],aa[R-(1<<k)+1][k]);
}
int rmqb(int L,int R)
{
int k=0;
while((1<<(k+1))<=R-L+1) k++;
return min(bb[L][k],bb[R-(1<<k)+1][k]);
}
int main()
{
while(cin>>n)
{
for(int i = 0; i<n; i++)cin>>a[i];
for(int i = 0; i<n; i++)cin>>b[i];
rmq_inita();
rmq_initb();
long long int ans= 0;
for(int i=0; i<n; i++)
{
long long int res=0;
int l = i;
int r = n-1;
while(l<=r)
{
int mid = (l + r)>>1;
if(rmqa(i,mid)-rmqb(i,mid)<0)
{
l = mid + 1;
}
else r = mid - 1;
}
res= l;
l = i;
r = n-1;
while(l<=r)
{
int mid = (l + r)>>1;
if(rmqa(i,mid)-rmqb(i,mid)>0)
{
r = mid - 1;
}
else l = mid + 1;
}
ans += l-res;
}
printf("%lld\n",ans);
}
}