号家军集训数据结构选做

讲师：金天

Codeforces 319E

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/319/E

形式化题意：对于两个二元组我们称能够到达当且仅当或者，现在有一个空集合，以及次操作：

加入一个二元组，满足每次加入二元组单调递增。
询问第个加入的二元组是否能通过若干个二元组到达第个加入的二元组。

数据范围：

考虑记，那么我们将视作一个结点，那么就会出现一张不定向图，查询就是某一个结点是否能通过一些结点到达另外一些结点。

显然直接把图建出来是，考虑一种优化。

我们考虑将视作线段的形式，能够连边，要么区间包含，要么区间相交。

用并查集维护连通性，因为路径中至多存在一条有向边，将区间拆分到线段树上，加入新区间的时候，把线段树上的对应区间合并打上标记，因为保证区间长度递增，所以新区间对于原集合而言不会存在包含。

AC Code

// ----- Eternally question-----
// Problem: E. Ping-Pong
// Contest: Codeforces - Codeforces Round 189 (Div. 1)
// URL: https://codeforces.com/problemset/problem/319/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-08-13 14:43:06
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10;
int N;
struct Node
{ int opt,l,r; }Qry[MAXN];
std::vector<int>Nums;
int L[MAXN],R[MAXN],Rt[MAXN];
int getRt(int x){ return Rt[x]==x?x:Rt[x]=getRt(Rt[x]); }
inline bool check(int x,int l,int r){ return l<x&&x<r; }
#define ls (p<<1)
#define rs (p<<1|1)
std::vector<int>Tr[MAXN<<2];
void solve(int p,int l,int r,int x,int cur)
{
	if(Tr[p].size())
	{
		for(int v:Tr[p])
		{
			int _v=v;_v=getRt(_v);Rt[_v]=cur;
			checkMin(L[cur],L[_v]),checkMax(R[cur],R[_v]);
		}
		Tr[p].clear();
		Tr[p].emplace_back(cur);
	}
	if(l==r) return ;
	int mid=(l+r)>>1;
	if(x<=mid) solve(ls,l,mid,x,cur);
	else solve(rs,mid+1,r,x,cur);
}
void modifyAdd(int p,int l,int r,int ql,int qr,int cur)
{
	if(l==ql&&qr==r) return Tr[p].emplace_back(cur),void();
	int mid=(l+r)>>1;
	if(qr<=mid) modifyAdd(ls,l,mid,ql,qr,cur);
	else if(ql>mid) modifyAdd(rs,mid+1,r,ql,qr,cur);
	else
	{
		modifyAdd(ls,l,mid,ql,mid,cur);
		modifyAdd(rs,mid+1,r,mid+1,qr,cur);
	}
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i)
	{
		read(Qry[i].opt,Qry[i].l,Qry[i].r);
		if(Qry[i].opt==1) Nums.emplace_back(Qry[i].l),Nums.emplace_back(Qry[i].r);
	}
	std::sort(Nums.begin(),Nums.end());
	Nums.erase(std::unique(Nums.begin(),Nums.end()),Nums.end());
	int Cnt=0,M=Nums.size();
	for(int i=1;i<=N;++i)
	{
		if(Qry[i].opt==1)
		{
			Qry[i].l=std::lower_bound(Nums.begin(),Nums.end(),Qry[i].l)-Nums.begin()+1;
			Qry[i].r=std::lower_bound(Nums.begin(),Nums.end(),Qry[i].r)-Nums.begin()+1;
			++Cnt;Rt[Cnt]=Cnt,L[Cnt]=Qry[i].l,R[Cnt]=Qry[i].r;
			solve(1,1,M,Qry[i].l,Cnt),solve(1,1,M,Qry[i].r,Cnt);
			if(Qry[i].l<Qry[i].r-1) modifyAdd(1,1,M,Qry[i].l+1,Qry[i].r-1,Cnt);
		}
		else
		{
			int u=getRt(Qry[i].l),v=getRt(Qry[i].r);
			bool ans=u==v||check(L[u],L[v],R[v])||check(R[u],L[v],R[v]);
			puts(ans?"YES":"NO");
		}
	}
	return 0;
}
/*

*/

CodeForces 573E

题目简介

题目名称：

题目来源：

评测链接：https://codeforces.com/problemset/problem/573/E

形式化题意：给出一个长度为的序列，求出其一个长度为的子序列，其中满足，且，最大化：

$\sum_{i=1}^{k}i\cdot a_{b_i}$

数据范围：

有一个比较好想的，据说常数比较小甚至还能过：设表示前个中已经选择了个，可以直接转移：

$f_{i,j}=\max\{f_{i-1,j},f_{i-1,j-1}+a_i\cdot j\}$

答案就是：

$\max\limits_{0\leq i\leq n}f_{n,i}$

代码比较好写，就不贴了。

然后考虑怎样去优化，我们把所有的转移给贴出来，发现一个规律，如果固定了，我们将从转移，会存在一个使得：

$f_{i,j}= \begin{cases} f_{i-1,j}&,j\leq k\\ f_{i-1,j-1}+a_i\cdot j&,j>k \end{cases}$

于是很显然的，第一个满足的就是。

如果我们已经找到了这个，就可以对整个数组进行级别的直接转移了。

考虑如何比较和，因为满足单调性，所以直接二分即可。

对于的部分，我们加的是一个公差为的等差数列，而且每加一次之后的项数都会，所以要求能够插入，所以选择来维护。

这样的话，时间复杂度可以做到。

这道题甚至可以优化，考虑在平衡树上执行类似于线段树二分的操作，也就是每一次 checkmid 直接跳平衡树，并只跳一个儿子即可。

AC Code

// ----- Eternally question-----
// Problem: Bear and Bowling
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF573E
// Memory Limit: 250 MB
// Time Limit: 6000 ms
// Written by: Eternity
// Time: 2023-07-08 15:33:13
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
#define int long long
const int MAXN=1e5+10;
const int INF=0x3f3f3f3f;
int N;
ll Dp[MAXN],Val,ans,maxK,valK;
std::mt19937 rnd(19260817);
struct Fhq
{
	#define ls(p) Tr[p].chi[0]
	#define rs(p) Tr[p].chi[1]
	int Idx,Rt,x,y,z;
	struct Treap
	{
		int siz,rd;
		ll val,rval,tagd,tagx;
		int chi[2];
	}Tr[MAXN];
	inline void pushUp(int p)
	{
		Tr[p].siz=Tr[ls(p)].siz+Tr[rs(p)].siz+1;
		Tr[p].rval=rs(p)?Tr[rs(p)].rval:Tr[p].val;
	}
	inline void upDate(int p,ll x,ll d)
	{
		Tr[p].val+=x+d*(Tr[ls(p)].siz+1);
		Tr[p].rval+=x+d*Tr[p].siz;
		Tr[p].tagx+=x,Tr[p].tagd+=d;
	}
	inline void pushDown(int p)
	{
		upDate(ls(p),Tr[p].tagx,Tr[p].tagd);
		upDate(rs(p),Tr[p].tagx+Tr[p].tagd*(Tr[ls(p)].siz+1),Tr[p].tagd);
		Tr[p].tagx=Tr[p].tagd=0;
	}
	inline int newNode(int v)
	{
		Tr[++Idx].siz=1,Tr[Idx].rd=rnd();
		Tr[Idx].val=Tr[Idx].rval=v,Tr[Idx].tagd=Tr[Idx].tagx=0;
		return Idx;
	}
	void splitRk(int p,int rk,int &u,int &v)
	{
		if(!p) u=v=0;
		else
		{
			pushDown(p);
			if(Tr[ls(p)].siz>=rk) v=p,splitRk(ls(p),rk,u,ls(p));
			else u=p,splitRk(rs(p),rk-Tr[ls(p)].siz-1,rs(p),v);
			pushUp(p);
		}
	}
	int merge(int u,int v)
	{
		if(!u||!v) return u^v;
		pushDown(u),pushDown(v);
		if(Tr[u].rd>Tr[v].rd)
		{
			rs(u)=merge(rs(u),v);
			return pushUp(u),u;
		}
		else
		{
			ls(v)=merge(u,ls(v));
			return pushUp(v),v;
		}
	}
	void Divide(int p,int k,ll v)
	{
		if(!p) return ;
		pushDown(p);
		int rk=k+Tr[ls(p)].siz+1;
		if(Tr[p].val>=(ls(p)?Tr[ls(p)].rval:v)+(ll)rk*Val) maxK=rk,valK=Tr[p].val,Divide(rs(p),rk,Tr[p].val);
		else Divide(ls(p),k,v);	
	}
	inline void insert(int pos,ll v)
	{
		x=y=0;
		splitRk(Rt,pos,x,y);
		Rt=merge(merge(x,newNode(v)),y);
	}
	inline void add(int pos,ll v,ll d)
	{
		x=y=z=0;
		splitRk(Rt,pos,x,y);
		upDate(y,v,d);
		Rt=merge(x,y);
	}
	void search(int p)
	{
		checkMax(ans,Tr[p].val);
		pushDown(p);
		if(ls(p)) search(ls(p));
		if(rs(p)) search(rs(p));
	}
	#undef ls
	#undef rs
}Tr;
signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i)
	{
		read(Val),maxK=valK=0;
		Tr.Divide(Tr.Rt,0,0);
		Tr.insert(maxK,valK),Tr.add(maxK,maxK*Val,Val);
	}
	Tr.search(Tr.Rt);
	write(ans);
	return 0;
}
/*

*/

这道题的正解还有一个，也就是把上述操作用分块维护，据说要好写很多。

LibreOJ NOI Round #2 Day 2 T3

题目简介

题目名称：小球进洞
题目来源：

评测链接：https://loj.ac/p/578

形式化题意：在一根非负整数数轴上，每一个点有一个洞，有个小球，初始位置分别在，其中一个点可能会有多个小球，但每一个洞只能装一个小球，每个小球会从向左走直到一个没有小球的洞，将其掉入的洞的位置记作，一共有次操作：

将第个小球的位置改为，
查询满足的小球的和。

数据范围：

首先考虑将拆开进行贡献，记录表示位置在的小球个数，表示的前缀和，表示在中还剩下多少个洞。

对于求解，考虑记表示在位置上满足的小球个数，所以可以得到答案为：

$\sum_{i\leq r}i\times f_{i,l}$

现在来求解：

如果，那么显然，所以；
如果，则考虑之前还能放入多少个小球，而对于之前剩下的洞，实际上就是，所以能够放进去的个数就是。

得到：

$f_{i,l}= \begin{cases} c(i)&,i\leq l\\ \max\left\{0,\min\limits_{l\leq j<i}\big(d(j)-d(i)\big)\right\}&,i>l \end{cases}$

考虑用线段树维护这个玩意儿，记录的最小值，并使用类似于兔队线段树的方式维护前缀最大值（参考楼房重建的做法），记录表示前缀最大值，先做左子树，再通过左子树更新的去记录右子树，这样可以做到。

然后考虑如果求解，用相同的方式，记录表示落在的小球是否，贡献答案：

$\sum_{i\leq l}i\times\big(g_{i,+\infty}-g_{i,r-1}\big)$

这里的取即可。

按照维护的方法，可以知道：

$g_{i,r}= \begin{cases} 1&,i\geq r\\ \left[ \left(\max\limits_{i\leq j\leq r}d(j)\right)\geq d(i-1) \right]&,i<r \end{cases}$

同样可以通过前缀最值线段树维护。

时间复杂度可以做到，至于的第一种取值，只有在的时候才可能出现，所以直接特判即可。

AC Code

// ----- Eternally question-----
// Problem: #578. 「LibreOJ NOI Round #2」小球进洞
// Contest: LibreOJ
// URL: https://loj.ac/p/578
// Memory Limit: 512 MB
// Time Limit: 4000 ms
// Written by: Eternity
// Time: 2023-07-08 20:52:42
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
#define int long long
const int MAXN=2e5+10,MAXQ=2e5+10;
const int INF=0x3f3f3f3f;
int N,Q,a[MAXN];
int Cnt[MAXN],Diff[MAXN];
#define ls (p<<1)
#define rs (p<<1|1)
struct St
{ int l,r,val,tag,ansa,ansb; }Tr[MAXN<<2];
inline int getSeg(int l,int r){ return (l+r)*(r-l+1)/2; }
inline void upDate(int p,int x){ Tr[p].val+=x,Tr[p].tag+=x; }
inline void pushDown(int p)
{
	if(!Tr[p].tag) return ;
	upDate(ls,Tr[p].tag),upDate(rs,Tr[p].tag);
	Tr[p].tag=0;
}
int get_ansa(int p,int l,int r,int &pre)
{
	if(l<=Tr[p].l&&Tr[p].r<=r)
	{
		if(pre>=Tr[p].val) return 0;
		if(Tr[p].l==Tr[p].r)
		{
			int res=(Tr[p].val-pre)*Tr[p].l;
			checkMax(pre,Tr[p].val);
			return res;
		}
		else
		{
			pushDown(p);
			if(Tr[ls].val<=pre) return get_ansa(rs,l,r,pre);
			else
			{
				int res=get_ansa(ls,l,r,pre)+(Tr[p].ansa-Tr[ls].ansa);
				checkMax(pre,Tr[rs].val);
				return res;
			}
		}
	}
	pushDown(p);
	int mid=(Tr[p].l+Tr[p].r)>>1,res=0;
	if(l<=mid) res+=get_ansa(ls,l,r,pre);
	if(mid<r) res+=get_ansa(rs,l,r,pre);
	return res;
}
int get_ansb(int p,int l,int r,int &pre)
{
	if(l<=Tr[p].l&&Tr[p].r<=r)
	{
		if(pre>=Tr[p].val) return getSeg(Tr[p].l+1,Tr[p].r+1);
		if(Tr[p].l==Tr[p].r)
		{
			int res=(pre>=Tr[p].val)*(Tr[p].l+1);
			checkMax(pre,Tr[p].val);
			return res;
		}
		else
		{
			pushDown(p);
			if(Tr[rs].val<=pre) return get_ansb(ls,l,r,pre)+getSeg(Tr[rs].l+1,Tr[rs].r+1);
			else
			{
				int res=get_ansb(rs,l,r,pre)+(Tr[p].ansb-Tr[rs].ansb);
				checkMax(pre,Tr[ls].val);
				return res;
			}
		}
	}
	pushDown(p);
	int mid=(Tr[p].l+Tr[p].r)>>1,res=0;
	if(mid<r) res+=get_ansb(rs,l,r,pre);
	if(l<=mid) res+=get_ansb(ls,l,r,pre);
	return res;
}
inline void pushUp(int p)
{
	Tr[p].val=std::max(Tr[ls].val,Tr[rs].val);
	int pre=Tr[ls].val;
	Tr[p].ansa=Tr[ls].ansa+get_ansa(rs,Tr[rs].l,Tr[rs].r,pre);
	pre=Tr[rs].val;
	Tr[p].ansb=Tr[rs].ansb+get_ansb(ls,Tr[ls].l,Tr[ls].r,pre);
}
void build(int p,int l,int r)
{
	Tr[p].l=l,Tr[p].r=r,Tr[p].tag=0;
	if(l==r)
	{
		Tr[p].val=Diff[l],Tr[p].ansa=Cnt[l]*l,Tr[p].ansb=(Diff[l]>=Diff[l-1])*(l+1);
		return ;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushUp(p);
}
void modifyAdd(int p,int l,int r,int v)
{
	if(l<=Tr[p].l&&Tr[p].r<=r) return upDate(p,v);
	pushDown(p);
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(l<=mid) modifyAdd(ls,l,r,v);
	if(mid<r) modifyAdd(rs,l,r,v);
	pushUp(p);
}
int query(int p,int l,int r)
{
	if(l>r) return -INF;
	if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].val;
	pushDown(p);
	int mid=(Tr[p].l+Tr[p].r)>>1,res=-INF;
	if(l<=mid) checkMax(res,query(ls,l,r));
	if(mid<r) checkMax(res,query(rs,l,r));
	return res;
}
signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(N,Q);
	for(int i=1;i<=N;++i) read(a[i]),++Cnt[a[i]];
	for(int i=1;i<=(N<<1);++i) Diff[i]=Diff[i-1]+Cnt[i]-1;
	build(1,0,N<<1);
	for(int opt,l,r;Q--;)
	{
		read(opt,l,r);
		if(opt==1)
		{
			int x=l,y=r;
			modifyAdd(1,a[x],N<<1,-1);
			--Cnt[a[x]];a[x]=y;++Cnt[a[x]];
			modifyAdd(1,a[x],N<<1,1);
		}
		else
		{
			int ans=0;
			int pre=query(1,l,N<<1);
			ans+=get_ansb(1,0,l-1,pre);
			pre=query(1,l,r-1);
			ans-=get_ansb(1,0,l-1,pre);
			if(l==r) ans+=r*Cnt[r],++r;
			pre=query(1,l,r-1);
			ans+=get_ansa(1,r,N<<1,pre);
			write(ans,'\n');
		}
	}
	return 0;
}
/*

*/

