2021 ICPC Asia Taipei Regional Programming Contest C、F

C、Community Service

题意：
有一个$0到1e6$的数轴，有$2e5$次操作：
操作一：增加一条 从$l到r$的线段，每条线段有名字；
操作二：给定一个区间$S$ 以及范围 $l到r$,求和$S$有交集的 最近一个被加入的线段$T$，并将$T$从线段集中删去。

思路1：
如果没有删除线段的操作，那么这道题就是 线段树区间赋值维护最大值，并且区间求最大值。
但是有删除操作之后，线段之间的关系就是相互覆盖，很容易想到 可持久化相关的数据结构。我的想法是 用主席树来维护增加线段，那么求最近的有交集的线段 就可以用 二分+主席树区间求和来实现。但是对于删除线段的操作，就需要在主席树上再套个数据结构来维护了，且不说时间复杂度会不会爆炸，感觉实现的难度就很大，况且也不确定 树套树能不能维护。如果有知道的，可以告诉我。

思路2：
首先，考虑有两颗 set 的线段树，对于增加一个线段的操作，我们对第一颗线段树，只在 $l到r$ 分成的$log$个区间的set中 加入当前线段的编号；对第二颗线段树，我们在 所有$log$个区间，以及这些区间到根区间的set 都加入当前线段的编号。
考虑询问的时候，第一个线段树，对于$l到r$分成的log个线段，我们对所有这些区间 以及到根区间的 set 取 max，也及覆盖询问区间的log个段 的线段的最大编号；第二个线段树，只对于 $log$ 个段的set最大值 取max，也及询问区间的 $log$个段 覆盖的线段的最大编号。这样时间复杂度 就是严格的线段树 $O(logn)$，以及 set $O(logn)$。
对于删除操作，就是插入的反操作，把标号从set中删除即可。

然后兴高采烈地写完，你会发现 $T54$，考虑优化时间复杂度。
注意到，上面的思路中，set的作用就是起到 存储一个序列，并且支持 查询最大值 以及删除一个数的功能。同时，我们插入的编号是 有递增性质的。那么vector或者stack都能实现，存储序列以及查询最大值的操作，但是对于删除一个数，我们可以不用立即删，可以对编号打个标记，下次取出来的手再删即可。

详情见代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n,m) for(int i=n;i<=m;i++)
#define repp(i,n,m) for(int i=n;i>=m;i--)
typedef pair<int,int> pii;

const ll mod=998244353;
const ll maxn=1e7+5;
const ll INF=0x3f3f3f3f;
ll qp(ll x,ll y){
	ll ans=1;
	while(y){
		if(y%2)ans=ans*x%mod;x=x*x%mod;y/=2;}return ans;}
ll fmul(ll x,ll y){ 	//蹇€熶箻
    ll tmp=(x*y-(ll)((long double)x/mod*y+1.0e-8)*mod);
	return tmp<0?tmp+mod:tmp; 
}    
inline int qread(){
    int s=0,w=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;
    for (;ch>='0'&&ch<='9';ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
    return (w==-1?-s:s);}

int n,m;
vector<int>tr[4000060],tr1[4000060];
int vis[200060];
int cnt=0,ans;
struct no{
	char s[20];
	int l,r;
}z[200050];
void update(int p,int l,int r,int x,int y,int w){
	tr[p].push_back(w);
	if(x<=l&&r<=y){
		return;
	}
	int mid=l+r>>1;
	if(x<=mid)update(2*p,l,mid,x,y,w);
	if(mid<y)update(2*p+1,mid+1,r,x,y,w);
}
void update1(int p,int l,int r,int x,int y,int w){
	if(x<=l&&r<=y){
		tr1[p].push_back(w);
		return;
	}
	int mid=l+r>>1;
	if(x<=mid)update1(2*p,l,mid,x,y,w);
	if(mid<y)update1(2*p+1,mid+1,r,x,y,w);
}
void query(int p,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		while(tr[p].size()){
			int now=*(tr[p].end()-1);
			if(vis[now]){
				tr[p].erase(tr[p].end()-1);
				continue;
			}
			ans=max(ans,now);
			break;
		}
		return;
	}
	int mid=l+r>>1;
	if(x<=mid)query(2*p,l,mid,x,y);
	if(mid<y)query(2*p+1,mid+1,r,x,y); 
}
void query1(int p,int l,int r,int x,int y){
	while(tr1[p].size()){
		int now=*(tr1[p].end()-1);
		if(vis[now]){
			tr1[p].erase(tr1[p].end()-1);
			continue;
		}
		ans=max(ans,now);
		break;
	}
	if(x<=l&&r<=y)return;
	int mid=l+r>>1;
	if(x<=mid)query1(2*p,l,mid,x,y);
	if(mid<y)query1(2*p+1,mid+1,r,x,y); 
}
int main(){
	n=qread();m=qread();
	while(m--){
		int op;
		op=qread();
		if(op==1){
			cnt++;
			scanf("%s",z[cnt].s);
			z[cnt].l=qread();z[cnt].r=qread();
			update(1,0,n-1,z[cnt].l,z[cnt].r,cnt);
			update1(1,0,n-1,z[cnt].l,z[cnt].r,cnt);
		}else{
			ans=0;
			int l=qread(),r=qread();
			query(1,0,n-1,l,r);
			query1(1,0,n-1,l,r);
			if(ans==0){
				printf(">_<n");
			}else {
				printf("%sn",z[ans].s);
				vis[ans]=1;
			}
		}
	}
	return 0;
}

