动态开点线段树问什么RE?
  • 板块灌水区
  • 楼主nauyng
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/11/4 20:22
  • 上次更新2024/11/4 21:23:07
查看原帖
动态开点线段树问什么RE?
1418281
nauyng楼主2024/11/4 20:22
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
	int l,r,k;
}a[40005];
bool operator<(node x,node y){return x.k<y.k;}
bool operator>(node x,node y){return x.k>y.k;}
struct node2{
	node2 *l,*r;
	int x;
}*root;
int n,maxx,ans;
void dg(int l,int r)
{
	int i=l,j=r;
	node mid=a[(l+r)>>1ll];
	while(i<=j)
	{
		while(a[i]<mid)i=-~i;
		while(a[j]>mid)j=~-j;
		if(i<=j)
		{
			swap(a[i],a[j]);
			i=-~i,j=~-j;
		}
	}
	if(i<r)dg(i,r);
	if(j>l)dg(l,j);
}
void push(node2* &x,int l,int r)
{
	if(x->x==0)
		return;
	if(l>=r)
		return;
	if(x->l==NULL)
		x->l=new node2;
	if(x->r==NULL)
		x->r=new node2;
	x->l->x=x->x;
	x->r->x=x->x;
	x->x=0;
}
node2* f2(node2* &p,int l,int r,int s,int t,int k)
{
	if(p==NULL)
		p=new node2;
	if(s<=l&&r<=t)
	{
		p->x=k;
		return p;
	}
	push(p,l,r);
	int mid=(l+r)/2;
	if(mid>=s)
		p->l=f2(p->l,l,mid,s,t,k);
	if(mid<t)
		p->r=f2(p->r,mid+1,r,s,t,k);
	return p;
}
void f3(node2* &p,int l,int r)
{
	if(p->x)
	{
		ans+=(r-l+1)*p->x;
		return;
	}
	int mid=(l+r)>>1ll;
	if(p->l!=NULL)
		f3(p->l,l,mid);
	if(p->r!=NULL)
		f3(p->r,mid+1,r);
}
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld%lld",&a[i].l,&a[i].r,&a[i].k);
		maxx=max(maxx,max(a[i].l,a[i].r)); 
		a[i].r--;
	}
	dg(1,n);
	for(int i=1;i<=n;i++)
		root=f2(root,1,maxx,a[i].l,a[i].r,a[i].k);
	f3(root,1,maxx);
	printf("%lld",ans);
	return 0;
}
2024/11/4 20:22
加载中...