BZOJ4237

题目简介

题目名称：稻草人
题目来源：

评测链接：https://darkbzoj.cc/problem/4237

形式化题意：在二维平面上有个点，称一个矩形合法要求三个条件：

其边与坐标轴平行；
左下角与右上角都是一个给定点（即由两个给定点组成）；
其矩形内除了这两个点之外不能有其他任何点。

求合法矩形个数。

数据范围：，保证两两不相同。

再简化一下题意，求二元组满足且不存在满足的二元组个数。

一个较为经典的偏序问题，考虑用分治来解决。

首先按照从小到大排序，就只需要计算的贡献，现在计算作为左下角点，作为右上角点的方案数。

考虑其贡献形式，对于的贡献集合，记录表示中大于的最小坐标，那对于中，能够贡献的只有满足且合法的部分。而对于的贡献集合，一定是一个在单调递增同时单调递减的单调序列，这个可以通过单调栈维护出来。同样也可以通过单调栈维护出来。

接下来我们已经得到了贡献的单调递减序列，对于所有，我们二分出满足的区间并更新答案就可以了。

时间复杂度。

AC Code

// ----- Eternally question-----
// Problem: #4237. 稻草人
// Contest: BZOJ
// URL: https://darkbzoj.cc/problem/4237
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-07-09 16:20:50
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e5+10;
const int INF=0x3f3f3f3f;
int N;
std::vector<int>Nums;
struct Point
{
	int x,y;
	bool operator<(const Point &_) const
	{ return x<_.x; }
}Pt[MAXN];
inline bool cmp(Point a,Point b){ return a.y>b.y; }
int Stk[MAXN],Top,Stkl[MAXN],Topl;
ll ans;
void DAC(int l,int r)
{
	if(l>=r) return ;
	int mid=(l+r)>>1;
	DAC(l,mid),DAC(mid+1,r);
	std::sort(Pt+l,Pt+mid+1,cmp),
	std::sort(Pt+mid+1,Pt+r+1,cmp);
	Topl=Top=0;
	for(int i=l,j=mid+1;i<=mid;++i)
	{
		for(;j<=r&&Pt[j].y>=Pt[i].y;++j)
		{
			while(Top&&Pt[Stk[Top]].x>Pt[j].x) --Top;
			Stk[++Top]=j;
		}
		while(Topl&&Pt[Stkl[Topl]].x<Pt[i].x) --Topl;
		int cur=Pt[Stkl[Topl]].y;
		Stkl[++Topl]=i;
		int ql=1,qr=Top+1,res=qr;
		while(ql<=qr)
		{
			int qmid=(ql+qr)>>1;
			if(Pt[Stk[qmid]].y<=cur) qr=qmid-1,res=qmid;
			else ql=qmid+1;
		}
		ans+=Top-res+1;
	}
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(N);Pt[0]=(Point){0,INF};
	for(int i=1;i<=N;++i) read(Pt[i].x,Pt[i].y);
	std::sort(Pt+1,Pt+N+1);
	DAC(1,N);
	write(ans);
	return 0;
}
/*

*/

