求调
查看原帖
求调
1415157
Samine_楼主2024/12/6 20:52

C++开1e6+5能过,Java开1e6+5RE。

有没有大佬帮忙调下qwq

import java.util.*;
import java.io.*;
import java.text.*;

public class Main {
    static long[] d = new long[500005] , a = new long[500005] , b = new long[500005];
    public static void Create(long l,long r,int p) {
        if(l == r) {
            d[p] = a[(int)l];
            return ;
        }
        long mid = l + ((r-l)>>1);
        Create(l,mid,2*p);
        Create(mid+1,r,2*p+1);
        d[p] = d[2*p] + d[2*p+1];
    }
    public static long Getsum(long l,long r,long s,long t,int p) {
        if(l <= s && r >= t) {
            return d[p];
        }
        long mid = s + ((t-s)>>1) , sum = 0;
        if(b[p] != 0 && s != t) {
            d[2*p] += (mid-s+1) * b[p] ; d[2*p+1] += (t-mid) * b[p];
            b[2*p] += b[p] ; b[2*p+1] += b[p];
            b[p] = 0;
        }
        if(l <= mid) sum += Getsum(l,r,s,mid,2*p);
        if(r > mid) sum += Getsum(l,r,mid+1,t,2*p+1);
        return sum;
    }
    public static void Update(long l,long r,long c,long s,long t,int p) {
        if(l <= s && r >= t) {
            d[p] += (t-s+1) * c;
            b[p] += c;
            return ;
        }
        long mid = s + ((t-s)>>1) ;
        if(b[p] != 0 && s != t) {
            d[2*p] += (mid-s+1) * b[p] ; d[2*p+1] += (t-mid) * b[p];
            b[2*p] += b[p] ; b[2*p+1] += b[p];
            b[p] = 0;
        }
        if(l <= mid) Update(l,r,c,s,mid,2*p);
        if(r > mid) Update(l,r,c,mid+1,t,2*p+1);
        d[p] = d[2*p] + d[2*p+1];
        return ;
    }
    public static void main(String args[]) throws Exception {
        Scanner cin = new Scanner(System.in);
        long n = cin.nextLong() , m = cin.nextLong() , op , l , r , k;
        for(int i = 1; i <= n ; i ++) {
            a[i] = cin.nextLong();
        }
        Create(1,n,1);
        for(long i = 1 ; i <= m ; i ++) {
            op = cin.nextLong() ; l = cin.nextLong() ; r = cin.nextLong() ;
            if(op == 1) {
                k = cin.nextLong();
                Update(l,r,k,1,n,1);
            }
            if(op == 2) {
                System.out.println(Getsum(l,r,1,n,1));
            }
        }
    }
}

C++ AC Code

#include <iostream>
using namespace std;
const int maxn = 1e6+5;
#define int long long
int a[maxn],b[maxn],d[maxn];
void Create(int l,int r,int p) {
	if(l == r) {
		d[p] = a[l];
		return ;
	}
	int mid = l + ((r-l)>>1);
	Create(l,mid,2*p);
	Create(mid+1,r,2*p+1);
	d[p] = d[2*p] + d[2*p+1];
}
int Getsum(int l,int r,int s,int t,int p) {
	if(l <= s && r >= t) {
		return d[p];
	}
	int mid = s + ((t-s)>>1) , sum = 0;
	if(b[p] && s != t) {
		d[2*p] += (mid-s+1) * b[p] , d[2*p+1] += (t-mid) * b[p];
		b[2*p] += b[p] , b[2*p+1] += b[p];
		b[p] = 0;
	}
	if(l <= mid) sum += Getsum(l,r,s,mid,2*p);
	if(r > mid) sum += Getsum(l,r,mid+1,t,2*p+1);
	return sum;
}
void Update(int l,int r,int c,int s,int t,int p) {
	if(l <= s && r >= t) {
		d[p] += (t-s+1) * c;
		b[p] += c;
		return ;
	}
	int mid = s + ((t-s)>>1) ;
	if(b[p] && s != t) {
		d[2*p] += (mid-s+1) * b[p] , d[2*p+1] += (t-mid) * b[p];
		b[2*p] += b[p] , b[2*p+1] += b[p];
		b[p] = 0;
	}
	if(l <= mid) Update(l,r,c,s,mid,2*p);
	if(r > mid) Update(l,r,c,mid+1,t,2*p+1);
	d[p] = d[2*p] + d[2*p+1];
}
signed main() {
	int n,m,op,l,r,k;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	Create(1,n,1);
	for(int i=1;i<=m;i++) {
		cin>>op>>l>>r;
		if(op == 1) {
			cin>>k;
			Update(l,r,k,1,n,1);
		}
		if(op == 2) cout<<Getsum(l,r,1,n,1)<<endl;
	}
	return 0;
}
2024/12/6 20:52
加载中...