求助,蒟蒻练习线段树,只过了样例
查看原帖
求助,蒟蒻练习线段树,只过了样例
1189662
h18j20y1楼主2024/9/7 23:28
#include <bits/stdc++.h>
using namespace std;

int l,r,n;

struct node{
    int x1,x2,y;
}a[100010];

bool cmp(node a,node b){
	return a.y<b.y;
}

struct tree{
    int l,r;
    long long v,lazy;
}t[100010];

void build(int k,int l,int r){
	t[k].l=l;
	t[k].r=r;
	if(l==r){
        return;
    }
    int mid=(r+l)/2;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
    t[k].v=t[k*2].v+t[k*2+1].v;
}

long long find(int l,int r,int k){
	if (t[k].l>r || t[k].r<l){
		return 0;
	}
	t[k*2].lazy+=t[k].lazy;
	t[k*2+1].lazy+=t[k].lazy;
	t[k].v+=t[k].lazy*(t[k].r-t[k].l+1);
	t[k].lazy=0;
	
	if (t[k].l>=l && t[k].r<=r){
		return t[k].v;
	}
	return find(l,r,k*2) + find(l,r,k*2+1);
}

void add(int l,int r,int kk,int k){
	//无交集
	if (t[k].l>r || t[k].r<l){
		return;
	}
	//节点为所需子集 
	else if (t[k].l>=l && t[k].r<=r){
		t[k].lazy=kk; 
		return;
	}
	//所需为节点子集 
	else if (t[k].l<=l && t[k].r>=r){
		t[k].v+=kk*(r-l+1); 
	}
	else if (t[k].r<=r){
		t[k].v+=kk*(t[k].r-l+1); 
	}
	else if (t[k].l>=l){
		t[k].v+=kk*(r-t[k].l+1); 
	}
	add(l,r,kk,k*2);
	add(l,r,kk,k*2+1);
}

int main (){
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>a[i].y>>a[i].x1>>a[i].x2;
	}
	
	sort(a+1,a+1+n,cmp);
	build(1,1,n);
	
	for (int i=1;i<=n;i++){
		add(a[i].x1,a[i].x2,a[i].y,1);
	}
	cout<<find(1,n,1);
	return 0;
}
2024/9/7 23:28
加载中...