线段树95分求助
  • 板块P4939 Agent2
  • 楼主崔化博
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/8/30 21:20
  • 上次更新2023/11/4 08:18:46
查看原帖
线段树95分求助
304524
崔化博楼主2021/8/30 21:20
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <algorithm>
using namespace std;
struct node {
	node *ls,*rs;
	int sum,lazy;
};
node *tree;
int n,m,ll,rr,p;
void push_down(int l,int r,node* &root) {
	int mid=(l+r)>>1;
	root->ls->sum+=(mid-l+1)*root->lazy;
	root->ls->lazy+=root->lazy;
	root->rs->sum+=(r-mid)*root->lazy;
	root->rs->lazy+=root->lazy;
	root->lazy=0;
}
void update(int l,int r,node* &root) {
	//cout<<l<<' '<<r<<' '<<root->sum<<endl;
	if(l>=ll&&r<=rr) {
		root->sum+=r-l+1;
		++root->lazy;
		return ;
	}
	int mid=(l+r)>>1;
	if(l!=r) {
		if(root->ls==NULL)
			root->ls=new node(),root->ls->ls=NULL,root->ls->rs=NULL,root->ls->lazy=0,root->ls->sum=0;
		if(root->rs==NULL)
			root->rs=new node(),root->rs->ls=NULL,root->rs->rs=NULL,root->rs->lazy=0,root->rs->sum=0;
	}
	push_down(l,r,root);
	if(ll<=mid)
		update(l,mid,root->ls);
	if(rr>mid)
		update(mid+1,r,root->rs);
	root->sum=root->ls->sum+root->rs->sum;
}
int search(int l,int r,node* root) {
	//cout<<l<<' '<<r<<' '<<root->sum<<endl;
	if(l==r)
		return root->sum;
	int mid=(l+r)>>1;
	if(l!=r) {
		if(root->ls==NULL)
			root->ls=new node(),root->ls->ls=NULL,root->ls->rs=NULL,root->ls->lazy=0,root->ls->sum=0;
		if(root->rs==NULL)
			root->rs=new node(),root->rs->ls=NULL,root->rs->rs=NULL,root->rs->lazy=0,root->rs->sum=0;
	}
	push_down(l,r,root);
	if(p<=mid)
		return search(l,mid,root->ls);
	return search(mid+1,r,root->rs);
}
int main() {
	ios::sync_with_stdio(false);
	tree=new node();
	tree->ls=NULL;
	tree->rs=NULL;
	tree->sum=0;
	tree->lazy=0;
	cin>>n>>m;
	for(int i=1; i<=m; ++i) {
		short k;
		cin>>k;
		if(k&1) {
			cin>>p;
			cout<<search(1,n,tree)<<endl;
		} else {
			cin>>ll>>rr;
			update(1,n,tree);
		}
	}
	return 0;
}











2021/8/30 21:20
加载中...