这道题目的数据卡得好厉害。

题目明显是考察线段树延迟标记的，但是因为要考虑到p的值，这种延迟是有条件的：在该节点下所有的数据对于p都应该位于p的同一侧。要么都比p大，要么都比p小。

开始的时候我用一个flag来标记节点下面的值是否相同，这个想法其实不对，在最恶劣的情况下，这种方式几乎会直接退化到单点更新的程度，而且随着数据的输入，算法的效率会越来越低，因为整个树从上到下都是在一次性使用，没办法维护。

但是我还是提交了一下，没有任何悬念的TLE。

我又开始正常的思路，不再考虑一个节点下面的值是否相同，而是去想这些值是否在p的同一侧。想了一下，这样的话，我们只需要知道节点下面的最小值和最大值是不是在p的同一侧就行了，而维护最大值最小值之类的事简直是线段树最擅长的了。代码写好后提交，还是TLE。

这我就有点儿郁闷了，这种方法确实在很高程度上实现了数据的成段更新。我的建树和查找是完全相同的操作，在两个地方不太可能有什么优化的空间，能优化的地方只有更新操作。不过我实在想不来该怎么优化。

我去看了下别人的题解，发现博主用跟我同样地思路过了，不过过得很勉强，在G++下TLE，在C++下AC。我看了下他的代码，相对于我的代码来说，做了两个地方的优化，一个是线段树向下分发的时候加了一个if(a[t].dam)的操作，这个操作能够提高的效率微乎其微。另一个是减少了一个判断操作，这个地方我觉得能提高一些效率。

提交C++928msAC。

 

#include
    
     #include
     
      #define N 200005struct node{	int x,y;	int dam;	int min,max;}a[N*3];int b[N];int m,n,p;int Max(int x,int y){	if(x>y)		return x;	else		return y;}int Min(int x,int y){	if(x
      
       =p)		{			a[t].dam+=2*k;			a[t].max+=2*k;			a[t].min+=2*k;			return ;		}		else if(a[t].max
       
        0)	{		a[temp].dam+=a[t].dam;		a[temp+1].dam+=a[t].dam;		a[temp].min+=a[t].dam;		a[temp+1].min+=a[t].dam;		a[temp].max+=a[t].dam;		a[temp+1].max+=a[t].dam;		a[t].dam=0;	}	if(y<=mid)		InsertTree(temp,x,y,k);	else if(x>mid)		InsertTree(temp+1,x,y,k);	else	{		InsertTree(temp,x,mid,k);		InsertTree(temp+1,mid+1,y,k);	}	a[t].max=Max(a[temp].max,a[temp+1].max);	a[t].min=Min(a[temp].min,a[temp+1].min);	return ;}void FindTree(int t,int x,int y){	if(a[t].x==a[t].y)	{		b[a[t].x]=a[t].dam;		//printf("%d %d %d %d %d\n",a[t].x,a[t].y,a[t].dam,a[t].max,a[t].min);		return ;	}	int temp=t*2;	int mid=(a[t].x+a[t].y)/2;	a[temp].dam+=a[t].dam;	a[temp+1].dam+=a[t].dam;	a[t].dam=0;	FindTree(temp,x,mid);	FindTree(temp+1,mid+1,y);	//printf("%d %d %d %d %d\n",a[t].x,a[t].y,a[t].dam,a[t].max,a[t].min);	return ;}int main(){	while(scanf("%d%d%d",&n,&m,&p)!=EOF)	{		CreatTree(1,1,n);		while(m--)		{			int x,y,k;			scanf("%d%d%d",&x,&y,&k);			InsertTree(1,x,y,k);		}		FindTree(1,1,n);		int i;		for(i=1;i