社区讨论

为什么这两篇代码常数差很多

ddream_on_screen
P2824[HEOI2016/TJOI2016] 排序参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mjcxnqh7
此快照首次捕获于
2025/12/19 21:56
2 个月前
此快照最后确认于
2025/12/21 15:30
2 个月前
查看原帖
第一篇代码CPP
#include <iostream>
using namespace std;
int n,m,q;
int a[100005];
struct node
{
    int l,r,sum,lazy;
};
node t[400005];
int b[100005];
void build(int id,int l,int r)
{
    if(l==r)
        t[id].sum=b[l];
    else
    {
        int mid=l+r>>1;
        build(id*2,l,mid);
        build(id*2+1,mid+1,r);
        t[id].sum=t[id*2].sum+t[id*2+1].sum;
    }
    t[id].l=l;
    t[id].r=r;
    t[id].lazy=-1;
}
void pushup(int id)
{
    if(t[id].lazy!=-1)
    {
        t[id].sum=t[id].lazy*(t[id].r-t[id].l+1);
        if(t[id].l!=t[id].r)
            t[id*2].lazy=t[id*2+1].lazy=t[id].lazy;
        t[id].lazy=-1;
    }
}
void cover(int id,int l,int r,int k)
{
	if(r<l)
		return ;
    if(t[id].l==l&&t[id].r==r)
    {
        t[id].lazy=k;
        pushup(id);
        return ;
    }
    pushup(id);
    int mid=t[id].l+t[id].r>>1;
    if(r<=mid)
        cover(id*2,l,r,k);
    else if(l>mid)
        cover(id*2+1,l,r,k);
    else
        cover(id*2,l,mid,k),cover(id*2+1,mid+1,r,k);
    pushup(id*2);
    pushup(id*2+1);
    t[id].sum=t[id*2].sum+t[id*2+1].sum;
}
int query(int id,int l,int r)
{
	if(r<l)
		return 0;
    pushup(id);
    if(t[id].l==l&&t[id].r==r)
        return t[id].sum;
    int mid=(t[id].l+t[id].r)/2;
    if(r<=mid)
        return query(id*2,l,r);
    else if(mid<l)
        return query(id*2+1,l,r);
    return query(id*2,l,mid)+query(id*2+1,mid+1,r);
}
struct node_
{
    int op,l,r;
};
node_ op[100005];
bool check(int limit)
{
    for(int i=1;i<=n;i++)
        if(a[i]>=limit)
            b[i]=1;
        else
            b[i]=0;
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int p=query(1,op[i].l,op[i].r);
        int q=op[i].r-op[i].l+1-p;
        if(op[i].op==0)
        {
            cover(1,op[i].l,op[i].l+q-1,0);
            cover(1,op[i].r-p+1,op[i].r,1);
        }
        else
        {
            cover(1,op[i].l,op[i].l+p-1,1);
            cover(1,op[i].r-q+1,op[i].r,0);
        }
    }
    return query(1,q,q)==1;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++)
        cin>>op[i].op>>op[i].l>>op[i].r;
    cin>>q;
    int l=0x3f3f3f3f,r=-0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
    	if(a[i]<l)
    		l=a[i];
    	if(a[i]>r)
    		r=a[i];
	}
    while(l!=r)
    {
        int mid=(l+r+1)/2;
        if(check(mid))
            l=mid;
        else
            r=mid-1;
    }
    cout<<l;
    return 0;
}
第二篇代码CPP
#include <iostream>
using namespace std;
int n,m,q;
int a[100005],b[100005];
int op[100005],l[100005],r[100005];
int t[400005],lazy[400005];
void build(int id,int l,int r)
{
    lazy[id]=-0x3f3f3f3f;
    if(l==r)
        t[id]=b[l];
    else
    {
        int mid=(l+r)>>1;
        build(id<<1,l,mid);
        build(id<<1|1,mid+1,r);
        t[id]=t[id<<1]+t[id<<1|1];
    }
}
void tag(int id,int l,int r,int lz)
{
    t[id]=(r-l+1)*lz;
    lazy[id]=lz;
}
void pushdown(int id,int l,int r)
{
    if(lazy[id]!=-0x3f3f3f3f&&l!=r)
    {
        int mid=(l+r)>>1;
        tag(id<<1,l,mid,lazy[id]);
        tag(id<<1|1,mid+1,r,lazy[id]);
    }
    lazy[id]=-0x3f3f3f3f;
}
int query(int id,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)
        return t[id];
    pushdown(id,l,r);
    int mid=(l+r)>>1;
    int ans=0;
    if(L<=mid)
    	ans+=query(id<<1,l,mid,L,R);
	if(R>mid)
		ans+=query(id<<1|1,mid+1,r,L,R);
	return ans; 
}
void change(int id,int l,int r,int L,int R,int d)
{
	if(L>r||l>R) return ;
    if(L<=l&&r<=R)
    {
        tag(id,l,r,d);
        return ;
    }
    pushdown(id,l,r);
    int mid=(l+r)>>1;
    if(L<=mid)
		change(id<<1,l,mid,L,R,d);
	if(R>mid)
		change(id<<1|1,mid+1,r,L,R,d);
    t[id]=t[id<<1]+t[id<<1|1];
}
bool check(int limit)
{
    for(int i=1;i<=n;i++)
        b[i]=a[i]>=limit;
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int k=r[i]-l[i]+1-query(1,1,n,l[i],r[i]);
        if(op[i]==0)
            change(1,1,n,l[i],l[i]+k-1,0),change(1,1,n,l[i]+k,r[i],1);
        else
            change(1,1,n,l[i],l[i]+(r[i]-l[i]+1-k)-1,1),change(1,1,n,l[i]+(r[i]-l[i]+1-k),r[i],0);
    }
    if(query(1,1,n,q,q)==1)
        return true;
    return false;
}
int main()
{
    cin>>n>>m;
    int mn=-0x3f3f3f3f,mx=0x3f3f3f3f;
    for(int i=1;i<=n;i++)
        cin>>a[i],mn=min(mn,a[i]),mx=max(mx,a[i]);
    for(int i=1;i<=m;i++)
        cin>>op[i]>>l[i]>>r[i];
    cin>>q;
    int l=mn,r=mx;
    while(l!=r)
    {
        int mid=(l+r+1)>>1;
        if(check(mid))
            l=mid;
        else
            r=mid-1;
    }
    cout<<r;
    return 0;
}
第一篇代码是暑假写的，第二篇代码是今天写的。
第一篇代码只跑了 6 秒多，第二篇代码跑了 10 秒，但是我完全不知道是什么东西导致常数大了这么多。

回复

共 2 条回复，欢迎继续交流。

正在加载回复...