线段树,为何错误?求调
查看原帖
线段树,为何错误?求调
549521
boy♂Next♂dooor楼主2024/8/6 21:45

参考了某题解的做法 代码大部分差不多 然而样例都过不了

#include<bits/stdc++.h>
#define lc 2*p
#define rc 2*p+1
#define up(p) tr[flag][p].num=tr[flag][lc].num+tr[flag][rc].num
#define len(p) (tr[flag][p].r-tr[flag][p].l+1)
using namespace std;
typedef long long ll;
const int N=1e4+5;
struct SegmentTree{
	int tag,l,r,num,cut;
}tr[2][4*N];//0:sapling+tree 1:tree
int n,l,ans[2];
bool flag;
void build(int p,int l,int r,bool f)
{
	tr[f][p]={0,l,r,0,0};
	if(l==r)
	{
		tr[f][p].num=1;
		return;
	}
	int mid=l+(r-l)/2;
	build(lc,l,mid,f);
	build(rc,mid+1,r,f);
	up(p);
}
void down(int p)
{
	if(tr[flag][p].tag==1)//plant 
	{
		tr[flag][lc].tag=tr[flag][rc].tag=1;
		tr[flag][lc].num=len(lc);tr[flag][rc].num=len(rc);
	}
	else if(tr[flag][p].tag==-1)//cut
	{
		tr[flag][lc].tag=tr[flag][rc].tag=-1;
		tr[flag][lc].num=tr[flag][rc].num=0;
	}
	tr[flag][p].tag=0;
}
void change(int p,int l,int r,int k)
{
	if(tr[flag][p].l>r||tr[flag][p].r<l) return;
	if(tr[flag][p].l>=l&&tr[flag][p].r<=r) 
	{
		if(k>0) //plant
		{
			tr[flag][p].tag=1;
			tr[flag][p].num=len(p);	
			return;
		}
		else //cut
		{
			tr[flag][p].tag=-1;
			ans[flag]+=tr[flag][p].num;
			tr[flag][p].num=0;
			return;
		}
	}	
	down(p);
	change(lc,l,r,k);
	change(rc,l,r,k);
	up(p);
	//if(p==3) cout<<tr[flag][p].num<<' '<<tr[flag][lc].num<<' '<<tr[flag][rc].num<<endl;
	//cout<<"p:"<<p<<endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>l>>n; 
	l++;

	build(1,1,l,1);build(1,1,l,0);
	//for(int i=1;i<=9;i++) cout<<tr[0][i].num<<' ';
	//cout<<endl;
	for(int i=1;i<=n;i++)
	{
		bool op;
		int x,y;
		cin>>op>>x>>y;	
		x++;y++;
		if(!op) 
		{
			flag=0;
			change(1,x,y,-1);
			flag=1;
			change(1,x,y,-1);
		}
		else flag=0,change(1,x,y,1);
	}
	//cout<<tr[0][0].num<<' '<<tr[1][0].num<<' '<<ans[0]-ans[1]<<endl;
	//for(int i=1;i<=9;i++) cout<<tr[0][i].num<<' ';
	//cout<<endl;
	cout<<tr[0][1].num-tr[1][1].num<<'\n'<<ans[0]-ans[1];
 	return 0;
}

2024/8/6 21:45
加载中...