NC22593. 签到题
描述
#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.C++ 解法, 执行用时: 900ms, 内存消耗: 5212K, 提交时间: 2023-08-13 14:43:31
#include<bits/stdc++.h>
using namespace std;
map<pair<int,int>,bool> mp;
int a[100010],ans;
signed main(){
int n,L; scanf("%d%d",&n,&L);
while(n--){
int opt,l,r; scanf("%d%d%d",&opt,&l,&r);
if(opt==1){
if(mp[{l,r}]) continue; mp[{l,r}]=true;
for(int i=l;i<=r;i++) if(++a[i]==1) ans++;
}else if(opt==2){
if(!mp[{l,r}]) continue; mp[{l,r}]=false;
for(int i=l;i<=r;i++) if(--a[i]==0) ans--;
}else if(opt==3){
printf("%d\n",ans);
}
}
return 0;
}