Loading [MathJax]/jax/output/CommonHTML/jax.js
Solutions of Subarray sum - MarisaOJ: Marisa Online Judge

Solutions of Subarray sum

Select solution language

Write solution here.


User Avatar Temrater    Created at    14 likes

## **Ý TƯỞNG:** Kích thước n <= 1e5, vì thế bạn không thể dùng vòng for lồng(1e5 x (1e5 - 1)) để duyệt. Ở bài này ta sử dụng kiến thức về **prefix_sum** và **map**. ### **Thành Phần:** **- prefix[]**: Mảng cộng dồn các phần tử từ i = 1 đến i = n. **- map[]**: Lưu số lần xuất hiện của prefix[i]. ### **Giải Thích:** Cần lưu ý như sau: A+B=C <=> B=CA Nghĩa là tổng hoặc hiệu của 2 số (A,B) chỉ có thể suy ra duy nhất 1 đáp án là C. Do vậy lưu **prefix_sum** của mảng ban đầu, duyệt lại mảng **prefix_sum** 1 lần nữa và ***trong khi duyệt***: với mỗi vị trí prefix[i] đếm xem có bao nhiêu số có giá trị là prefix[i]-x (x là số đề bài cho). mp[prefix[i]-x] là số lượng số có giá trị prefix[i]-x, chính những số lượng số có giá trị prefix[i]-x này là các đoạn con liên tiếp mà tổng của đoạn con tại vị trí prefix[i] = x *(prefix[i] - (prefix[i]-x) = x)*. Cần lưu ý **trường hợp đặc biệt** rằng có thể x = 0, prefix[i] = 0. cpp#clude<bitsstdc++.h>usingnamespacestd;#defelonglongn,x,ans;prefix[100005];map<,>mp;sigdma(){cnx;for(i=1;in;i++){tempo;ctempo;prefix[i]=prefix[i-1]+tempo;mp[prefix[i]]++;ans+=mp[prefix[i]-x];if(prefix[i]==x&&prefix[i]-xprefix[i])ans++;/Truonghopx=0,prefix[i]=0}coutans;}/FrommemberofTrnBiênHighshl