陈志轩 • 5个月前
众所周知,线段树可以求某个区间内数的总和,具体看这里
所以可以算出一共是有 n 个数,第 i 个数是 i^2,然后用线段树计算从第 1 个数到第 n 个数的总和即可。
我是 LLL,只会打模板
code:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 55;
int n,val[maxn * 4],a[maxn],tag[maxn];
void build(int u,int l,int r){
if (l == r){
val[u] = a[l];
return ;
}
int mid = (l + r) / 2;
build(u * 2,l,mid);
build(u * 2 + 1,mid + 1,r);
val[u] = val[u * 2] + val[u * 2 + 1];
}
void pushdown(int u,int l,int r){
if (tag[u]){
int mid = (l + r) / 2;
val[u * 2] += tag[u] * (mid - l + 1);
tag[u * 2] += tag[u];
val[u * 2 + 1] += tag[u] * (r - mid);
tag[u * 2 + 1] += tag[u];
tag[u] = 0;
}
}
int query(int u,int l,int r,int s,int t){
if (s <= l && r <= t){
return val[u];
}
pushdown(u,l,r);
int mid = (l + r) / 2;
if (t <= mid){
return query(u * 2,l,mid,s,t);
}
if (s > mid){
return query(u * 2 + 1,mid + 1,r,s,t);
}
return query(u * 2,l,mid,s,t) + query(u * 2 + 1,mid + 1,r,s,t);
}
signed main(){
int n;
cin>>n;
for (int i = 1;i <= n;i++){
a[i] = i * i;
}
build(1,1,n);
cout<<query(1,1,n,1,n);
return 0;
}
评论: