796. 子矩陣的和（二維前綴和）-有解無憂

輸入一個n行m列的整數矩陣，再輸入q個詢問，每個詢問包含四個整數x1, y1, x2, y2，表示一個子矩陣的左上角坐標和右下角坐標，

對于每個詢問輸出子矩陣中所有數的和，

輸入格式

第一行包含三個整數n，m，q，

接下來n行，每行包含m個整數，表示整數矩陣，

接下來q行，每行包含四個整數x1, y1, x2, y2，表示一組詢問，

輸出格式

共q行，每行輸出一個詢問的結果，

資料范圍

$1 \leq n, m \leq 1000$

輸入樣例：

輸出樣例：

17
27
21

注意下java的快速輸入輸出，否則超時

代碼：

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main {
    static class FastScanner{//用于快速讀入大量資料
        BufferedReader br;
        StringTokenizer st;
        public FastScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in),16384);
            eat("");
        }
        public void eat(String s) {
            st = new StringTokenizer(s);
        }
        public String nextLine() {
            try {
                return br.readLine();
            } catch (IOException e) {
                return null;
            }
        }
        public boolean hasNext() {
            while(!st.hasMoreTokens()) {
                String s = nextLine();
                if(s==null) return false;
                eat(s);
            }
            return true;
        }
        public String next() {
            hasNext();
            return st.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }
    }
      static FastScanner scan = new FastScanner(System.in);//快讀
      static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));//快速輸出


      static final int max=1005;
      static int a[][]=new int[max][max];
      static int s[][]=new int[max][max];
      public static void main(String[] args) {
            int n=scan.nextInt();
            int m=scan.nextInt();
            int c=scan.nextInt();
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                    a[i][j]=scan.nextInt();
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                   s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];//求前綴和
            while(c-->0){
                   int x1=scan.nextInt();
                   int y1=scan.nextInt();
                   int x2=scan.nextInt();
                   int y2=scan.nextInt();
                   out.println(s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);//求子矩陣的和
            }
            out.flush();
    }


}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/107634.html

標籤：其他

上一篇：Java輸入輸出掛

下一篇：795. 前綴和（一維前綴和）