线段树可爱awa!!!

#include<bits/stdc++.h>
#define ls id<<1
#define rs id<<1|1
#define int long long
using namespace std;

const int N=1e5+10;
int n,m,a[N];
struct SegmentTree{
	int l,r,sum,lazy;
}tr[N<<2];

void Push_up(int id)
{
	tr[id].sum=tr[ls].sum+tr[rs].sum;
}

void Push_down(int id)
{
	tr[ls].sum+=(tr[ls].r-tr[ls].l+1)*tr[id].lazy;
	tr[rs].sum+=(tr[rs].r-tr[rs].l+1)*tr[id].lazy;
	
	tr[ls].lazy+=tr[id].lazy;
	tr[rs].lazy+=tr[id].lazy;
	
	tr[id].lazy=0;
}

void Build(int id,int l,int r)
{
	tr[id].l=l;tr[id].r=r;tr[id].lazy=0;
	if(l>=r)
	{
		tr[id].sum=a[l];
		return;
	}
	int mid=(l+r)>>1;
	Build(ls,l,mid);
	Build(rs,mid+1,r);
	Push_up(id);
}

void Add(int id,int l,int r,int k)
{
	if(tr[id].l>r || tr[id].r<l)return;
	if(tr[id].l>=l && tr[id].r<=r)
	{
		tr[id].sum+=(tr[id].r-tr[id].l+1)*k;
		tr[id].lazy+=k;
		return;
	}
	Push_down(id);
	Add(ls,l,r,k);
	Add(rs,l,r,k);
	Push_up(id);
}

int Calc(int id,int l,int r)
{
	if(tr[id].l>r || tr[id].r<l)return 0;
	if(tr[id].l>=l && tr[id].r<=r)return tr[id].sum;
	Push_down(id);
	return Calc(ls,l,r)+Calc(rs,l,r);
}

signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld",&a[i]);
	}
	Build(1,1,n);
	while(m--)
	{
		char opt;int a,b,c;
		cin>>opt;
		if(opt=='C')
		{
			scanf("%lld%lld%lld",&a,&b,&c);
			Add(1,a,b,c);
		}
		else if(opt=='Q')
		{
			scanf("%lld%lld",&a,&b);
			printf("%lld\n",Calc(1,a,b));
		}
	}
	return 0;
}

一个“简单”的整数问题

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>

using namespace std;
//#define int long long
//#define map unordered_map
typedef long long ll;
const int N = 1e5 + 10, M = 350;
int n, m;
int a[N];
ll sum[M], add[M];
int len;

int get(int i)
{
    return i / len;
}

ll ask(int l, int r)
{
    ll res = 0;
    int L = get(l), R = get(r);
    if (L == R)
    {
        for (int i = l; i <= r; ++i)
        {
            int I = get(i);
            res += (a[i] + add[I]);
        }
    }
    else
    {
        int i = l, j = r, I, J;
        while ((I = get(i)) == L) {
            res += (a[i] + add[I]), ++i;
        }
        while ((J = get(j)) == R) {
            res += (a[j] + add[J]), --j;
        }
        for (int k = I; k <= J; ++k) {
            res += sum[k];
        }
    }
    return res;
}

void modify(int l, int r, int d)
{
    int L = get(l), R = get(r);
    if (L == R)
    {
        for (int i = l; i <= r; ++i)
        {
            int I = get(i);
            a[i] += d, sum[I] += d;
        }
    }
    else
    {
        int i = l, j = r, I, J;
        while ((I = get(i)) == L) {
            a[i] += d, sum[I] += d, ++i;
        }
        while ((J = get(j)) == R) {
            a[j] += d, sum[J] += d, --j;
        }
        for (int k = I; k <= J; ++k){
            sum[k] += (len * d), add[k] += d;
        }
    }
}

signed main()
{
    cin >> n >> m;
    len = n / sqrt(n);
    for (int i = 1; i <= n; ++i)
    {
        int I = get(i);
        scanf("%d", &a[i]);
        sum[I] += a[i];
    }

    while (m--)
    {
        char op[2]; int l, r, d;
        scanf("%s%d%d", op, &l, &r);
        if (*op == 'Q')
        {
            printf("%lld\n", ask(l, r));
        }
        else
        {
            scanf("%d", &d);
            modify(l, r, d);
        }
    }

    return 0;
}