谁家橙题这么难，建议升绿）））
2026-02-28 19:36:14
发布于：浙江
49阅读
0回复
0点赞
严肃发布在灌水池塘
看见“区间和”这三个字，你想到了什么？
当然是 前缀和 线段树啊。
再来看数据，高达 ，说明暴力肯定做不了了，我们只能老老实实的打线段树了。
代码：
#include <bits/stdc++.h>
using namespace std;
namespace fast{
#define int long long
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
inline bool blank(const char x) {return !(x^32)||!(x^10)||!(x^13)||!(x^9);}
template<typename Tp> inline void read(Tp &x) {x=0; register bool z=true; register char a=gc(); for(;!isdigit(a);a=gc()) if(a=='-') z=false; for(;isdigit(a);a=gc()) x=(x<<1)+(x<<3)+(a^48); x=(z?x:~x+1);}
inline void read(double &x) {x=0.0; register bool z=true; register double y=0.1; register char a=gc(); for(;!isdigit(a);a=gc()) if(a=='-') z=false; for(;isdigit(a);a=gc()) x=x*10+(a^48); if(a!='.') return x=z?x:-x,void(); for(a=gc();isdigit(a);a=gc(),y/=10) x+=y*(a^48); x=(z?x:-x);}
inline void read(char &x) {for(x=gc();blank(x)&&(x^-1);x=gc());}
inline void read(char *x) {register char a=gc(); for(;blank(a)&&(a^-1);a=gc()); for(;!blank(a)&&(a^-1);a=gc()) *x++=a; *x=0;}
inline void read(string &x) {x=""; register char a=gc(); for(;blank(a)&&(a^-1);a=gc()); for(;!blank(a)&&(a^-1);a=gc()) x+=a;}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y) {read(x),read(y...);}
template<typename Tp> inline void write(Tp x) {if(!x) return pc(48),void(); if(x<0) pc('-'),x=~x+1; register int len=0; register char tmp[64]; for(;x;x/=10) tmp[++len]=x%10+48; while(len) pc(tmp[len--]);}
inline void write(const double x) {register int a=6; register double b=x,c=b; if(b<0) pc('-'),b=-b,c=-c; register double y=5*powl(10,-a-1); b+=y,c+=y; register int len=0; register char tmp[64]; if(b<1) pc(48); else for(;b>=1;b/=10) tmp[++len]=floor(b)-floor(b/10)*10+48; while(len) pc(tmp[len--]); pc('.'); for(c*=10;a;a--,c*=10) pc(floor(c)-floor(c/10)*10+48);}
inline void write(const pair<int,double>x) {register int a=x.first; if(a<7) {register double b=x.second,c=b; if(b<0) pc('-'),b=-b,c=-c; register double y=5*powl(10,-a-1); b+=y,c+=y; register int len=0; register char tmp[64]; if(b<1) pc(48); else for(;b>=1;b/=10) tmp[++len]=floor(b)-floor(b/10)*10+48; while(len) pc(tmp[len--]); a&&(pc('.')); for(c*=10;a;a--,c*=10) pc(floor(c)-floor(c/10)*10+48);} else cout<<fixed<<setprecision(a)<<x.second;}
inline void write(const char x) {pc(x);}
inline void write(const bool x) {pc(x?49:48);}
inline void write(char *x) {fputs(x,stdout);}
inline void write(const char *x) {fputs(x,stdout);}
inline void write(const string &x) {fputs(x.c_str(),stdout);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y) {write(x),write(y...);}
}using namespace fast;
const int N=4000005;
vector<int> a(N);
class segment_tree{
private:
struct node{
int lazy=0,data;
}tree[N];
int left_child(int now){//取左孩子，返回的是索引
return 2*now;
}int right_child(int now){//取右孩子
return 2*now+1;
}void pushdown(int now,int l,int r){//懒标记的处理
if(tree[now].lazy!=0){
int mid=(l+r)/2;
tree[left_child(now)].data+=tree[now].lazy*(mid-l+1);
tree[left_child(now)].lazy+=tree[now].lazy;
tree[right_child(now)].data+=tree[now].lazy*(r-mid);
tree[right_child(now)].lazy+=tree[now].lazy;
tree[now].lazy=0;
}
}
public:
void build(int now,int l,int r){//递归建树
tree[now].lazy=0;//懒标记的初始化，后面会讲
if(l==r){//叶子节点
tree[now].data=a[l];
return ;
}int mid=l+(r-l)/2;
build(left_child(now),l,mid);build(right_child(now),mid+1,r);//分别递归左半边和右半边
tree[now].data=tree[left_child(now)].data+tree[right_child(now)].data;//赋值该节点为他的左右孩子节点值之和。
}
long long query_add(int now,int l,int r,int ql,int qr){//求区间和函数。分别为当前节点，左区间，右区间，所求区间的左右区间
if(ql>r or qr<l)return 0;
if(ql<=l and qr>=r)return tree[now].data;
int mid=l+(r-l)/2;
pushdown(now,l,r);
return query_add(left_child(now),l,mid,ql,qr)+query_add(right_child(now),mid+1,r,ql,qr);
}
void update(int now,int l,int r,int idx,int val){//单点更新
if(l==r){
tree[now].data=val;
return ;
}int mid=l+(r-l)/2;
pushdown(now,l,r);
if(idx<=mid){
update(left_child(now),l,mid,idx,val);
}else{
update(right_child(now),mid+1,r,idx,val);
}tree[now].data=tree[left_child(now)].data+tree[right_child(now)].data;
}
void update_range(int now,int l,int r,int ul,int ur,int val){//区间更新
if(ul>r or ur<l)return ;
if(ul<=l and ur>=r){
tree[now].data+=1LL*val*(r-l+1);
tree[now].lazy+=val;
return ;
}int mid=l+(r-l)/2;
pushdown(now,l,r);
update_range(left_child(now),l,mid,ul,ur,val);
update_range(right_child(now),mid+1,r,ul,ur,val);
tree[now].data=tree[left_child(now)].data+tree[right_child(now)].data;
}
};
signed main(){
segment_tree tree;
int n,m;
read(n,m);
for(int i=1;i<=n;i++)cin >> a[i];
tree.build(1,1,n);
while(m--){
int l,r;
cin >> l >> r;
write(tree.query_add(1,1,n,l,r),'\n');
}
return 0;
}
时间复杂度 。
线段树板子，建议升绿（
（效率还不如前缀和
严肃再用莫队做一遍
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+10;
int a[N],ans[N],n,m,b,c,k;
struct node{
int l,r,id;
}md[N];
bool cmp(node x,node y){
if((x.l-1)/b==(y.l-1)/b)return x.r<y.r;
return x.l/b<y.l/b;
}
void add(int x){
c+=a[x];
}
void del(int x){
c-=a[x];
}
signed main(){
int x=1,y=0;
cin >> n >> m;
for(int i=1;i<=n;i++)cin >> a[i];
for(int i=1;i<=m;i++){
cin >> md[i].l >> md[i].r;
md[i].id=i;
}b=sqrt(n);
sort(md+1,md+m+1,cmp);
for(int i=1;i<=m;i++){
int l=md[i].l,r=md[i].r;
while(x>l)add(--x);
while(y<r)add(++y);
while(x<l)del(x++);
while(y>r)del(y--);
ans[md[i].id]=c;
}for(int i=1;i<=m;i++)cout << ans[i] << "\n";
return 0;
}
时间复杂度 。
有帮助，赞一个