3189. 求和

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Interval
{
int L;
int U;
};

uint64_t add_interval(const vector<int> &vec, int begin, int end)
{
uint64_t sum = 0;
for (int i = begin; i <= end; ++i)
sum += vec[i];
return sum;
}

int main()
{
int T;
cin >> T;
for (int z = 0; z < T; ++z)
{
int n, m;
cin >> n >> m;
vector<int> vec(n);
for (auto &i : vec)
cin >> i;
vector<Interval> ivec(m);
for (auto &i : ivec)
cin >> i.L >> i.U;
vector<int> count;
for (int i = 0; i + add_incr < vec.size(); ++i)
sort(count.begin(), count.end());
cout << "case #" << z << ":" << endl;
for (const auto &i : ivec)
cout << add_interval(count, i.L - 1, i.U - 1) << endl;
}
return 0;
}


#include "bits/stdc++.h"

using namespace std;
using u64 = uint64_t;

int main() {
u64 t;
cin >> t;
for (u64 query = 0; query < t; ++query) {
cout << "case #" << query << ":\n";
u64 n, m;
cin >> n >> m;
vector<u64> orig_arr(n);
for (auto &i : orig_arr) {
cin >> i;
}
vector<u64> orig_pre_sum(n + 1);
orig_pre_sum[0] = 0;
partial_sum(begin(orig_arr), end(orig_arr), next(begin(orig_pre_sum)));
vector<u64> new_arr;
new_arr.reserve(n * (n + 1) / 2);
for (u64 i = 0; i < n; ++i) {
for (u64 j = i + 1; j <= n; ++j) {
new_arr.push_back(orig_pre_sum[j] - orig_pre_sum[i]);
}
}
sort(new_arr.begin(), new_arr.end());
vector<u64> new_pre_sum(new_arr.size() + 1);
new_pre_sum[0] = 0;
partial_sum(begin(new_arr), end(new_arr), next(begin(new_pre_sum)));
for (u64 i = 0; i < m; ++i) {
u64 lo, hi;
cin >> lo >> hi;
cout << new_pre_sum[hi] - new_pre_sum[lo - 1] << '\n';
}
}
}


include

int cmp(const voida,const voidb)
{
return (int)a-(int)b;
}
void slove(inta,ints,int n)
{
int i,j=0,k;
for(i=0;i<n;i++)
{
s[j]=a[i],j++;
for(k=i+1;k<n;k++)
{
s[j]=s[j-1]+a[k];
j++;
}
}
qsort(s,j,sizeof(s[0]),cmp);
// for(i=0;i<j;i++)printf(“%d “,s[i]);printf(“\n”);
}
int main()
{
int t,cas;
int m,n,i,a[1001],l[32],u[32],s[500501];
int sum,j;
scanf(“%d”,&cas);
for(t=0;t<cas;t++)
{
scanf(“%d%d”,&n,&m);
for(i=0;i<n;i++)
{
scanf(“%d”,&a[i]);
}
for(i=0;i<m;i++)
{
scanf(“%d%d”,&l[i],&u[i]);
}
printf(“case #%d:\n”,t);
slove(a,s,n);
for(i=0;i<m;i++)
{
sum=0;
for(j=l[i]-1;j<u[i];j++)
sum+=s[j];
printf(“%d\n”,sum);
}
}
return 0;
}