记录编号	364831	评测结果	AAAAAAAAAA
题目名称	求和问题	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.377 s
提交时间	2017-01-18 10:38:58	内存使用	5.31 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
using namespace std;
namespace IO
{
    char buf[1<<16], *fs, *ft;
    inline char readc()
    {
        return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<16,stdin), fs==ft))?0:*fs++;
    }
    inline int fast_read()
    {
        char c = readc();
        int r = 0;
        bool sig = false;
        while(c > '9' || c < '0')
        {
            if(c == '-')sig = true;
            c = readc();
        }
        while(c >= '0' && c <= '9')
        {
            r = (r<<3)+(r<<1)+(c^0x30);
            c = readc();
        }
        return sig?-r:r;
    }
}using IO::fast_read;using IO::readc;
#define MAXN 100001
int a[MAXN];
struct que
{
    int l, r;
    int bk;
    long long ans;
    bool operator<(const que &q) const
    {
        return bk < q.bk || (bk == q.bk && r < q.r);
    }
}qs[200001];
int rank[200001];
bool cmp(int a, int b)
{
    return qs[a] < qs[b];
}
int main()
{
    freopen("sum.in", "r", stdin);
    freopen("sum.out", "w", stdout);
    int n = fast_read();
    int magic = (int)sqrt(n);
    for(int i = 1; i <= n; i++)a[i] = fast_read();
    int m = fast_read();
    for(int i = 0; i < m; i++)
    {
        que &q = qs[i];
        q.l = fast_read();
        q.r = fast_read();
        q.bk = q.l/magic;
        rank[i] = i;
    }
    sort(rank, rank+m);
    long long ans = a[1];
    int l = 1, r = 1;
    for(int i = 0; i < m; i++)
    {
        que &q = qs[rank[i]];
        while(l < q.l)ans -= a[l++];
        while(r < q.r)ans += a[++r];
        while(l > q.l)ans += a[--l];
        while(r > q.r)ans -= a[r--];
        q.ans = ans;
    }
    for(int i = 0; i < m; i++)printf("%lld\n", qs[i].ans);
    return 0;
}