UDP广播协议叫吃饭


私信TA

用户名:Mustenaka

访问量:6480

签 名:

大家别被 HZU挑战自我 给骗了,其实他是HZU中最强的人!

排  名 26
经  验 6645
参赛次数 6
文章发表 120
年  龄 3
在职情况
学  校 Sky_box
专  业 NE

  自我简介:

この青春の始まりを、悔しいのないように大切にしたい。

放点自用模板...自用的

<差分数组>

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int orign[maxn];
int divi[maxn];
int fin[maxn];
int sum[maxn];
int n,t,s; //n为数组长度,t为修改区间次数,s为查询区间总和数量
int l,r,value;	//l,r决定一个区间区间,value为修改值.
int main() {
	memset(orign,0,sizeof(orign));
	memset(divi,0,sizeof(divi));
	memset(fin,0,sizeof(fin));
	memset(sum,0,sizeof(sum));
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>orign[i];
		divi[i]=orign[i]-orign[i-1];
	}
	cin>>t;
	while(t--) {
		cin>>l>>r>>value;
		divi[l]+=value;
		divi[r+1]-=value;
	}
	for(int i=1; i<=n; i++) {	//更新参数;
		fin[i]=fin[i-1]+divi[i];
		sum[i]=sum[i-1]+fin[i];
	}
	cin>>s;
	while(s--){
		cin>>l>>r;
		cout<<sum[r]-sum[l-1]<<endl;
	}
	return 0;
}

<树状数组>

#include<bits/stdc++.h>
#define hh ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
int n,t;	//n数组大小,t为查询次数 
int d[100005];	//d为树状数组 
int orign[100005];	//orign为原数组 

int lowbit(int x){	//lowbit操作 
	 return x&(-x); 
} 
int query(int x){	//前k个数的和 
	int res=0;
	while(x){
		res+=d[x];
		x-=lowbit(x);
	}
	return res;
}
void update(int x,int v){	//将第x个数相加v 
	while(x<=n){
		d[x]+=v;
		x+=lowbit(x);
	}
}
int ask(int l,int r){		//求区间l~r的区间和 
	return query(r)-query(l-1);
} 
int main() {
	memset(d,0,sizeof(d));
	memset(orign,0,sizeof(orign));
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>orign[i];
		update(i,orign[i]);
	}
	/*printf("orign\td \n");
	for(int i=0;i<=n;i++){
		printf("%d\t%d\n",orign[i],d[i]);
	}*/
	cin>>t;			//输入查询次数 
	for(int i=1;i<=t;i++){
		int l,r;
		cin>>l>>r;
		cout<<ask(l,r)<<endl;
	}
	return 0;
} 
//树状数组模板

不做解释(网上一大堆),需要自取

  评论区