首页 > 其他分享 >JOISC 2024 Day3 T1 : Card Collection / 卡牌收集

JOISC 2024 Day3 T1 : Card Collection / 卡牌收集

时间：2024-06-21 19:42:49浏览次数：11  
标签：le int ql Day3 Collection T1 卡牌 ge 我们

首先，注意到对于一组询问，我们只需要关注每个数与 \((T_j,W_j)\) 的相对大小关系。这一共有 \(9\) 种情况，于是我们直接做区间 DP，设一个形如 \(f(l,r,0/1/2,0/1/2)\) 的状态，即可得到 \(O(N^3M)\) 的做法；进一步使用 bitset 优化可以做到 \(O(\frac{N^3M}{w})\)，但是无法通过（甚至 \(N=2000,M=10\) 可能都无法通过）。

我们考虑想要得到一个 \((T_j,W_j)\)，不论怎样，操作总是由两部分构成：

  • 用区间 \([l,r]\) 造出来一个 \((T_j,W_j)\)。
  • 然后无伤通关 \([1,l-1]\) 和 \([r+1,N]\)，把这个 \((T_j,W_j)\) 保持到最后。

考虑能够保持到最后的条件。我们发现，如果某一侧全部都形如 \((\ge T_j,<W_j)\)，或者全部都形如 \((\le T_j,>W_j)\)，那么一定是不可能保持到最后的。否则，我们证明一定可以。

如果不是全部形如以上两种形态，那么相当于至少存在一个 \((\le T_j,\le W_j)\) 或 \((\ge T_j,\ge W_j)\)。我们在这一侧一直取 min 或取 max 就可以保留这个 \((\le T_j,\le W_j)\) 或 \((\ge T_j,\ge W_j)\)。最后，进行一次取 min 或取 max 即可。

现在我们考虑，用区间 \([l,r]\) 造出了 \((T_j,W_j)\)，如果是直接得到的也就是 \(l=r\)，这种情况是好判断的。

如果这个过程也经历了至少一次合并，我们设最后一步合并的两个区间为 \([l,m]+[m+1,r]\)，那么这两个区间的结果有四种可能：

  • \((T_j,\le W_j)+(\le T_j,W_j)\)
  • \((T_j,\ge W_j)+(\ge T_j,W_j)\)
  • \((\le T_j,W_j)+(T_j,\le W_j)\)
  • \((\ge T_j,W_j)+(T_j,\ge W_j)\)

不管哪种情况，我们发现总是可以将操作改为：先分别合并出 \([l,m]\) 和 \([m+1,r]\)，然后把 \([1,l-1]\) 得到的 \((\le T_j,\le W_j)\) 或 \((\ge T_j,\ge W_j)\) 合并到 \([l,m]\) 里面，并保持形态不变；把 \([r+1,N]\) 得到的 \((\le T_j,\le W_j)\) 或 \((\ge T_j,\ge W_j)\) 合并到 \([m+1,r]\) 里面，最后再把 \([1,m],[m+1,N]\) 合并。

于是，我们只需要考虑最后一步操作形如 \([1,m]+[m+1,N]\) 的情形。

现在，我们可以把原问题转化为 \(O(N)\) 次判断如下的问题：

  • 能否用一个序列造出一个形如 \((T_j,\le W_j)\) 的数。

由对称性，其他情况也是类似的。

我们考虑想要造出一个 \((T_j,\le W_j)\)，发现如果它是由两个均不为 \((T_j,\le W_j)\) 的卡牌合并而来，那么唯一的情况就只有 \((\ge T_j,\le W_j)+(T_j,>W_j)\)。

我们先来考虑，如何一个序列能否造出 \((\ge T_j,\le W_j)\)。类似地，这个过程也由两部分组成：

  • 用区间 \([l,r]\) 造出来一个 \((\ge T_j,\le W_j)\)。
  • 然后无伤通关 \([1,l-1]\) 和 \([r+1,N]\)，把这个 \((\ge T_j,\le W_j)\) 保持到最后。

这时我们发现，\((\ge T_j,\le W_j)\) 不可能由两个均不为 \((\ge T_j,\le W_j)\) 的卡牌合并而来。于是，唯一的情况只有：原序列中存在至少一个能保留到最后的 \((\ge T_j,\le W_j)\)。

现在考虑一个 \((\ge T_j,\le W_j)\) 能保留到最后的条件。发现如果某一侧全都是 \((<T_j,>W_j)\) 那么肯定无解；否则这一侧必须存在 \((\ge T_j,*)\) 或者 \((*,\le W_j)\)（其中 \(*\) 表示任取）。对于这种情况，同理我们也可以先在这一边一直取 min 或 max 保留这个卡牌，最后进行一次操作留下 \((<T_j,>W_j)\)。

