首页 > 其他分享 >CF1290E Cartesian Tree 注意点--zhengjun

CF1290E Cartesian Tree 注意点--zhengjun

时间:2023-07-13 21:55:14浏览次数:37  
标签:rt Cartesian return -- pushcov zhengjun int pushdown fi

解题思路

容易想到从小到大加数,维护每个点的子树大小。

可转化为维护每个点为 \(\max\) 时的 \([L,R]\) 区间。

然后需要写一个支持 【区间+1】、【区间取min】、单点加入、全局查询。

上个吉司机线段树即可。

注意点

  • 吉司机线段树下推 \(fi\) 的标记的时候要注意 \(fi\) 的变化。

    • 错误写法:

      if(fi[rt<<1]>=fi[rt<<1|1])pushcov(rt<<1,tag[rt]);
      if(fi[rt<<1|1]>=fi[rt<<1])pushcov(rt<<1|1,tag[rt]);
      
    • 正确写法:

      int x=fi[rt<<1]-fi[rt<<1|1];
      if(x>=0)pushcov(rt<<1,tag[rt]);
      if(x<=0)pushcov(rt<<1|1,tag[rt]);
      

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1.5e5+10,M=N<<2,INF=1e9;
int n,a[N],pos[N];
namespace R{
	int fi[M],se[M],cnt[M],siz[M];
	int laz[M],tag[M];
	ll sum[M];
	void pushup(int rt){
		siz[rt]=siz[rt<<1]+siz[rt<<1|1];
		sum[rt]=sum[rt<<1]+sum[rt<<1|1];
		fi[rt]=max(fi[rt<<1],fi[rt<<1|1]);
		se[rt]=max(se[rt<<1],se[rt<<1|1]);
		cnt[rt]=0;
		if(fi[rt<<1]==fi[rt])cnt[rt]+=cnt[rt<<1];
		else se[rt]=max(se[rt],fi[rt<<1]);
		if(fi[rt<<1|1]==fi[rt])cnt[rt]+=cnt[rt<<1|1];
		else se[rt]=max(se[rt],fi[rt<<1|1]);
	}
	void pushadd(int rt,int x){
		if(!siz[rt])return;
		laz[rt]+=x,sum[rt]+=1ll*x*siz[rt],fi[rt]+=x,se[rt]+=x;
	}
	void pushcov(int rt,int x){
		if(!siz[rt])return;
		sum[rt]+=1ll*x*cnt[rt],fi[rt]+=x,tag[rt]+=x;
	}
	void pushdown(int rt){
		if(laz[rt]){
			pushadd(rt<<1,laz[rt]);
			pushadd(rt<<1|1,laz[rt]);
			laz[rt]=0;
		}
		if(tag[rt]){
			int x=fi[rt<<1]-fi[rt<<1|1];
			if(x>=0)pushcov(rt<<1,tag[rt]);
			if(x<=0)pushcov(rt<<1|1,tag[rt]);
			tag[rt]=0;
		}
	}
	void build(int l=1,int r=n,int rt=1){
		laz[rt]=tag[rt]=0;
		if(l==r){
			sum[rt]=0;
			fi[rt]=se[rt]=-INF;
			cnt[rt]=0;
			return;
		}
		int mid=(l+r)>>1;
		build(l,mid,rt<<1);
		build(mid+1,r,rt<<1|1);
		pushup(rt);
	}
	void update(int L,int R,int x,int l=1,int r=n,int rt=1){
		if(L<=l&&r<=R)return pushadd(rt,x);
		int mid=(l+r)>>1;
		pushdown(rt);
		if(L<=mid)update(L,R,x,l,mid,rt<<1);
		if(mid<R)update(L,R,x,mid+1,r,rt<<1|1);
		pushup(rt);
	}
	void modify(int L,int R,int x,int l=1,int r=n,int rt=1){
		if(x>=fi[rt])return;
		if(L<=l&&r<=R&&x>=se[rt])return pushcov(rt,x-fi[rt]);
		int mid=(l+r)>>1;
		pushdown(rt);
		if(L<=mid)modify(L,R,x,l,mid,rt<<1);
		if(mid<R)modify(L,R,x,mid+1,r,rt<<1|1);
		pushup(rt);
	}
	void insert(int x,int y,int l=1,int r=n,int rt=1){
		if(l==r){
			siz[rt]=cnt[rt]=1;
			fi[rt]=sum[rt]=y;
			return;
		}
		int mid=(l+r)>>1;
		pushdown(rt);
		if(x<=mid)insert(x,y,l,mid,rt<<1);
		else insert(x,y,mid+1,r,rt<<1|1);
		pushup(rt);
	}
	ll query(){
		return sum[1];
	}
	int find(int x,int l=1,int r=n,int rt=1){
		if(l==r)return fi[rt];
		int mid=(l+r)>>1;
		pushdown(rt);
		return x<=mid?find(x,l,mid,rt<<1):find(x,mid+1,r,rt<<1|1);
	}
}
namespace L{
	int fi[M],se[M],cnt[M],siz[M];
	int laz[M],tag[M];
	ll sum[M];
	void pushup(int rt){
		siz[rt]=siz[rt<<1]+siz[rt<<1|1];
		sum[rt]=sum[rt<<1]+sum[rt<<1|1];
		fi[rt]=min(fi[rt<<1],fi[rt<<1|1]);
		se[rt]=min(se[rt<<1],se[rt<<1|1]);
		cnt[rt]=0;
		if(fi[rt<<1]==fi[rt])cnt[rt]+=cnt[rt<<1];
		else se[rt]=min(se[rt],fi[rt<<1]);
		if(fi[rt<<1|1]==fi[rt])cnt[rt]+=cnt[rt<<1|1];
		else se[rt]=min(se[rt],fi[rt<<1|1]);
	}
	void pushadd(int rt,int x){
		if(!siz[rt])return;
		laz[rt]+=x,sum[rt]+=1ll*x*siz[rt],fi[rt]+=x,se[rt]+=x;
	}
	void pushcov(int rt,int x){
		if(!siz[rt])return;
		sum[rt]+=1ll*x*cnt[rt],fi[rt]+=x,tag[rt]+=x;
	}
	void pushdown(int rt){
		if(laz[rt]){
			pushadd(rt<<1,laz[rt]);
			pushadd(rt<<1|1,laz[rt]);
			laz[rt]=0;
		}
		if(tag[rt]){
			int x=fi[rt<<1]-fi[rt<<1|1];
			if(x<=0)pushcov(rt<<1,tag[rt]);
			if(x>=0)pushcov(rt<<1|1,tag[rt]);
			tag[rt]=0;
		}
	}
	void build(int l=1,int r=n,int rt=1){
		laz[rt]=tag[rt]=0;
		if(l==r){
			sum[rt]=0;
			fi[rt]=se[rt]=INF;
			cnt[rt]=0;
			return;
		}
		int mid=(l+r)>>1;
		build(l,mid,rt<<1);
		build(mid+1,r,rt<<1|1);
		pushup(rt);
	}
	void update(int L,int R,int x,int l=1,int r=n,int rt=1){
		if(L<=l&&r<=R)return pushadd(rt,x);
		int mid=(l+r)>>1;
		pushdown(rt);
		if(L<=mid)update(L,R,x,l,mid,rt<<1);
		if(mid<R)update(L,R,x,mid+1,r,rt<<1|1);
		pushup(rt);
	}
	void modify(int L,int R,int x,int l=1,int r=n,int rt=1){
		if(x<=fi[rt])return;
		if(L<=l&&r<=R&&x<=se[rt])return pushcov(rt,x-fi[rt]);
		int mid=(l+r)>>1;
		pushdown(rt);
		if(L<=mid)modify(L,R,x,l,mid,rt<<1);
		if(mid<R)modify(L,R,x,mid+1,r,rt<<1|1);
		pushup(rt);
	}
	void insert(int x,int y,int l=1,int r=n,int rt=1){
		if(l==r){
			siz[rt]=cnt[rt]=1;
			fi[rt]=sum[rt]=y;
			return;
		}
		int mid=(l+r)>>1;
		pushdown(rt);
		if(x<=mid)insert(x,y,l,mid,rt<<1);
		else insert(x,y,mid+1,r,rt<<1|1);
		pushup(rt);
	}
	ll query(){
		return sum[1];
	}
	int find(int x,int l=1,int r=n,int rt=1){
		if(l==r)return fi[rt];
		int mid=(l+r)>>1;
		pushdown(rt);
		return x<=mid?find(x,l,mid,rt<<1):find(x,mid+1,r,rt<<1|1);
	}
}
int c[N];
void add(int x,int y){
	for(;x<=n;x+=x&-x)c[x]+=y;
}
void get(int x,int &y){
	for(;x;x^=x&-x)y+=c[x];
}
int main(){
	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),pos[a[i]]=i;
	L::build(),R::build();
	for(int i=1,x,t;i<=n;i++){
		add(x=pos[i],1),get(x,t=0);
		L::insert(x,1),R::insert(x,i);
		if(x<n){
			R::update(x+1,n,1);
			L::update(x+1,n,1);
			L::modify(x+1,n,t+1);
		}
		if(x>1){
			R::modify(1,x-1,t-1);
		}
//		for(int i=1;i<=n;i++){
//			auto trs=[&](int x){
//				return abs(x)<=n?x:-1;
//			};
//			fprintf(stderr,"(%d,%d)%c",trs(L::find(i)),trs(R::find(i)),"\n "[i<n]);
//		}
		printf("%lld\n",R::query()-L::query()+i);
	}
	return 0;
}

