第十九届同济大学程序设计竞赛 G-归零(前缀和版)
输入：
6 31 1 4 5 1 43 5 101 4 111 4 6输出：
10115
AC代码：(前缀和优化版本)
#includeusing namespace std;typedef long long ll;ll n,l,r,k,t,i,mx,ans,sum[200005];int a[200005];int main(){ scanf("%lld %lld",&n,&t); for(i=1;i<=n;i++){ scanf("%lld",&a[i]); sum[i] = sum[i-1] + a[i];//数组A的前缀和 if (mx < a[i])//求Ai的最大值 mx = a[i]; } while(t--){ scanf("%lld%lld%lld",&l,&r,&k); if (mx * 2 <= k)//当数组A中的数都比较小时，此时全部进行操作2，使用前缀和，复杂度为2*10^5 ans = sum[r] - sum[l-1]; else//当数组中的数有比较大的时候，此时只能一个个数去算，复杂度为 2*10^5*2*10^5=4*10^10 {//虽然 4*10^10肯定会超时，但测试样例有很多都是数比较小的，不会进行到这一步，所以可以凑巧AC ans = 0; for(i = l; i <= r; i++){ if(a[i]<= k -a[i]) ans += a[i]; else ans += (k - a[i]); } } printf("%lld\n",ans); } return 0;}如果该题的数据没有那么仁慈的话，那么简单的前缀和优化也AC不了了，最保底的做法应该是用主席树(前缀和+权值线段树)不过我现在还不会呜呜...