第30个点MLE求助
查看原帖
第30个点MLE求助
474128
kiribati楼主2021/10/14 17:08

RT,求大佬帮忙看看

#include<iostream>
#include<stdio.h>
using namespace std;

const int N = 3e5 + 10;
int n,q;
int rt;
int tot;

struct Node
{
	int l,r;
	int num;
	int len;
	int change;
} tr[40 * N];

void pushup(int u)
{
	tr[u].num = tr[tr[u].l].num + tr[tr[u].r].num;
}

void pushdown(int u)
{
	int change = tr[u].change;
	tr[u].change = 0;
	
	if(!change) return;
	if(change > 0) 
	{
		int& l = tr[u].l;
		int& r = tr[u].r;
		if(!l)
		{
			l = ++tot;
			tr[l].len = (tr[u].len + 1) / 2;
		}
		if(!r)
		{
			r = ++tot;
			tr[r].len = tr[u].len - tr[l].len;
		}
		tr[tr[u].l].change = 1;
		tr[tr[u].r].change = 1;
		tr[tr[u].l].num = tr[tr[u].l].len;
		tr[tr[u].r].num = tr[tr[u].r].len;
	}
	else
	{
		int& l = tr[u].l;
		int& r = tr[u].r;
		if(!l)
		{
			l = ++tot;
			tr[l].len = (tr[u].len + 1) / 2;
		}
		if(!r)
		{
			r = ++tot;
			tr[r].len = tr[u].len - tr[l].len;
		}
		tr[tr[u].l].change = -1;
		tr[tr[u].r].change = -1;
		tr[tr[u].l].num = 0;
		tr[tr[u].r].num = 0;
	}
}

void modify(int& u,int l,int r,int x,int y,int op)
{
	if(!u)
	{
		u = ++tot;
		tr[u].len = r - l + 1;	
	}
	int mid = l + r >> 1;
	
	if(x <= l && r <= y)
	{
		if(op == 1)
		{
			tr[u].change = 1;
			tr[u].num = tr[u].len;	
		}
		else
		{
			tr[u].change = -1;	
			tr[u].num = 0;
		}	
	}
	else
	{
		pushdown(u);
		
		if(x <= mid) modify(tr[u].l,l,mid,x,y,op);
		if(y >= mid + 1) modify(tr[u].r,mid + 1,r,x,y,op);
		
		pushup(u);	
	}	
}

int main()
{
	scanf("%d %d",&n,&q);
	rt = ++tot;
	tr[rt].len = n;
	
	while(q--)
	{
		int x,y,op;
		scanf("%d %d %d",&x,&y,&op);
		
		modify(rt,1,n,x,y,op);
		
		printf("%d\n",n - tr[rt].num);
	}
	
	return 0;
}
2021/10/14 17:08
加载中...