动态开点线段树

<发现自己写代码的能力好垃圾...也可能是饿的>

一下午在debug...跟昨天一样,自己写了份动态开点的代码,然后最后告诉自己清醒一点清楚每个变量要干什么终于解决了.QWQ

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e6+5;
const int mod=1e9+7;
//区间修改 维护区间最值. 
struct Seg{
	int mx[N],lz[N],lc[N],rc[N],id=1;
	void me()
	{
		for(int i=1;i<N;i++)	mx[i]=lz[i]=lc[i]=rc[i]=0;
	}
	void pushup(int u)
	{
		mx[u]=max(mx[lc[u]],mx[rc[u]]);
	}
	void pushdown(int u)
	{
		if(lz[u])
		{
			if(!rc[u])	rc[u]=++id;
			if(!lc[u])	lc[u]=++id;
			mx[rc[u]]=max(mx[rc[u]],lz[u]);
			mx[lc[u]]=max(mx[lc[u]],lz[u]);
			lz[rc[u]]=max(lz[rc[u]],lz[u]);
			lz[lc[u]]=max(lz[lc[u]],lz[u]);
			lz[u]=0;
		}
	}
	void change(int &o,int l,int r,int L,int R,int val)
	{
		if(!o)	o=++id;
		if(L<=l&&r<=R)
		{
			mx[o]=max(mx[o],val);
			lz[o]=max(lz[o],val);
			return;
		}
		int mid=(l+r)>>1;
		pushdown(o);
		if(L<=mid)	change(lc[o],l,mid,L,R,val);
		if(R>mid)	change(rc[o],mid+1,r,L,R,val);	
		pushup(o);
	}
	int query(int o,int l,int r,int pos)
	{
		if(!o)	return 0;
		if(pos<=l&&pos>=r)	
		{
			return mx[o];
		}
		pushdown(o);
		int res=0;
		int mid=(l+r)>>1;
		if(pos<=mid)		res=max(res,query(lc[o],l,mid,pos));
		if(pos>mid)			res=max(res,query(rc[o],mid+1,r,pos));
		return res;
	}
	
}R,C;
map<pair<int,int>,bool>vis;
int main()
{
	int n,q;
	scanf("%d%d",&n,&q);
	R.me();C.me();
	while(q--)
	{
		int x,y;char op;
		cin>>x>>y>>op;
		if(vis[{x,y}])	
		{
			puts("0");
			continue;
		}
		else vis[{x,y}]=true;
		if(op=='L')
		{
			int res=C.query(1,1,n,y);
			cout<<x-res<<'\n';
			int rt=1;
			R.change(rt,1,n,res+1,x,y);
		}
		else
		{
			int res=R.query(1,1,n,x);
			cout<<y-res<<'\n';
			int rt=1;
			C.change(rt,1,n,res+1,y,x);
		}
	}
	return 0;
}