F. What a Colorful Wall

题意：
在 一个$2e8\ast 2e8$的二维平面上，执行$4000$次操作，每次操作是把一个矩形涂成一个给定元素。

思路：
这是一道比较经典的题目，就是用并查集维护，还没涂的点。
考虑倒序涂矩形，那么就可以用并查集维护下一个还没涂的点。
有一个细节是，对于每个$y$都需要所有的$x$，也及总共$8000\ast 8000$个点。少了的话，会有问题，可以画图找一下。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n,m) for(int i=n;i<=m;i++)
#define repp(i,n,m) for(int i=n;i>=m;i--)
typedef pair<int,int> pii;

const ll mod=998244353;
const ll maxn=1e7+5;
const ll INF=0x3f3f3f3f;
ll qp(ll x,ll y){
	ll ans=1;
	while(y){
		if(y%2)ans=ans*x%mod;x=x*x%mod;y/=2;}return ans;}
ll fmul(ll x,ll y){ 	//蹇€熶箻
    ll tmp=(x*y-(ll)((long double)x/mod*y+1.0e-8)*mod);
	return tmp<0?tmp+mod:tmp; 
}    
inline ll qread(){
    ll s=0,w=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;
    for (;ch>='0'&&ch<='9';ch=getchar())s=(s<<1)+(s<<3)+(ch^48);
    return (w==-1?-s:s);}

int n;
struct node{
	int a,b,c,d;
	int co;
}z[40060];
unordered_map<int,int>vis,idx;
struct no{
	int x,y;
}zz[64008001];
int ans=0;
int fa[64008001];
bool cmp(no a,no b){
	if(a.y==b.y)return a.x<b.x;
	return a.y<b.y;
}

int id=0;
int find(int x){
	if(x==fa[x])return x;
	return fa[x]=find(fa[x]);
}
int vv[4060];
vector<int>vx,vy;
int tot=0;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d%d%d",&z[i].a,&z[i].b,&z[i].c,&z[i].d,&z[i].co);
		vx.push_back(z[i].a);
		vx.push_back(z[i].c);
		vy.push_back(z[i].b);
		vy.push_back(z[i].d);
	}
	sort(vx.begin(),vx.end());
	vx.erase(unique(vx.begin(),vx.end()),vx.end());
	sort(vy.begin(),vy.end());
	vy.erase(unique(vy.begin(),vy.end()),vy.end());
	for(int i=0;i<vy.size();i++){
		vis[vy[i]]=++id;
		for(int j=0;j<vx.size();j++){
			tot++;
			fa[tot]=tot;
			zz[tot].x=vx[j];
			zz[tot].y=vy[i];
		}
		tot++;
		fa[tot]=tot;
		zz[tot].x=1e9;
		zz[tot].y=vy[i];
	}
	for(int j=0;j<vx.size();j++){
		idx[vx[j]]=j+1;
	}
	for(int i=n;i>=1;i--){
		int f=0;
		for(int j=vis[z[i].d];j<vis[z[i].b];j++){
			int pos=(j-1)*(vx.size()+1)+idx[z[i].a];
			pos=find(pos);
			for(int k=pos;zz[k].x<z[i].c;k=find(k)){
				fa[k]=k+1;
				f=1;
			}
		}
		if(f&&!vv[z[i].co]){
			vv[z[i].co]=1;
			ans++;
		}
	}
	printf("%dn",ans);
	return 0;
}

最后

以上就是微笑香水为你收集整理的2021 ICPC Asia Taipei Regional Programming Contest C、F的全部内容，希望文章能够帮你解决2021 ICPC Asia Taipei Regional Programming Contest C、F所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。