5 条题解

  • 3
    @ 2025-10-7 13:01:14

    一道线段树入门题。上代码:

    namespace solver11
    {
    	struct SegTree
    	{
    		int l,r;
    		long long val,tag;
    	}t[50];
    	
    	inline void Push_Up(int id)
    	{
    		t[id].val=t[id<<1].val+t[id<<1|1].val;
    	}
    	
    	inline void Push_Down(int id)
    	{
    		if (t[id].tag)
    		{
    			int mid=(t[id].l+t[id].r)>>1;
    			t[id<<1].tag+=t[id].tag;
    			t[id<<1|1].tag+=t[id].tag;
    			t[id<<1].val+=(mid-t[id].l+1)*t[id].tag;
    			t[id<<1|1].val+=(t[id].r-mid)*t[id].tag;
    			t[id].tag=0;
    		}
    	}
    	
    	inline void Build(int id,int l,int r)
    	{
    		t[id].l=l;
    		t[id].r=r;
    		if (l==r)
    			return;
    		int mid=(l+r)>>1;
    		Build(id<<1,l,mid);
    		Build(id<<1|1,mid+1,r);
    		Push_Up(id);
    	}
    	
    	inline void Change(int id,int l,int r,int val)
    	{
    		if (l<=t[id].l && t[id].r<=r)
    		{
    			t[id].tag+=val;
    			t[id].val+=val*(t[id].r-t[id].l+1);
    			return;
    		}
    		Push_Down(id);
    		int mid=(t[id].l+t[id].r)>>1;
    		if (r<=mid)
    			Change(id<<1,l,r,val);
    		else if (l>mid)
    			Change(id<<1|1,l,r,val);
    		else
    		{
    			Change(id<<1,l,mid,val);
    			Change(id<<1|1,mid+1,r,val);
    		}
    		Push_Up(id);
    	}
    	
    	inline long long Query(int id,int l,int r)
    	{
    		if (l<=t[id].l && t[id].r<=r)
    			return t[id].val;
    		Push_Down(id);
    		int mid=(t[id].l+t[id].r)>>1;
    		if (r<=mid)
    			return Query(id<<1,l,r);
    		else if (l>mid)
    			return Query(id<<1|1,l,r);
    		else
    			return Query(id<<1,l,mid)+Query(id<<1|1,mid+1,r);
    	}
    	
    	inline void solve()
    	{
    		Build(1,1,2);
    		Change(1,1,1,read());
    		Change(1,2,2,read());
    		cout << Query(1,1,2) << endl;
    	}
    }
    
    

    信息

    ID
    550
    时间
    1000ms
    内存
    256MiB
    难度
    1
    标签
    (无)
    递交数
    911
    已通过
    602
    上传者