题干：
链接：https://ac.nowcoder.com/acm/contest/370/A
来源：牛客网
恭喜你找到了本场比赛的签到题！
为了让大家都有抽奖的机会，只需要复制粘贴以下代码（并且稍微填下空）即可 AC：
（我超良心的）
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define fi first
#define lc (x<<1)
#define se second
#define U unsigned
#define rc (x<<1|1)
#define Re register
#define LL long long
#define MP std::make_pair
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 1000000+5;
int N,maxL;
std::set<std::pair<int,int> > L;
inline int calc(){
// 返回 set 中所有线段的并长度。(每个 pair 表示一个线段[first,second]
}
int main(){
scanf("%d%d",&N,&maxL);
while(N--){
int opt,x,y;
scanf("%d%d%d",&opt,&x,&y);
if(opt == 1){
if(L.find(MP(x,y)) != L.end()) continue;
L.insert(MP(x,y));
}
if(opt == 2){
if(L.find(MP(x,y)) == L.end()) continue;
L.erase(MP(x,y));
}
if(opt == 3){
printf("%d\n",calc());
}
}
return 0;
} 输入描述:
第一行两个整数 N,L，意义如代码所述。
接下来 N 行，每行三个整数 opt,l,r，意义如代码所述。 输出描述:
对于每一组 opt=3 的询问输出一个答案。 示例1
输入
6 13
1 1 2
1 4 5
1 4 7
1 6 9
1 12 13
3 3 3 输出
10 说明
我们依次加入线段[1,2],[4,5],[4,7],[6,9],[12,13]， 它们的并集长度为 10. 备注:
N≤105,L≤105,0≤l≤r≤LN≤105,L≤105,0≤l≤r≤L，保证数据随机生成。 解题报告：
题目需要你维护一个线段集合，支持插入线段，删除线段和求线段并长度。
我们可以用简化版的扫描线来实现，当然因为数据随机，暴力也可以过。。。。
AC代码1：（直接暴力）（400ms-800ms）
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 1e5 + 5;
set<int> ss[MAX];
int vis[MAX];
int main()
{
int n,maxl,ans=0;
scanf("%d%d", &n, &maxl);
for(int i = 1; i<=n; i++) {
int op,l,r;
scanf("%d%d%d",&op,&l,&r);
if(l > r) swap(l,r);
if(op == 1) {
if(ss[l].find(r)!=ss[l].end()) continue;
ss[l].insert(r);
for(int j = l; j<=r; j++) {
if(vis[j] == 0) ans++;
vis[j]++;
}
}
if(op == 2) {
if (ss[l].find(r)==ss[l].end()) continue;
ss[l].erase(r);
for(int j = l; j<=r; j++) {
if(vis[j] == 1) ans--;
vis[j]--;
}
}
if(op == 3) printf("%d\n",ans);
}
return 0 ;
} AC代码2：（扫描线）（100ms）
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
set<int> s[100005];
struct Tree {
int l,r;
int val;
int laz;
} tree[100005 * 4];
inline int len(int cur) {
return tree[cur].r - tree[cur].l + 1;
}
void pushup(int cur) {
if(tree[cur].laz > 0) tree[cur].val = len(cur);
else if (tree[cur].l == tree[cur].r) tree[cur].val = 0;
else tree[cur].val = tree[cur*2].val + tree[cur*2+1].val;
}
void pushdown(int cur) {
if(tree[cur].laz == 0) return ;
tree[cur*2].laz += tree[cur].laz;
tree[cur*2+1].laz += tree[cur].laz;
tree[cur*2].val += tree[cur].laz;
tree[cur*2+1].val += tree[cur].laz;
tree[cur].laz = 0;
}
void build(int l,int r,int cur) {
tree[cur].val=0;
tree[cur].l = l;
tree[cur].r = r;
if(l == r) return ;
int m = (l+r)>>1;
build(l,m,cur*2);
build(m+1,r,cur*2+1);
}
void update(int pl,int pr,int val,int cur) {
if(pl <= tree[cur].l && pr >= tree[cur].r) {
tree[cur].laz += val;
pushup(cur);
return ;
}
//pushdown(cur);
if(tree[cur*2].r >= pl) update(pl,pr,val,cur*2);
if(tree[cur*2+1].l <= pr) update(pl,pr,val,cur*2+1);
pushup(cur);
}
int main() {
int ans=0,N,maxL;
scanf("%d%d", &N, &maxL);
build(1,maxL,1);
while (N--) {
int opt, x, y;
scanf("%d%d%d", &opt, &x, &y);
if (x>y) swap(x,y);
if (opt == 1) {
if (s[x].find(y)!=s[x].end()) continue;
s[x].insert(y);
update(x,y,1,1);
}
if (opt == 2) {
if (s[x].find(y)==s[x].end()) continue;
s[x].erase(y);
update(x,y,-1,1);
}
if (opt == 3) {
printf("%d\n", tree[1].val);
}
}
return 0;
} AC代码3：（扫描线+pushdown版本）（应该是可以支持区间覆盖情况查询的）
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
set<int> s[100005];
struct Tree {
int l,r;
int val;
int laz;
} tree[100005 * 4];
inline int len(int cur) {
return tree[cur].r - tree[cur].l + 1;
}
void pushup(int cur) {
if(tree[cur].laz > 0) tree[cur].val = len(cur);
else if (tree[cur].l == tree[cur].r) tree[cur].val = 0;
else tree[cur].val = tree[cur*2].val + tree[cur*2+1].val;
}
void pushdown(int cur) {
if(tree[cur].laz == 0) return ;
tree[cur*2].laz += tree[cur].laz;
tree[cur*2+1].laz += tree[cur].laz;
// tree[cur*2].val += tree[cur].laz;
// tree[cur*2+1].val += tree[cur].laz;
// tree[cur].laz = 0;
}
void build(int l,int r,int cur) {
tree[cur].val=0;
tree[cur].l = l;
tree[cur].r = r;
if(l == r) return ;
int m = (l+r)>>1;
build(l,m,cur*2);
build(m+1,r,cur*2+1);
}
void update(int pl,int pr,int val,int cur) {
if(pl <= tree[cur].l && pr >= tree[cur].r) {
tree[cur].laz += val;
pushup(cur);
return ;
}
pushdown(cur);
if(tree[cur*2].r >= pl) update(pl,pr,val,cur*2);
if(tree[cur*2+1].l <= pr) update(pl,pr,val,cur*2+1);
pushup(cur);
}
int main() {
int ans=0,N,maxL;
scanf("%d%d", &N, &maxL);
build(1,maxL,1);
while (N--) {
int opt, x, y;
scanf("%d%d%d", &opt, &x, &y);
if (x>y) swap(x,y);
if (opt == 1) {
if (s[x].find(y)!=s[x].end()) continue;
s[x].insert(y);
update(x,y,1,1);
}
if (opt == 2) {
if (s[x].find(y)==s[x].end()) continue;
s[x].erase(y);
update(x,y,-1,1);
}
if (opt == 3) {
printf("%d\n", tree[1].val);
}
}
return 0;
} 标程：
我们考虑一种非常暴力的做法：对于这个数轴建出线段树，然后插入删除对应了区间加值操作。
我们来考虑一下询问操作：最朴素的方法是查询每个点是否有值然后统计答案。我们可以考虑对每一个线段树上的节点维护一个 min 值，这样遍历到一个节点的时候如果当前节点的 min > 0 那么说明这个线段树节点对应的区间是所有线段并的一部分。
当然这样的话还是不一定能过的，但是注意到数据随机生成，所以查询操作仅为总操作的1313 ，且删除操作大概率不会触发。
const int MAXN = 100000+5;
#define lc (x<<1)
#define rc (x<<1|1)
int min[MAXN<<2],tag[MAXN<<2];
inline void pushup(int x){
min[x] = std::min(min[lc],min[rc]);
}
inline void cover(int x,int l,int r,int delta){
min[x] += delta;
tag[x] += delta;
}
inline void pushdown(int x,int l,int r){
if(tag[x]){
int mid = (l + r) >> 1;
cover(lc,l,mid,tag[x]);
cover(rc,mid+1,r,tag[x]);
tag[x] = 0;
}
}
inline void modify(int x,int l,int r,int L,int R,int delta){
if(l == L && R == r){
cover(x,l,r,delta);
return;
}
pushdown(x,l,r);
int mid = (l + r) >> 1;
if(R <= mid) modify(lc,l,mid,L,R,delta);
else if(L > mid) modify(rc,mid+1,r,L,R,delta);
else modify(lc,l,mid,L,mid,delta),modify(rc,mid+1,r,mid+1,R,delta);
pushup(x);
}
inline int query(int x,int l,int r){
if(min[x] != 0) return r-l+1;
if(l == r) return min[x] != 0;
int mid = (l + r) >> 1;
pushdown(x,l,r);
return query(lc,l,mid)+query(rc,mid+1,r);
}
std::map<P,bool> S;
int L = 0;
int main(){
int N;scanf("%d%d",&N,&L);
while(N--){
int opt,x,y;scanf("%d%d%d",&opt,&x,&y);
if(opt == 1){
if(S[MP(x,y)]) continue;
S[MP(x,y)] = true;
// L = std::max(L,y);
modify(1,1,L,x,y,1);
}
if(opt == 2){
if(!S[MP(x,y)]) continue;
S[MP(x,y)] = false;
modify(1,1,L,x,y,-1);
}
if(opt == 3){
printf("%d\n",query(1,1,L));
}
}
return 0;
}
京公网安备 11010502036488号