标签:rt,Cartesian,return,--,pushcov,zhengjun,int,pushdown,fi
From: https://www.cnblogs.com/A-zjzj/p/17552307.html

相关文章

  • 我们刚刚知道那些题的解法-7
    ZR2423一个第一次见到的套路:我们考虑转化一下两个儿子都走这个选择,我们可以考虑建第三个儿子,它的子树中的每个节点的权值等于之前两个儿子对应权值的异或和,则显然,如果接下来没有选择两个儿子都走的话,走第三个儿子正确性是显然的,如果又选择了两个儿子都走,那么就可以对于某个节点再......
  • 虚树
    我们用单调栈来建虚树,如果求lca的复杂度为\(O(\logn)\)的话,整个求虚树的复杂度应该为\(O(n\logn)\)。整体思路为我们用首先把所有关键点按照dfs序排序,然后首先把\(1\)节点加入栈。整个过程我们维护一条左链。我们考虑往里面加入一个新的关键点。求一下这个点和栈顶的......
  • 原根
    原根一些说明令\(p\inPrime\)表示\(p\)是一个素数。一些定义由欧拉定理可以知道,对于\(a\inZ,m\inZ^+,(a,m)=1\),则:\[a^{\phi(m)}\equiv1\bmodm\]因此,对于假设(即在\(a\)和\(m\)互素的前提下),满足同余式\(a^n\equiv1\bmodm\)的最小正整数\(n\)存在,这个......
  • 长链剖分
    类似于轻重链剖分,也有一种树链剖分方式叫做长链剖分,每次我们选子树深度最大的节点当做重儿子,注意这里子树深度是指一棵子树中所有结点的深度最大值。有以下性质:一个节点的\(k\)级祖先所在链的长度一定大于等于\(k\)。比较显然。因为如果小于\(k\)的话就会选从那个祖先到......
  • jvm注意事项 - 指令集出现this关键字
    首先如果在虚拟机中出现了this关键字,那么在栈帧中调用了非static方法。大家都知道,非static方法是需要一个对象的没这个对象的地址就是这个this,如果局部变量表中就存在这个this了,那么他就一定是个非static方法。如果this存在,则操作的指令集的顺序的下标就为0,其他变量的顺序就从1......
  • 我们刚刚知道那些题的解法-3
    NOIPDay1T4考虑以下问题,斜率为\(-1\)的直线上区间加,询问一个点左下角的值的和。如果线是水平或垂直的,那么显然可以用扫描线来解决。考虑这个题如何扫描线。首先我们肯定要斜着扫描,扫描的时候注意维护的是\(x\)轴和\(y\)轴上的值的和而不是扫描线上的值得和。询问只需要考......
  • iOS锁屏事件监听
    私有API(慎用不上appstore的话就可以用)//AppDelegate.m//监听锁屏事件#definekNotificationLockCFSTR("com.apple.springboard.lockcomplete")//监听屏幕状态变化事件#definekNotificationChangeCFSTR("com.apple.springboard.lockstate")-(BOOL)application:(UIAp......
  • xss-labs靶场1-20关详解
    靶场下载链接https://github.com/do0dl3/xss-labs在线靶场https://xssaq.com/yx/Level1(直接注入)源码<!DOCTYPEhtml><!--STATUSOK--><html><head><metahttp-equiv="content-type"content="text/html;charset=utf-8"><scr......
  • 我们刚刚知道那些题的解法-4
    初赛考虑把这些数分成\(n\)组,每组内部比较,然后大的那些选最大,小的那些选最小。答案为\(3n-2\)。double除int或者int除double的返回值都是double,而int除int会向下取整。300iqContest2B题目链接首先考虑\(a_i\oplusa_j\lex\)这个限制不好做,考虑转化,经过......
  • 递归相关知识(java)版
    递归递归小题练习publicstaticintf(intn){if(n==1){return1;}returnn*f(n-1);}publicstaticvoidmain(String[]args){intf=f(5);}递归反向打印字符串-c的话,就正序,java正逆无所谓publicst......