Ynoi2009

题目来源

题目名称：

题目来源：

评测链接：https://www.acmicpc.net/problem/18756
评测链接：https://www.luogu.com.cn/problem/P6109

形式化题意：在的二维空间中，有个矩阵加操作形如，有个矩阵最大值查询形如，保证在之前。

数据范围：

感觉和之前的某个题很熟悉，但是数据范围扩大了很多，所以不可能使用二维树状数组来解决，考虑一种分治的结构。并考虑降维。

我们对某一维作扫描线，将操作视作两个操作，在时对区间进行区间加，在的时候对区间进行区间加。

所以我们将一个修改操作视为。

考虑一个稍微暴力的解法，我们枚举并处理所有修改，然后处理所有的询问，扫描线到，此时可以使用线段树维护历史最值，然后维护区间加，并在处理完之后将历史最值时效化（也就是，清空历史最大值）。这样可以做到。

~~好像比暴力要略优一点~~，考虑优化。

考虑从询问入手，一个询问由两部分组成：

的操作，作为初始的和；
的操作，此时需要依次加入操作并维护历史最值。

这是一个较为普遍的分治结构，考虑线段树分治。

设当前我们处理区间为，此时的操作已经被处理完毕了，首先处理，插入的操作后将询问按照由小到大排序，依次插入操作并询问，然后回退并递归右子树，然后处理左子树，将由大到小合并每次询问后删除操作即可。先左后右也是可以做的。

这样最后实现的复杂度就是了。

AC Code

