但是那个可以卡，这个无法卡啊
1 个赞
找出来个类似的
#include<bits/stdc++.h>
#define ll long long
#define N 200005
using namespace std;
int n,lg[N];
int dp_a[N][25],dp_b[N][25];
ll ans=0;
int query_a(int l,int r){
int k=lg[r-l+1];
return min(dp_a[l][k],dp_a[r-(1<<k)+1][k]);
}
int query_b(int l,int r){
int k=lg[r-l+1];
return min(dp_b[l][k],dp_b[r-(1<<k)+1][k]);
}
vector<int> v;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d%d",&dp_a[i][0],&dp_b[i][0]);
v.push_back(i);
}
for(int i=2;i<=n;i++){
lg[i]=lg[i>>1]+1;
}
for(int i=1;i<21;i++){
for(int j=1;j+(1<<i)-1<=n;j++){
dp_a[j][i]=min(dp_a[j][i-1],dp_a[j+(1<<i-1)][i-1]);
dp_b[j][i]=min(dp_b[j][i-1],dp_b[j+(1<<i-1)][i-1]);
}
}
random_shuffle(v.begin(),v.end());
for(auto i:v){
for(ll j=i;j<=n;j++){
ll x=1ll*query_a(i,j)*query_b(i,j);
ans=max(ans,x*(j-i+1));
j=(ans/x)+i-1;
}
}
cout<<ans;
return 0;
}
@linan024
怎么，一起讨论的证明方法，老师教的，怎么就是抄袭了？
2 个赞
首先，我承认codeforces上面有随机化题目，错误率十分小。
但是和这个帖子的情况本质不同。这个是时间复杂度的问题不是正确性的问题。
1 个赞
本质肯定相同啊，WA和TLE不都是错吗。这两题中，WA 和 TLE 的概率都很小
2 个赞
如何证明非常小，出题人没考虑到的方面就非常小吗
这么说其实所有的hash题错误率都是100
任何的hash都是可以卡的，除非你的模数是值域，直接T飞/cf
那你总结一下，就是出题人的问题了？就是老师的问题了？
2 个赞
本人请你这个巨佬来估一估：），是你们在卡我们的题解
2 个赞
我所指的那题应该是 CF1305F，你可以去看题解里面有错误概率的具体计算。
那我讲的通俗一点：那你有本事卡啊。你卡不掉就不要叫，这么简单的道理不懂吗
1 个赞
不接受别人的 hack，你的眼睛容不下沙子？
题解代码明显不是随机化
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
typedef long long ll;
typedef unsigned un;
ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
return f*x;
}
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
void umin(ll& a,ll t){if(a>t)a=t;}
bool umax(ll& a,ll t){if(a<t)return a=t,1;return 0;}
#define MAXN 200011
ll a[MAXN],b[MAXN];
ll ans=0;
struct Line
{
ll k,b;
Line(ll _k=0,ll _b=0){k=_k,b=_b;}
ll f(int x){return k*x+b;}
};
struct Segment_Tree
{
std::vector<Line>v[MAXN<<2|1];
int it[MAXN<<2|1],len;
#define rtv v[num]
#define rtp it[num]
#define bk2 rtv[rtv.size()-2]
#define bk1 rtv[rtv.size()-1]
void build(ll* arr,un l,un r,un num)
{
rtv.clear();
for(int i=l;i<=r;++i)
{
Line cur(arr[i],-arr[i]*i);
while(rtv.size()>1&&double(bk1.b-bk2.b)*(cur.k-bk1.k)<=double(cur.b-bk1.b)*(bk1.k-bk2.k))rtv.pop_back();
if(rtv.empty()||bk1.k!=cur.k)rtv.push_back(cur);
rtp=0;
}
if(l==r)return;
un mid=(l+r)>>1;
build(arr,l,mid,num<<1),build(arr,mid+1,r,num<<1|1);
}
ll Query(un ql,un qr,int x,un l=1,un r=1,un num=1)
{
if(num==1)r=len;
if(ql<=l&&r<=qr)
{
while(rtp+1<rtv.size()&& (x+1)*(rtv[rtp+1].k-rtv[rtp].k) >=(-rtv[rtp+1].b+rtv[rtp].b))++rtp;
return rtv[rtp].f(x);
}
un mid=(l+r)>>1;ll res=0;
if(ql<=mid)umax(res,Query(ql,qr,x,l,mid,num<<1));
if(qr>mid)umax(res,Query(ql,qr,x,mid+1,r,num<<1|1));
return res;
}
void build(ll* arr,int n){len=n;build(arr,1,len,1);}
}TA,TB,TAB;
ll fa[MAXN],fb[MAXN],fab[MAXN];
void solve(int l,int r)
{
if(l==r){umax(ans,ll(a[l])*b[l]);return;}
un mid=(l+r)>>1,ls=mid-l+1;
fa[ls]=a[mid],fb[ls]=b[mid],fab[ls]=a[mid]*b[mid];
for(int i=mid-1;i>=l;--i)
fa[i-l+1]=min(a[i],fa[i-l+2]),fb[i-l+1]=min(b[i],fb[i-l+2]),
fab[i-l+1]=fa[i-l+1]*fb[i-l+1];
TA.build(fa,ls),TB.build(fb,ls),TAB.build(fab,ls);
ll ra=a[mid+1],rb=b[mid+1];
for(int i=mid+1;i<=r;++i)
{
umin(ra,a[i]),umin(rb,b[i]);
int posa=std::upper_bound(fa+1,fa+ls+1,ra)-fa-1;
int posb=std::upper_bound(fb+1,fb+ls+1,rb)-fb-1;
if(posa>0&&posb>0)umax(ans,TAB.Query(1,min(posa,posb),i-l+2));
++posb;
if(posb<=posa)umax(ans,TA.Query(posb,posa,i-l+2)*rb);
++posa,--posb;
if(posa<=posb)umax(ans,TB.Query(posa,posb,i-l+2)*ra);
++posb;
if(posa<=ls&&posb<=ls)umax(ans,(i-l+1-max(posa,posb)+1)*ra*rb);
}
solve(l,mid),solve(mid+1,r);
}
int main()
{
int n=read();
for(int i=1;i<=n;++i)a[i]=read(),b[i]=read();
solve(1,n);
printf("%lld\n",ans);
return 0;
}
不能卡就不要吵，不要叫，这一点做到有那么难吗？
2 个赞
但是“不通过概率小”之类的言论是你们说的。
看我的上个帖子，里面有一个类似的代码可以卡
有用随机化的题解。
1 个赞
不会证概率就不要吵，不要叫，这一点做到有那么难吗？