145 条题解

  • -35
    @ 2021-8-8 16:35:12

    用线段树+标记永久化即可

    #include <cstdio>
    #define mid L + (R-L >> 1)
    const int maxn = 1e5+5;
    
    int n, a[maxn], m;
    int sl, sr, add;
    
    struct segtree{
    	int sum[maxn<<2], tag[maxn<<2];
    	inline int lc(int o){return o<<1;}
    	inline int rc(int o){return o<<1|1;}
    	void build(int o, int L, int R){
    		if(L == R){sum[o] = a[L];return;}
    		int M = mid;
    		build(lc(o), L, M);
    		build(rc(o), M+1, R);
    		sum[o] = sum[lc(o)] + sum[rc(o)];
    	}
    	void maintain(int o, int L, int R){
    		if(R>L){
    			sum[o] = sum[lc(o)] + sum[rc(o)];
    			sum[o] += tag[o] * (R-L+1);
    		} else {
    			sum[o] += tag[o];
    			tag[o] = 0;
    		}
    	}
    	void updata(int o, int L, int R){
    		if(sl <= L && R <= sr)tag[o] += add;
    		else{
    			int M = mid;
    			if(sl <= M)updata(lc(o), L, M);
    			if(sr > M)updata(rc(o), M+1, R);
    		}
    		maintain(o, L, R);
    	}
    	int query(int o, int L, int R, int tags){
    		if(sl <= L && R <= sr)return sum[o] + tags * (R-L+1);
    		else {
    			int M = mid, res = 0;
    			if(sl <= M)res += query(lc(o), L, M, tags+tag[o]);
    			if(sr > M)res += query(rc(o), M+1, R, tags+tag[o]);
    			return res;
    		}
    	}
    } sol;
    
    signed main(){
    	n = 1; 
    	int a, b; 
    	scanf("%d%d", &a, &b);
    	sol.build(1, 1, n);
    	add=a; sl=1; sr=1;
    	sol.updata(1, 1, 1);
    	add=b;
    	sol.updata(1, 1, 1);
    	printf("%d\n", sol.query(1, 1, n, 0));
    	return 0;
    }
    

    当然,树状数组也可以,并且更快

    #include <iostream>
    using namespace std;
    const int n = 1;
    int a, b;
    int c[500005];
    inline int lowbit(int x){
    	return x & (-x);
    }
    inline int sum(int x){
    	int ans=0;
    	for(int i=x;i>0;i-=lowbit(i))
    	ans+=c[i];
    	return ans;
    }
    void add(int x,int y){
    	for(int i=x;i<=n;i+=lowbit(i))
    	c[i]+=y;
    }
    int main(){
    	cin>>a>>b;
    	add(1, a); add(1, b);
    	printf("%d\n", sum(1));
    	return 0;
    }
    
    • @ 2022-7-25 16:33:55

      咕咕咕

    • @ 2022-7-25 16:34:54

      装摸做样的建了棵树……

信息

ID
56
时间
1000ms
内存
1024MiB
难度
1
标签
递交数
9073
已通过
4043
上传者