java求调，第二个AC，最后三个MLE，其他WA

P3372 【模板】线段树 1

190859136kkkk @ 2024-03-25 17:11:38

import java.util.ArrayList;
import java.util.Scanner;

class node{
    int sum,l,r,add;
}

public class SegmentTree {
    static void build(int p,int l,int r,ArrayList<node> a,int[] b) {
        a.get(p).l=l;  a.get(p).r=r;  a.get(p).add=0;  a.get(p).sum=b[l];
        if(a.get(p).l==a.get(p).r)  
            return;
        int m = (l+r)>>1;
        build(p<<1,l,m,a,b);
        build(p<<1|1,m+1,r,a,b);
        pushup(p,a);
    }

    static void update(int x,int y,int n,int p,ArrayList<node> a) { 
        if(x<=a.get(p).l&&y>=a.get(p).r) {
            a.get(p).sum+=(a.get(p).r-a.get(p).l+1)*n;
            a.get(p).add+=n;
            return;
        }
        int m=(a.get(p).l+a.get(p).r)>>1;
        pushdown(p,a);
        if(x<=m) update(x,y,n,p<<1,a);
        if(y>m) update(x,y,n,p<<1|1,a);
        pushup(p,a);
    }

    static void pushup(int p,ArrayList<node> a) {
        a.get(p).sum=a.get(p<<1).sum+a.get(p<<1|1).sum;
    }

    static void pushdown(int p,ArrayList<node> a) {
        if(a.get(p).add!=0) {
            a.get(p<<1).sum+=(a.get(p<<1).r-a.get(p<<1).l+1)*a.get(p).add;
            a.get(p<<1|1).sum+=(a.get(p<<1|1).r-a.get(p<<1|1).l+1)*a.get(p).add;
            a.get(p<<1).add+=a.get(p).add;
            a.get(p<<1|1).add+=a.get(p).add;
            a.get(p).add=0;
        }
    }

    static long query(int p,int x,int y,ArrayList<node> a) {
        if(x<=a.get(p).l&&y>=a.get(p).r) {
            return a.get(p).sum;
        }
        int m =(a.get(p).l+a.get(p).r)>>1;
        int sum =0;
        pushdown(p,a);
        if(x<=m) sum+=query(p<<1,x,m,a);
        if(y>m) sum+=query(p<<1|1,m+1,y,a);
        return sum;
    }

    public static void main(String[] args) {
        Scanner in =new Scanner(System.in);
        int n =in.nextInt();
        int m =in.nextInt();
        int[] num =new int[n+1];
        ArrayList<node> a =new ArrayList<>();
        for(int i=1;i<n+1;i++) {
            num[i]=in.nextInt();
        }
        for(int i=0;i<4*n+1;i++) {
            node no =new node();
            a.add(no);
        }
        build(1,1,n,a,num);
        for(int i=0;i<m;i++) {
            int op =in.nextInt();
            if(op==1) {
                int x= in.nextInt(),y=in.nextInt(),k=in.nextInt();
                update(x,y,k,1,a);
            }
            else if(op==2) {
                int x=in.nextInt();
                int y=in.nextInt();
                System.out.println(query(1,x,y,a)); 
                }
        }
    }

}

by 190859136kkkk @ 2024-03-25 17:44:05

只剩下最后三个MLE了。我在网上找了一些快读的模板，多次尝试无果，求助。（其中一个模板让我通过了另一题的MLE，这次不管用了，是否是别的原因导致MLE？）

之前的错误是：

if(x<=m) sum+=query(p<<1,x,m,a);
        if(y>m) sum+=query(p<<1|1,m+1,y,a);

应当改为

if(x<=m) sum+=query(p<<1,x,y,a);
        if(y>m) sum+=query(p<<1|1,x,y,a);

by running__coder @ 2024-04-07 21:27:51

我的瓶颈在Scanner，我把输入改成这个就能过了，输出可以不改。

    static class Reader {
        static BufferedReader reader;
        static StringTokenizer tokenizer;

        /** 调用这个方法来初始化reader，即InputStream*/
        static void init(InputStream input) {
            reader = new BufferedReader(new InputStreamReader(input));
            tokenizer = new StringTokenizer("");
        }

        /** 获取下一段文本 */
        static String next() throws IOException {
            while ( ! tokenizer.hasMoreTokens() ) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return tokenizer.nextToken();
        }

        static int nextInt() throws IOException {
            return Integer.parseInt( next() );
        }

        static double nextDouble() throws IOException {
            return Double.parseDouble( next() );
        }
    }

你这里我看用到了ArrayList，但ArrayList在空间不足时是会按照1.5倍动态扩容的，那么你这个ArrayList实际申请的空间可能是超过你这个4n的，可能也是导致MLE的因素。