吉司机线段树

学了一下吉老师的在某年WC的讲的线段树。

特来总结,学习一番.

PDF地址：吉老师的Segment tree Beats!

楔子：给出一个数列A 每次让某个区间中的\(a_i\)对x取min 询问某个区间的和。

\(n,m\leq 500000\)

由于存在多次询问我们进行标记永久化也没什么用如果是一次的话我可以每次把标记标记到区间最后求值即可。

这里要引出吉司机线段树了。

做法：线段树维护区间最大值mx 最大值次数 T 次大值 se 维护区间和 sum

当某个区间要对x取min时显然 mx<=x直接跳过这个区间 se

最坏的情况 x

通过吉老师的证明这复杂度最坏是mlog^2的！

具体证明：自己看pdf... 好吧听说吉老师证明是萎的具体证明看国家集训队论文时间复杂度每次修改时间复杂度为log^2

说了这么多了上例题/cy

bzoj 4695最假女选手

虽然很复杂但是还是要码的要迎男而上男上加男？

//#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define db double
#define INF 2000000000
#define ld long double
#define pb push_back
#define put(x) printf("%d\n",x)
#define rep(p,n,i) for(RE int i=p;i<=n;++i)
#define pii pair 
#define F first
#define mk make_pair
#define mod 64123
#define RE register
#define get(x) x=read()
#define gt(x) scanf("%d",&x)
#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])
#define l(p) t[p].l
#define r(p) t[p].r
#define sum(p) t[p].sum
#define mx(p) t[p].mx
#define mn(p) t[p].mn
#define sx(p) t[p].sx
#define sn(p) t[p].sn
#define tag(p) t[p].tag
#define cx(p) t[p].cx
#define cn(p) t[p].cn
#define zz p<<1
#define yy p<<1|1
#define ls p<<1,l,r
#define rs p<<1|1,l,r
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
	return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
	RE int x=0,f=1;char ch=getc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
	return x*f;
}
const int MAXN=500010;
int n,Q;
struct wy
{
	int l,r,tag;
	ll sum;
	int mx,sx,cx;
	int mn,sn,cn;
}t[MAXN<<2];
inline void pushup(int p)
{
	sum(p)=sum(zz)+sum(yy);
	if(mx(zz)>mx(yy))mx(p)=mx(zz),cx(p)=cx(zz),sx(p)=max(mx(yy),sx(zz));
	if(mx(yy)>mx(zz))mx(p)=mx(yy),cx(p)=cx(yy),sx(p)=max(mx(zz),sx(yy));
	if(mx(zz)==mx(yy))mx(p)=mx(zz),cx(p)=cx(zz)+cx(yy),sx(p)=max(sx(zz),sx(yy));
	if(mn(zz)>1;
	build(zz,l,mid);
	build(yy,mid+1,r);
	pushup(p);
}
inline void pushdown(int p)
{
	int mid=(l(p)+r(p))>>1;
	if(tag(p))
	{
		int x=tag(p);tag(p)=0;
		mx(zz)+=x;tag(zz)+=x;mn(zz)+=x;sx(zz)+=x;sn(zz)+=x;sum(zz)+=(ll)(mid-l(p)+1)*x;
		mx(yy)+=x;tag(yy)+=x;mn(yy)+=x;sx(yy)+=x;sn(yy)+=x;sum(yy)+=(ll)(r(p)-mid)*x;
	}
	if(mx(p)mn(zz))
	{
		if(mx(zz)==mn(zz))mx(zz)=mn(p);
		if(sx(zz)==mn(zz))sx(zz)=mn(p);
		sum(zz)+=(ll)(mn(p)-mn(zz))*cn(zz);
		mn(zz)=mn(p);
	}
	if(mn(p)>mn(yy))
	{
		if(mx(yy)==mn(yy))mx(yy)=mn(p);
		if(sx(yy)==mn(yy))sx(yy)=mn(p);
		sum(yy)+=(ll)(mn(p)-mn(yy))*cn(yy);
		mn(yy)=mn(p);
	}
}
inline void change(int p,int l,int r,int x)
{
	if(l<=l(p)&&r>=r(p))
	{
		sum(p)+=(ll)(r(p)-l(p)+1)*x;
		mx(p)+=x;mn(p)+=x;
		sx(p)+=x;sn(p)+=x;
		tag(p)+=x;return;
	}
	int mid=(l(p)+r(p))>>1;
	pushdown(p);
	if(l<=mid)change(ls,x);
	if(r>mid)change(rs,x);
	pushup(p);
}
inline void modifymax(int p,int l,int r,int x)
{
	if(mn(p)>=x)return;
	if(l<=l(p)&&r>=r(p)&&sn(p)>x)
	{
		sum(p)+=(ll)(x-mn(p))*cn(p);
		if(sx(p)==mn(p))sx(p)=x;
		if(mx(p)==mn(p))mx(p)=x;
		mn(p)=x;return;
	}
	int mid=(l(p)+r(p))>>1;
	pushdown(p);
	if(l<=mid)modifymax(ls,x);
	if(r>mid)modifymax(rs,x);
	pushup(p);
}
inline void modifymin(int p,int l,int r,int x)
{
	if(mx(p)<=x)return;
	if(l<=l(p)&&r>=r(p)&&sx(p)>1;
	pushdown(p);
	if(l<=mid)modifymin(ls,x);
	if(r>mid)modifymin(rs,x);
	pushup(p);
}
inline ll ask(int p,int l,int r)
{
	if(l<=l(p)&&r>=r(p))return sum(p);
	int mid=(l(p)+r(p))>>1;
	pushdown(p);ll cnt=0;
	if(l<=mid)cnt+=ask(ls);
	if(r>mid)cnt+=ask(rs);
	return cnt;
}
inline int querymax(int p,int l,int r)
{
	if(l<=l(p)&&r>=r(p))return mx(p);
	int mid=(l(p)+r(p))>>1;
	pushdown(p);int cnt=-INF;
	if(l<=mid)cnt=max(cnt,querymax(ls));
	if(r>mid)cnt=max(cnt,querymax(rs));
	return cnt;
}
inline int querymin(int p,int l,int r)
{
	if(l<=l(p)&&r>=r(p))return mn(p);
	int mid=(l(p)+r(p))>>1;
	pushdown(p);int cnt=INF;
	if(l<=mid)cnt=min(cnt,querymin(ls));
	if(r>mid)cnt=min(cnt,querymin(rs));
	return cnt;
}
int main()
{
	freopen("1.in","r",stdin);
	get(n);build(1,1,n);
	get(Q);
	rep(1,Q,i)
	{
		int op,x,y;
		get(op);get(x);get(y);
		if(op==1)change(1,x,y,read());
		if(op==2)modifymax(1,x,y,read());
		if(op==3)modifymin(1,x,y,read());
		if(op==4)printf("%lld\n",ask(1,x,y));
		if(op==5)printf("%d\n",querymax(1,x,y));
		if(op==6)printf("%d\n",querymin(1,x,y));
	}
	return 0;
}

一遍AC 再见这又臭又长的代码把我给写蒙蔽了没想到这么长尽管我已经极力压行了。。

考虑标记问题我们在下放标记是有两类标记可以发现赋值标记可以被区间加标记给修改区间加标记则不能被赋值标记修改。

所以我们在进行区间修改时我们把赋值标记修改后就相当于赋值标记后来区间加标记先来这个顺序。

所以再pushdown的时候也同样先区间赋值再单点赋值。

需要注意的是修改mx时会影响到mn sn,修改mn时可能会影响到mx sx.

线段树

吉司机线段树

相关

#直径，线段树#51nod 1766 树上的最远点对

「NOI2020」命运（树形DP+线段树合并）

线段树学习笔记 1

关于线段树的一些认识

线段树

[NOI2015]软件包管理器（巧用线段树）

P6242 【模板】线段树 3

P5494 【模板】线段树分裂

CF1557D Ezzat and Grid（线段树）

cf739 C. Alyona and towers（线段树）

可持久化线段树

Codeforces Round #625 Div1 C,二维偏序，排序+线段树

标签