// ----- Eternally question-----
// Problem: P6109 [Ynoi2009] rprmq1
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6109
// Memory Limit: 512 MB
// Time Limit: 4000 ms
// Written by: Eternity
// Time: 2023-07-11 14:45:07
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=5e5+10;
const int Inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
int N,M,Q;
ll ans[MAXN];
struct Segment
{
	#define ls (p<<1)
	#define rs (p<<1|1)
	struct St
	{
		int l,r;
		ll val,cval,tag,ctag;
		bool rst;
	}Tr[MAXN<<2];
	inline void pushUp(int p)
	{
		Tr[p].val=std::max(Tr[ls].val,Tr[rs].val);
		Tr[p].cval=std::max(Tr[ls].cval,Tr[rs].cval);
	}
	inline void upDate(int p,ll tag,ll ctag)
	{
		checkMax(Tr[p].cval,Tr[p].val+ctag);
		checkMax(Tr[p].ctag,Tr[p].tag+ctag);
		Tr[p].val+=tag,Tr[p].tag+=tag;
	}
	inline void Reset(int p)
	{
		upDate(ls,Tr[p].tag,Tr[p].ctag),upDate(rs,Tr[p].tag,Tr[p].ctag);
		Tr[p].tag=Tr[p].ctag=0,Tr[p].rst=1;
		Tr[p].cval=Tr[p].val;
	}
	inline void pushDown(int p)
	{
		if(Tr[p].rst){ Reset(ls),Reset(rs),Tr[p].rst=0; }
		upDate(ls,Tr[p].tag,Tr[p].ctag),
		upDate(rs,Tr[p].tag,Tr[p].ctag);
		Tr[p].tag=Tr[p].ctag=0;
	}
	void build(int p,int l,int r)
	{
		Tr[p].l=l,Tr[p].r=r;
		if(l==r) return ;
		int mid=(l+r)>>1;
		build(ls,l,mid),build(rs,mid+1,r);
	}
	void modifyAdd(int p,int l,int r,ll v)
	{
		if(l<=Tr[p].l&&Tr[p].r<=r) return upDate(p,v,v);
		pushDown(p);
		int mid=(Tr[p].l+Tr[p].r)>>1;
		if(l<=mid) modifyAdd(ls,l,r,v);
		if(mid<r) modifyAdd(rs,l,r,v);
		pushUp(p);
	}
	ll queryCmax(int p,int l,int r)
	{
		if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].cval;
		pushDown(p);
		int mid=(Tr[p].l+Tr[p].r)>>1;ll res=-INF;
		if(l<=mid) checkMax(res,queryCmax(ls,l,r));
		if(mid<r) checkMax(res,queryCmax(rs,l,r));
		return res;
	}
	#undef ls
	#undef rs
}Tr;
struct Query
{ int id,l,r,x,y; }qr[MAXN];
struct Node
{ int l,r;ll val; };
std::vector<Query>Qry[MAXN<<2];
std::vector<Node>vec[MAXN];
#define ls (p<<1)
#define rs (p<<1|1)
inline void Segadd(int p,int l,int r,Query q)
{
	int mid=(l+r)>>1;	
	if(q.l<=mid+1&&mid<=q.r) return Qry[p].emplace_back(q),void();
	if(q.r<=mid) Segadd(ls,l,mid,q);
	else Segadd(rs,mid+1,r,q);
}
inline bool cmpNode(Node a,Node b){ return a.val<b.val; }
inline bool cmpL(Query a,Query b){ return a.l>b.l; }
inline bool cmpR(Query a,Query b){ return a.r<b.r; }
inline void Segup(int p,int opt)
{
	if(opt==1) for(auto x:vec[p]) Tr.modifyAdd(1,x.l,x.r,x.val);
	else for(int i=vec[p].size()-1;~i;--i) Tr.modifyAdd(1,vec[p][i].l,vec[p][i].r,-vec[p][i].val);
}
void Dac(int p,int l,int r)
{
	int mid=(l+r)>>1;
	for(int i=l;i<=mid;++i) Segup(i,1);
	int cnt=0,pos=1;
	for(auto v:Qry[p]) qr[++cnt]=v;
	std::sort(qr+1,qr+cnt+1,cmpR);
	while(pos<=cnt&&qr[pos].r==mid) ++pos;
	for(int i=mid+1;i<=r;++i)
	{
		Segup(i,1);
		if(i==mid+1) Tr.Reset(1);
		while(qr[pos].r==i&&pos<=cnt)
		{
			checkMax(ans[qr[pos].id],Tr.queryCmax(1,qr[pos].x,qr[pos].y));
			++pos;
		}
	}
	for(int i=r;i>mid;--i) Segup(i,-1);
	if(l!=r) Dac(rs,mid+1,r);
	cnt=0,pos=1;
	for(auto v:Qry[p]) qr[++cnt]=v;
	std::sort(qr+1,qr+cnt+1,cmpL);
	while(pos<=cnt&&qr[pos].l==mid+1) ++pos;
	for(int i=mid;i>=l;--i)
	{
		if(i==mid) Tr.Reset(1);
		while(qr[pos].l==i&&pos<=cnt)
		{
			checkMax(ans[qr[pos].id],Tr.queryCmax(1,qr[pos].x,qr[pos].y));
			++pos;
		}
		Segup(i,-1);
	}
	if(l!=r) Dac(ls,l,mid);
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(N,M,Q);
	Tr.build(1,1,N);
	for(int i=1;i<=M;++i)
	{
		int l,r,x,y;ll val;
		read(l,x,r,y,val);
		vec[l].emplace_back((Node){x,y,val});
		vec[r+1].emplace_back((Node){x,y,-val});
	}
	for(int i=1,l,r,x,y;i<=Q;++i)
	{
		read(l,x,r,y);
		Segadd(1,1,N,(Query){i,l,r,x,y});
	}
	for(int i=1;i<=N;++i) std::sort(vec[i].begin(),vec[i].end(),cmpNode);
	Dac(1,1,N);
	for(int i=1;i<=Q;++i) write(ans[i],'\n');
	return 0;
}
/*

*/