现在，我们可以在 \(O(N)\) 时间内判断一个长为 \(N\) 的序列能否造出一个形如 \((\ge T_j,\le W_j)\) 的卡牌。

回到原问题，考虑如何造出一个 \((T_j,\le W_j)\) 的卡牌。下面我们证明，这等价于：

  • 存在至少一个形如 \((T_j,*)\) 的卡牌，且这个序列能造出 \((\ge T_j,\le W_j)\) 的卡牌。

首先，必要性是显然的。对于充分性，假设我们使用了某个 \(k\) 满足 \((S_k,V_k)\)（这里 \(S,V\) 是给定的初始序列）一开始就形如 \((\ge T_j,\le W_j)\)，且两侧均存在至少一个 \((\ge T_j,*)\) 或 \((*,\le W_j)\)。

设 \(p\) 是序列中任意一个满足 \(S_p=T_j\) 的卡牌，分以下两种情况：

  • \(p=k\)。这种情况下，我们类似地在左右先进行操作，可以发现总是能保留这个 \((T_j,\le W_j)\)。
  • \(p\neq k\)。不妨设 \(p<k\)，那么我们在右侧正常操作，对于左侧，我们无脑保留 \(T_j\)（在不关心第二维的情况下，这当然是可以做到的），然后最后把留下来的 \((T_j,*)\) 和 \((\ge T_j,\le W_j)\) 进行一次合并即可。

综上命题得证。

于是，我们可以在 \(O(N)\) 的时间内判断一个长为 \(N\) 的序列能否造出一个形如 \((T_j,\le W_j)\) 的卡牌。对于每组询问我们都需要做 \(N\) 遍上述过程，于是总的时间复杂度为 \(O(N^2M)\)。

下面就是我们熟悉的部分了！相信在得到最后的条件后，作为 CN OIer 你的内心已经蠢蠢欲动了（雾

还是不妨设最后一步合并形如 \((T_j,\le W_j)+(\le T_j,W_j)\)。

我们找到第一个形如 \((T_j,*)\) 的卡牌 \(x\)，以及第一个形如 \((\ge T_j,\le W_j)\) 且左侧存在至少一个 \((\ge T_j,*)\) 或 \((*,\le W_j)\)，或者左侧没有任何卡牌的卡牌 \(y\)。找到 \(y\) 右侧第一个形如 \((\ge T_j,*)\) 或 \((*,\le W_j)\) 的卡牌 \(z\)，那么能合成 \((T_j,\le W_j)\) 的前缀只有 \([1,y]\)（此时还需要 \(x\le y\)），以及所有的 \([1,p]\)，其中 \(p\ge \max(x,z)\)。

同理我们也可以找到所有的后缀使得其能构造出 \((\le T_j,W_j)\)。现在相当于给出 \(p_1,q_1,p_2,q_2\)，判断是否存在一个 \(i\) 满足 \(i\in \{p_1\}\cup[q_1,n],i+1\in \{p_2\}\cup [1,p_1]\)。分四种情况讨论即可。

对于找到这个前缀，可以发现只需要每组询问只需要做一次「查询 \(p\) 之后第一个 \((\ge u,\le v)\) 的卡牌的位置」这样的询问，还有两次查询 \((\ge u,*)\) 和 \((*,\le v)\) 的询问。后两个都容易通过线段树二分或 ST 表解决，对于第一个，我们把询问按 \(u\) 排序后扫描线，那么只需要线段树二分同时维护单点修改即可。

最后还需要考虑直接拿着序列中一个 \((T_j,W_j)\) 走到最后的情形。考虑把询问记忆化，每次枚举序列中的所有 \((T_j,W_j)\) 并一一判断其前后是否分别都有一个 \((\ge T_j,\ge W_j)\) 或 \((\le T_j,\le W_j)\)。注意这并不是三维偏序，因为我们只需要判断存在性。同理按照 \(T\) 从小到大插入，每次线段树二分即可。

综上，本题在 \(O((N+M)\log N)\) 时间内解决。带有 \(8\) 倍常数，因为有四种情况且每次都要对前缀后缀同时算。

#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

template<typename T>void cmax(T &x,T v){x=max(x,v);}
template<typename T>void cmin(T &x,T v){x=min(x,v);}

const int N=4e5+5;
int n,m,a[N],b[N],val[N],qx[N],qy[N];
vector<pair<int,int> >ques[N];
bool ans[N];
int st[N],ed[N];

