1 solutions

  • 1
    @ 2026-3-28 23:08:55

    线段树好题。
    问题可以建模为区间加与区间求和,此时问题简化为在区间 [1,1][1,1] 加上一个数,再在区间 [2,2][2,2] 加上一个数,查询区间 [1,2][1,2] 的和。可以使用线段树维护区间加与区间求和操作。

    #include <bits/stdc++.h>
    using namespace std;
    
    const int N=1e5+5;
    int t[N<<2],tag[N<<2];
    inline int lc(int u){return u<<1;};
    inline int rc(int u){return u<<1|1;};
    inline void pushup(int u){t[u]=t[lc(u)]+t[rc(u)];}
    void pushdown(int u,int l,int r){
    	if(!tag[u]) return;
    	int mid=(l+r)>>1;
    	t[lc(u)]+=tag[u]*(mid-l+1);
    	t[rc(u)]+=tag[u]*(r-mid);
    	tag[lc(u)]+=tag[u];
    	tag[rc(u)]+=tag[u];
    	tag[u]=0;
    }
    void update(int u,int l,int r,int x,int y,int k){
    	if(r<x || l>y) return;
    	if(l>=x && r<=y){
    		t[u]+=k*(r-l+1);
    		tag[u]+=k;
    		return;
    	}
    	pushdown(u,l,r);
    	int mid=(l+r)>>1;
    	update(lc(u),l,mid,x,y,k);
    	update(rc(u),mid+1,r,x,y,k);
    	pushup(u);
    }
    int query(int u,int l,int r,int x,int y){
    	if(r<x || l>y) return 0;
    	if(l>=x && r<=y) return t[u];
    	pushdown(u,l,r);
    	int mid=(l+r)>>1;
    	return query(lc(u),l,mid,x,y)+query(rc(u),mid+1,r,x,y);
    }
    int super_fast_read(){
    	int x;
    	cin>>x;
    	return x;
    }
    void super_fast_write(int x,int k){
    	if(x==0){
    		if(k==1) cout<<0;
    		return;
    	}
    	super_fast_write(x/10,k+1);
    	if(k%3==0 && x/10!=0) cout<<',';
    	cout<<x%10;
    }
    int main(){
    	int a=super_fast_read();
    	int b=super_fast_read();
    	update(1,1,N-1,1,1,a);
    	update(1,1,N-1,1,1,b);
    	int ans=query(1,1,N-1,1,2);
    	super_fast_write(ans,1);
    	return 0;
    }
    
    
    • 1

    Information

    ID
    360
    Time
    1000ms
    Memory
    64MiB
    Difficulty
    10
    Tags
    # Submissions
    1
    Accepted
    1
    Uploaded By