免责声明

B老师别骂我

正文

对于这道前缀和的板子题，大家坑定使用朴素的前缀和O(n)预处理,O(1)查询(想必大家都会吧。。。)

但为了学好线段树，我写出了如下代码:

CPP

#include<bits/stdc++.h>
using namespace std;

int const ma = 1e5+5;
int t[ma<<2],a[ma];

inline void up(int p){t[p] = t[p<<1]+t[p<<1|1];}

void found(int l,int r,int p){
	if(l == r){
		t[p] = a[l];
		return ;
	}
	int mid = (l + r) >> 1;
	found(l,mid,p<<1);
	found(mid+1,r,p<<1|1);
	up(p);
}

int qry(int L,int R,int l,int r,int p){
	if(L <= l and r <= R)  return t[p];
	int mid = (l + r) >> 1;
	if(R <= mid)  return qry(L,R,l,mid,p<<1);
	else if(L > mid)  return qry(L,R,mid+1,r,p<<1|1);
	else  return qry(L,mid,l,mid,p<<1)+qry(mid+1,R,mid+1,r,p<<1|1);
}

int main(){
	ios:: sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	for(int i = 1; i <= n; ++i)  cin>>a[i];
	found(1,n,1);
	int q;
	cin>>q;
	while(q--){
		int l,r;
		cin>>l>>r;
		cout<<qry(l,r,1,n,1)<<'\n';
	}
	return 0;
//我的马蜂真的很丑吗qwq
}

(集训那会儿教练写的是动态开，而不是堆存)

后来，暑假集训过去了

教练觉得我菜，有俩玩意儿没交我

树状数组，莫队

(树状数组浪费了我一个晚自习，莫队浪费了我一个国庆)

然后这道题就成了我的造粪良地

树状数组:

CPP

#include<bits/stdc++.h>
#define lowbit(aa) (aa&(-aa))
using namespace std;

int const ma = 1e5+5;
int bit[ma],a[ma];

inline int qry(int x){
	int res = 0;
	while(x){
		res += bit[x];
		x -= lowbit(x);
	}
	return res;
}

int main(){
	ios:: sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	for(int i = 1; i <= n; ++i){
		cin>>a[i];
		bit[i] += a[i];
		if(i+lowbit(i) <= n)  bit[i+lowbit(i)] += bit[i];
		// bit[i+lowbit(i)] += bit[i];
	}
	int q;
	cin>>q;
	while(q--){
		int l,r;
		cin>>l>>r;
		cout<<qry(r)-qry(l-1)<<'\n';
	}
	return 0;
}

~~好了这下大家都高兴了~~

然后就是丑陋的莫队了 ~~(我感觉和我初二那会儿一个想法相同，不过我那个想法O(n^2),优化后O(n^3))~~

不得不说，改一个cmp就可以给复杂度从

O(n^2)

变成

O(n\sqrt n)

着实给了我一点震撼

CPP

#include<bits/stdc++.h>
using namespace std;

int const ma = 1e5+5;
int ans = 0;
int a[ma],s;

struct ask{
	int l,r,ans,id;
}que[ma];

int main(){
	ios:: sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	s = sqrt(n);
	for(int i = 1; i <= n; ++i)  cin>>a[i];
	int q;
	cin>>q;
	for(int i = 1; i <= q; ++i){
		cin>>que[i].l>>que[i].r;
		que[i].id = i;
	}
	sort(que+1,que+1+q,[](ask aa,ask bb){
		if(aa.l/s == bb.l/s)  return aa.r < bb.r;
		return aa.l/s < bb.l/s;
	});
	int l = 1,r = 0;
	for(int i = 1; i <= q; ++i){
		int L = que[i].l,R = que[i].r;
		while(l < L)  ans -= a[l++];
		while(l > L)  ans += a[--l];
		while(r < R)  ans += a[++r];
		while(r > R)  ans -= a[r--];
		que[i].ans = ans;
	}
	sort(que + 1,que + 1 + q,[](ask aa,ask bb){return aa.id < bb.id;});
	for(int i = 1; i <= q; ++i)  cout<<que[i].ans<<'\n';
	return 0;
}

我第一次发一个这样的东西，我也不知道我要表达什么， ~~给时间被浪费的人说一声对不起~~

好

【造粪】莫队求静态区间和

文章操作

免责声明

正文

国庆快了，开心比什么都重要

相关推荐

评论

【造粪】莫队求静态区间和