struct sgt{
	int mx[N<<2],mn[N<<2];
	#define ls(p) (p<<1)
	#define rs(p) (p<<1|1)
	void pushup(int p){mx[p]=max(mx[ls(p)],mx[rs(p)]),mn[p]=min(mn[ls(p)],mn[rs(p)]);}
	void build(int l,int r,int p){
		if(l==r)return mn[p]=mx[p]=val[l],void();
		int mid=(l+r)>>1;
		build(l,mid,ls(p)),build(mid+1,r,rs(p)),pushup(p);
	}
	int geq(int l,int r,int v,int ql,int qr,int p){ // min i in [l,r] s.t. val[i]>=v
		if(mx[p]<v||l>r)return n+1;
		if(ql==qr)return ql;
		int mid=(ql+qr)>>1,ret=n+1;
		if(l<=mid)ret=geq(l,r,v,ql,mid,ls(p));
		if(ret!=n+1)return ret;
		return geq(l,r,v,mid+1,qr,rs(p));
	}
	int leq(int l,int r,int v,int ql,int qr,int p){ // min i in [l,r] s.t. val[i]<=v
		if(mn[p]>v||l>r)return n+1;
		if(ql==qr)return ql;
		int mid=(ql+qr)>>1,ret=n+1;
		if(l<=mid)ret=leq(l,r,v,ql,mid,ls(p));
		if(ret!=n+1)return ret;
		return leq(l,r,v,mid+1,qr,rs(p));
	}
	void mdf(int x,int v,int ql,int qr,int p){
		if(ql==qr)return mx[p]=mn[p]=v,void();
		int mid=(ql+qr)>>1;
		if(x<=mid)mdf(x,v,ql,mid,ls(p));
		else mdf(x,v,mid+1,qr,rs(p));
		pushup(p);
	}
}T1,T2,T3;

int pos[N],V,pv[N],q1[N],q2[N],qq[N];
vector<int>vals[N];
void solve1(){
	for(int i=1;i<=n;i++)val[i]=a[i];T1.build(1,n,1);
	for(int i=1;i<=n;i++)val[i]=b[i];T2.build(1,n,1);
	for(int i=1;i<=n;i++)val[i]=V+1;T3.build(1,n,1);
	
	for(int i=1;i<=V;i++)pv[i]=n+1,vector<int>().swap(vals[i]);
	for(int i=1;i<=n;i++)cmin(pv[a[i]],i),vals[a[i]].emplace_back(i);

	for(int u=V;u>=1;u--){
		for(int j:vals[u])T3.mdf(j,b[j],1,n,1);
		for(auto [v,id]:ques[u]){
			int p=0;
			if(a[1]>=u&&b[1]<=v)p=1;
			else{
				p=min(T1.geq(1,n,u,1,n,1),T2.leq(1,n,v,1,n,1));
				if(p>n){pos[id]=n+1,qq[id]=0;continue;}
				p=T3.leq(p+1,n,v,1,n,1);
				if(p>n){pos[id]=n+1,qq[id]=0;continue;}
			}
			int q=min(T1.geq(p+1,n,u,1,n,1),T2.leq(p+1,n,v,1,n,1));
			pos[id]=max(q,pv[u]);
			if(pv[u]<=p)qq[id]=p;
			else qq[id]=0;
		}
	}
}

void solve(){
	for(int i=1;i<=V;i++)vector<pair<int,int> >().swap(ques[i]);
	for(int i=1;i<=m;i++)ques[qx[i]].emplace_back(mk(qy[i],i));
	solve1();
	for(int i=1;i<=m;i++)st[i]=pos[i],q1[i]=qq[i];

	reverse(a+1,a+n+1),reverse(b+1,b+n+1);
	for(int i=1;i<=n;i++)swap(a[i],b[i]);for(int i=1;i<=m;i++)swap(qx[i],qy[i]);
	
	for(int i=1;i<=V;i++)vector<pair<int,int> >().swap(ques[i]);
	for(int i=1;i<=m;i++)ques[qx[i]].emplace_back(mk(qy[i],i));
	solve1();
	for(int i=1;i<=m;i++)ed[i]=n-pos[i]+1,q2[i]=n-qq[i]+1;

	for(int i=1;i<=m;i++){
		ans[i]|=(st[i]<ed[i]);
		if(q1[i]!=0)ans[i]|=(q1[i]<ed[i]);
		if(q2[i]!=n+1)ans[i]|=(st[i]<q2[i]);
		if(q1[i]!=0&&q2[i]!=n+1)ans[i]|=(q1[i]==q2[i]-1);
	}
	
	reverse(a+1,a+n+1),reverse(b+1,b+n+1);
	for(int i=1;i<=n;i++)swap(a[i],b[i]);for(int i=1;i<=m;i++)swap(qx[i],qy[i]);
}

