Defence

emm...这道题我调了一下午你敢信？？

好吧还是我太天真了。

开始的时候以为自己线段树动态开点与合并写错了，就调;

结果发现没问题，那就是信息维护错了。

一开始以为自己最左右的1维护错了，后来与同学标程对拍，没问题。

最后才发现是自己维护最长的0序列时错了，具体的说是，动态开点线段树只有操作过的地方才有实际的点，因此我就忽略了没有插过点的区间是0序列，会给序列长度贡献，因此我就错了。

后来同学提醒才想起来。

然而还是\(WA\)。。。。。。

于是今天下午，坐后面的同学与老师就看到了前排一个抓狂的人，没错就是我。

最终，当我在抓狂中冷静下来时，我看到同学的程序里是在\(DFS\)是实时记录答案，我才猛然想起来：

段树合并时，原来的树信息会被合并到另外一棵树上，这个过程中会有信息的修改与丢失，也就是说，这个过程对原来的某些信息是不安全的。

改掉他后，我就\(A\)了。。。。。。

真是无语了。。。。。。

就当花一下午买个记性吧，正好暴露出我对这个东西不熟，又要复习了。

Code

#include<bits/stdc++.h>

using namespace std;

namespace STD

{

	#define rr register

	typedef long long ll;

	const int N=100004;

	const int inf=INT_MAX;

	int n,m,q;

	int to[N],dire[N],head[N];

	template<typename T> T cmax(rr T x,rr T y){return x>y?x:y;}

	template<typename T> T cmin(rr T x,rr T y){return x<y?x:y;}

	inline void add(int f,int t)

	{

		static int num=0;

		to[++num]=t;

		dire[num]=head[f];

		head[f]=num;

	}

	int read()

	{

		rr int x_read=0,y_read=1;

		rr char c_read=getchar();

		while(c_read<'0'||c_read>'9')

		{

			if(c_read=='-') y_read=-1;

			c_read=getchar();

		}

		while(c_read<='9'&&c_read>='0')

		{

			x_read=(x_read<<3)+(x_read<<1)+(c_read^48);

			c_read=getchar();

		}

		return x_read*y_read;

	}

	class sgt

	{

		private:

			int tot;

			int in;

			int root[N];

			int le[N*30],re[N*30];

			int len[N*30],lc[N*30];

			int rc[N*30];

			int Merge(int,int,int,int);

			void Insert(int&,int,int,int);

			inline void push_up(int,int,int);

			int cmax(int x,int y){return x>y?x:y;}

		public:

			sgt()

			{

				tot=0;

				memset(le,127,sizeof le);

				memset(re,128,sizeof re);

				memset(len,128,sizeof len);

				memset(lc,0,sizeof lc);

				memset(rc,0,sizeof rc);

				in=le[3];

			}

			void insert(int id,int pos){Insert(root[id],1,m,pos);}

			void merge(int x,int y){root[x]=Merge(root[x],root[y],1,m);}

			int query(int id)

			{

				if(!root[id]) return -1;

				return cmax(len[root[id]],m-re[root[id]]+le[root[id]]-1);

			}

	}t;

	inline void sgt::push_up(int id,int l,int r)

	{

		int mid=(l+r)>>1;

		if(lc[id])

		{

			le[id]=le[lc[id]];

			re[id]=re[lc[id]];

			len[id]=max(len[lc[id]],le[id]-l);

			if(rc[id])

			{

				len[id]=max(len[id],len[rc[id]]);

				len[id]=max(len[id],le[rc[id]]-re[lc[id]]-1);

				re[id]=re[rc[id]];

			}

			else

				len[id]=max(len[id],r-re[id]);

		}

		else

		{

			if(!rc[id]) return;

			le[id]=le[rc[id]];

			re[id]=re[rc[id]];

			len[id]=max(len[rc[id]],le[id]-l);

		}

	}

	void sgt::Insert(int &id,int l,int r,int pos)

	{

		if(!id) id=++tot;

		if(l==r)

		{

			le[id]=l;

			re[id]=r;

			len[id]=0;

			return;

		}

		int mid=(l+r)>>1;

		if(pos<=mid) Insert(lc[id],l,mid,pos);

		else Insert(rc[id],mid+1,r,pos);

		len[id]=-inf;

		push_up(id,l,r);

	}

	int sgt::Merge(int id1,int id2,int l,int r)

	{

		if(!id1||!id2) return id1+id2;

		if(l==r)

		{

			le[id1]=l;

			re[id1]=r;

			len[id1]=0;

			return id1;

		}

		int mid=(l+r)>>1;

		lc[id1]=Merge(lc[id1],lc[id2],l,mid);

		rc[id1]=Merge(rc[id1],rc[id2],mid+1,r);

		push_up(id1,l,r);

		return id1;

	}

	int ans[N];

	void dfs(int x)

	{

		for(rr int i=head[x];i;i=dire[i])

		{

			dfs(to[i]);

			t.merge(x,to[i]);

		}

		ans[x]=t.query(x);

	}

};

using namespace STD;

int main()

{

	n=read(),m=read(),q=read();

	for(rr int i=1;i<n;i++)

	{

		int u=read(),v=read();

		add(u,v);

	}

	for(rr int i=1;i<=q;i++)

	{

		int u=read(),p=read();

		t.insert(u,p);

	}

	dfs(1);

	for(rr int i=1;i<=n;i++)

		printf("%d\n",ans[i]);

}

巴特西

Defence

最新文章

热门文章