小萌新提问，只对了一个，球求大佬们帮忙看看，谢谢各位大佬
查看原帖
小萌新提问，只对了一个，球求大佬们帮忙看看，谢谢各位大佬
483607
Sui_da_xia隋顺意楼主2021/10/6 12:21
#include <bits/stdc++.h> 
using namespace std;
long long answer[1000000];
long long answer_point = 0;

struct point{
	bool is_leaf = false;
	long long value = 0;
	long long depth;
	point * left_son;
	point * right_son;
	long long begin;
	long long end;
	long long waited_add = 0;
};

point * got_father(point * left_son,point*right_son){
	point * temp_father = new point();
	temp_father -> depth = max(left_son -> depth,right_son->depth) + 1;
	temp_father -> left_son = left_son;
	temp_father -> right_son = right_son;
	temp_father -> value = left_son -> value + right_son -> value;
	temp_father -> begin = min(left_son->begin,right_son->begin);
	temp_father -> end = max(left_son->end,right_son->end);
	return temp_father;
}

long long got_sum(point * head,long long begin,long long end){
	//cout << "little_find_shit" << head ->value << endl;
	if (not head->is_leaf){
		//cout << "left_and right: " << head -> left_son->value << " "<<head -> right_son -> value << endl;
		head -> left_son -> value +=  (head -> waited_add * (head->left_son -> end - head -> left_son ->begin+1));
		head -> right_son -> value += (head -> waited_add * (head->right_son -> end - head -> right_son ->begin+1));
		//cout << "left_and right: " << head -> left_son->value << " "<<head -> right_son -> value << endl;
		head -> waited_add = 0;
	}
	if (begin > head -> end or end < head -> begin ){
		return 0;
	}
	if (begin <= head->begin and head->end <= end){
		return head -> value;
	}
	else{
		return got_sum(head->left_son,begin,end) + got_sum(head->right_son,begin,end);
	}
} 

void add(point * head,long long begin,long long end,long long plus){
	if (not head -> is_leaf){
		head -> left_son -> value +=  (head -> waited_add * (head->left_son -> end - head -> left_son ->begin+1));
		head -> right_son -> value += (head -> waited_add * (head->right_son -> end - head -> right_son ->begin+1));
		head -> waited_add = 0;
	}
	if (begin > head -> end or end < head -> begin ){
		return;
	}
	if (begin <= head->begin and head->end <= end){
		//cout << "little_shit: " << head->value << endl;
		head -> value += ((head->end - head->begin+1) * plus);
		//cout << "little_fuck: " << head->value << endl;
		head -> waited_add += plus;
	}else{
		//cout << "adding: "<< head -> value << endl;
		if (head -> begin <= begin and end <= head -> end){
			head -> value += ((end-begin+1) * plus);
			add(head->left_son,begin,end,plus);
			add(head->right_son,begin,end,plus);
		} else if(head -> begin <= begin and head -> end <= end){
			head -> value += ((head->end-begin+1) * plus);
			add(head->left_son,begin,end,plus);
			add(head->right_son,begin,end,plus);
		} else if(head -> end >= end and head -> begin >= begin){
			head -> value += ((end-head->begin+1) * plus);
			add(head->left_son,begin,end,plus);
			add(head->right_son,begin,end,plus);
		} else{
			//cout << "                    fuck" << endl;
		}
		
	}
}

point * grand_father = NULL;
point * temp_leaf[100000];
long long now_temp_point = 0;
int main(){
	long long n,m; //n个数,m行数
	cin >> n >> m;
	
	long long temp_value;
	for(int i = 1;i<=n;i++){
		cin >> temp_value;
		point * temp = new point();
		temp -> depth = 1;
		temp -> value = temp_value;
		temp -> begin = i;
		temp -> end = i;
		temp -> is_leaf = true;
		temp_leaf[now_temp_point] = temp;
		now_temp_point ++;
		while (true){
			if (now_temp_point == 1){
				break;
			}
			if (temp_leaf[now_temp_point-1] -> depth == temp_leaf[now_temp_point-2] -> depth){
				point * temp_father = got_father(temp_leaf[now_temp_point-2],temp_leaf[now_temp_point-1]);
				temp_leaf[now_temp_point-2] = temp_father;
				temp_leaf[now_temp_point-1] = NULL; 
				now_temp_point --;
			}else{
				break;
			}
		}
	}
	while (now_temp_point > 1){
		point * temp_father = got_father(temp_leaf[now_temp_point-2],temp_leaf[now_temp_point-1]);
		temp_leaf[now_temp_point-2] = temp_father;
		temp_leaf[now_temp_point-1] = NULL; 
		now_temp_point --;
	}
	grand_father = temp_leaf[0];
	long long op;
	long long x,y,k;
	for (int i = 0;i<m;i++){
		cin >> op;
		if (op == 2){
			cin >> x >> y; //x起始位置，y终止位置
			answer[answer_point] = got_sum(grand_father,x,y); 
			//cout << "test: "<<answer[answer_point] <<endl;
			answer_point ++;
		}if (op == 1){
			cin >> x >> y >> k;
			add(grand_father,x,y,k);
		}
	}
	for (int i =0;i<answer_point;i++){
		cout << answer[i]<<endl;
	}
}

回复的大佬最帅了，球求大佬了，琢磨了3小时都没弄出来【扎心】

2021/10/6 12:21