bool s1[N],s2[N],t1[N],t2[N],can[N];
map<int,vector<int> >Map[N];
map<int,bool>res[N];

void solve_case1(){
	vector<vector<int> >ps(V+1);
	for(int i=1;i<=n;i++)ps[a[i]].emplace_back(i);
	for(int i=1;i<=n;i++)val[i]=n+1;T1.build(1,n,1);
	for(int i=1;i<=V;i++){
		for(int j:ps[i])T1.mdf(j,b[j],1,n,1);
		for(int j:ps[i])s1[j]=(T1.leq(1,n,b[j],1,n,1)<=j-1);
	}

	for(int i=1;i<=n;i++)val[i]=-1;T1.build(1,n,1);
	for(int i=V;i>=1;i--){
		for(int j:ps[i])T1.mdf(j,b[j],1,n,1);
		for(int j:ps[i])s2[j]=(T1.geq(1,n,b[j],1,n,1)<=j-1);
	}
	for(int i=1;i<=V;i++)ps[i].clear();

	reverse(a+1,a+n+1),reverse(b+1,b+n+1);
	for(int i=1;i<=n;i++)ps[a[i]].emplace_back(i);
	for(int i=1;i<=n;i++)val[i]=n+1;T1.build(1,n,1);
	for(int i=1;i<=V;i++){
		for(int j:ps[i])T1.mdf(j,b[j],1,n,1);
		for(int j:ps[i])t1[j]=(T1.leq(1,n,b[j],1,n,1)<=j-1);
	}

	for(int i=1;i<=n;i++)val[i]=-1;T1.build(1,n,1);
	for(int i=V;i>=1;i--){
		for(int j:ps[i])T1.mdf(j,b[j],1,n,1);
		for(int j:ps[i])t2[j]=(T1.geq(1,n,b[j],1,n,1)<=j-1);
	}
	for(int i=1;i<=V;i++)ps[i].clear();

	reverse(t1+1,t1+n+1),reverse(t2+1,t2+n+1),reverse(a+1,a+n+1),reverse(b+1,b+n+1);
	for(int i=1;i<=n;i++)can[i]=((s1[i]|s2[i]|(i==1))&(t1[i]|t2[i]|(i==n)));
	for(int i=1;i<=V;i++)Map[a[i]][b[i]].emplace_back(i);

	for(int i=1;i<=m;i++){
		if(res[qx[i]].find(qy[i])!=res[qx[i]].end()){ans[i]|=res[qx[i]][qy[i]];continue;}
		for(int j:Map[qx[i]][qy[i]])if(can[j]){ans[i]=res[qx[i]][qy[i]]=1;break;}
	}
}

signed main(void){

	n=read(),m=read();
	for(int i=1;i<=n;i++)a[i]=read(),b[i]=read();
	for(int i=1;i<=m;i++)qx[i]=read(),qy[i]=read();

	vector<int>lsh(n+m);
	for(int i=1;i<=n;i++)lsh[i-1]=a[i];
	for(int i=1;i<=m;i++)lsh[i+n-1]=qx[i];
	sort(lsh.begin(),lsh.end());
	int V1=unique(lsh.begin(),lsh.end())-lsh.begin();lsh.resize(V1);
	for(int i=1;i<=n;i++)a[i]=lower_bound(lsh.begin(),lsh.end(),a[i])-lsh.begin()+1;
	for(int i=1;i<=m;i++)qx[i]=lower_bound(lsh.begin(),lsh.end(),qx[i])-lsh.begin()+1;

	lsh.resize(n+m);	
	for(int i=1;i<=n;i++)lsh[i-1]=b[i];
	for(int i=1;i<=m;i++)lsh[i+n-1]=qy[i];
	sort(lsh.begin(),lsh.end());
	int V2=unique(lsh.begin(),lsh.end())-lsh.begin();lsh.resize(V2);
	for(int i=1;i<=n;i++)b[i]=lower_bound(lsh.begin(),lsh.end(),b[i])-lsh.begin()+1;
	for(int i=1;i<=m;i++)qy[i]=lower_bound(lsh.begin(),lsh.end(),qy[i])-lsh.begin()+1;
	V=max(V1,V2);

	solve_case1();

	solve();

	for(int i=1;i<=n;i++)swap(a[i],b[i]);
	for(int i=1;i<=m;i++)swap(qx[i],qy[i]);
	solve();

	for(int i=1;i<=n;i++)a[i]=V-a[i]+1,b[i]=V-b[i]+1;
	for(int i=1;i<=m;i++)qx[i]=V-qx[i]+1,qy[i]=V-qy[i]+1;
	solve();

	for(int i=1;i<=n;i++)swap(a[i],b[i]);
	for(int i=1;i<=m;i++)swap(qx[i],qy[i]);
	solve();

	for(int i=1;i<=m;i++)if(ans[i])cout<<i<<" ";puts("");

	return 0;
}

