C、Community Service
题意：
有一个
0
到
1
e
6
0到1e6
0到1e6的数轴，有
2
e
5
2e5
2e5次操作：
操作一：增加一条 从
l
到
r
l到r
l到r的线段，每条线段有名字；
操作二：给定一个区间
S
S
S 以及范围
l
到
r
l到r
l到r,求和
S
S
S有交集的 最近一个被加入的线段
T
T
T，并将
T
T
T从线段集中删去。
思路1：
如果没有删除线段的操作，那么这道题就是 线段树区间赋值维护最大值，并且区间求最大值。
但是有删除操作之后，线段之间的关系就是相互覆盖，很容易想到 可持久化相关的数据结构。我的想法是 用主席树来维护增加线段，那么求最近的有交集的线段 就可以用 二分+主席树区间求和来实现。但是对于删除线段的操作，就需要在主席树上再套个数据结构来维护了，且不说时间复杂度会不会爆炸，感觉实现的难度就很大，况且也不确定 树套树能不能维护。如果有知道的，可以告诉我。
思路2：
首先，考虑有两颗 set 的线段树，对于增加一个线段的操作，我们对第一颗线段树，只在
l
到
r
l到r
l到r 分成的
l
o
g
log
log个区间的set中 加入当前线段的编号；对第二颗线段树，我们在 所有
l
o
g
log
log个区间，以及这些区间到根区间的set 都加入当前线段的编号。
考虑询问的时候，第一个线段树，对于
l
到
r
l到r
l到r分成的log个线段，我们对所有这些区间 以及到根区间的 set 取 max，也及覆盖询问区间的log个段 的线段的最大编号；第二个线段树，只对于
l
o
g
log
log 个段的set最大值 取max，也及询问区间的
l
o
g
log
log个段 覆盖的线段的最大编号。这样时间复杂度 就是严格的线段树
O
(
l
o
g
n
)
O(logn)
O(logn)，以及 set
O
(
l
o
g
n
)
O(logn)
O(logn)。
对于删除操作，就是插入的反操作，把标号从set中删除即可。
然后兴高采烈地写完，你会发现
T
54
T54
T54，考虑优化时间复杂度。
注意到，上面的思路中，set的作用就是起到 存储一个序列，并且支持 查询最大值 以及删除一个数的功能。同时，我们插入的编号是 有递增性质的。那么vector或者stack都能实现，存储序列以及查询最大值的操作，但是对于删除一个数，我们可以不用立即删，可以对编号打个标记，下次取出来的手再删即可。
详情见代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109#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
题意：
在 一个
2
e
8
∗
2
e
8
2e8*2e8
2e8∗2e8的二维平面上，执行
4000
4000
4000次操作，每次操作是把一个矩形涂成一个给定元素。
思路：
这是一道比较经典的题目，就是用并查集维护，还没涂的点。
考虑倒序涂矩形，那么就可以用并查集维护下一个还没涂的点。
有一个细节是，对于每个
y
y
y都需要所有的
x
x
x，也及总共
8000
∗
8000
8000*8000
8000∗8000个点。少了的话，会有问题，可以画图找一下。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96#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内容请搜索靠谱客的其他文章。
发表评论 取消回复