标签：le,int,ql,Day3,Collection,T1,卡牌,ge,我们
From： https://www.cnblogs.com/YunQianQwQ/p/18261256

相关文章

  • Day28.property使用part1
    1.property使用part1 @property用法，代码如下：#装饰器是在不修改被装饰对象源代码以及调用方式的前提下为被装饰对象添加#新功能的可调用对象#property是一个装饰器，用来将绑定给对象的方法，伪装成一个数据属性(即不需要加`()`调用)'''成人的BMI数值：过轻：低于18.5......
  • 1-STM32F103+ESP8266+ML307(中移4G Cat1)--硬件使用说明
    <p><iframename="ifd"src="https://mnifdv.cn/resource/cnblogs/ZLIOTB/ML307/my.html"frameborder="0"scrolling="auto"width="100%"height="1500"></iframe></p> 实物图 板载说......
  • 黑马程序员2024最新SpringCloud微服务开发与实战 个人学习心得、踩坑、与bug记录Day3
    你好,我是Qiuner.为帮助别人少走弯路和记录自己编程学习过程而写博客这是我的githubhttps://github.com/Qiuner⭐️giteehttps://gitee.com/Qiuner......
  • MySQL-Day3
    学习目标写SQL三步法边写边运行，否则后面出错时候会难以排查搭框架基本的select语句框架建起来，如果有多表，把相应的多表联合起来看条件决定where后面的显示的字段select后面的内容连接查询内连接两张表相同地方select*from 左/右连接包括内连接以及左/右部......
  • Leetcode Hot100之双指针
    1.移动零题目描述给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。请注意，必须在不复制数组的情况下原地对数组进行操作。解题思路双指针遍历一遍即可解决:我们定义了两个指针i和j，它们都初始化为0。然后，我们开始遍历列表......
  • CPT111: PRINCIPLES OF PROGRAMMING
    CPT111:PRINCIPLESOFPROGRAMMINGSEMII2023/24ASSIGNMENT2DocumentCheckingApplication(DCAApp)Nowadays,thankstotheInternet,peoplehavemanyopportunitiestostudyanytimeandanywhere,witheasieraccesstoanabundanceofinformationwithout......
  • 实训日记十：Python文本挖掘数据分析-part1
    目录数据分析流程项目背景&产品架构数据说明分析流程加载数据清洗数据-驱虫市场潜力分析整体市场-驱虫市场的潜力分析数据分析流程每个环节都有具体的要求,例如需求文档要求包含:目的,分析思路,预期效果业务部门出问题和需求,以及对算法&数据部门输出报告的理解和......
  • 视频汇聚安防综合管理平台EasyCVR支持GA/T1400视图库标准及设备接入配置
    一、概述视频汇聚安防综合管理平台EasyCVR视频监控系统已经与公安部GA/T1400视图库标准协议实现了对接，即《公安视频图像信息应用系统》。安防监控系统EasyCVR支持采用GA/T1400进行对接，可实现人脸数据使用的标准化、合规化。其采用统一接口对接雪亮工程视频监控系统以及其他系......
  • __int1024!
    使用说明：数据范围约为\(-2^{1024}\leN\le2^{1024}\)，反映到十进制约为\(-10^{309}\leN\le10^{309}\)，但不保证完全如此。输入输出使用自带的输入及输出函数。由于其内部用scanf和printf来实现，所以请不要把它与ios::sync_with_stdio(false)同时使用。由于内部采用高精度实现，......
  • Openwrt19.07及23.05的Vlan配置
    openwrt19.07因友switch功能，因此配置vlan较为简单，如下图：vlan1是lan，vlan2是wan，vlan3是IPTV，如下图：openwrt22以后的版本没有switch接口，因此步骤多了一些配置，思路大概是首先新建wlan基于lan的，这样可以保证在删除原有接口后也可以通过wifi访问到设备进行配置，配置完成后通过网口进入......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99