cncnk205634848 @ 2024-12-23 22:35:39
用的珂朵莉树，样例1RE，样例2WA，AC关注
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
int l,r;
mutable int v;
bool operator<(const node&d) const{
return l<d.l;
}
};
node d;
set<node> s;
set<node>::iterator it;
void split(int k){
set<node>::iterator it1;
for(it1=s.begin();it1!=s.end();it1++){
if((*it1).l<=k&&(*it1).r>=k){
break;
}
}
int ll=(*it1).l;
int rr=(*it1).r;
int vv=(*it1).v;
s.erase(it1);
d.l=ll;
d.r=k;
d.v=vv;
s.insert(d);
d.l=k+1;
d.r=rr;
s.insert(d);
}
void tp(const int&x,const int&y){
split(x-1);
split(y-1);
set<node>::iterator itl;
set<node>::iterator itr;
for(it=s.begin();it!=s.end();it++){
if((*it).l==x){
itl=it;
}
else if((*it).l==y){
itr=it;
}
}
s.erase(itl,itr);
d.l=x;
d.r=y;
d.v=0;
s.insert(d);
}
int main(){
int cnt=0;
cin>>n>>m;
d.l=1;
d.r=n;
d.v=1;
s.insert(d);
for(int i=1;i<=m;i++){
int l,r;
cin>>l>>r;
tp(l,r);
}
set<node>::iterator pq;
for((pq)=s.begin();(pq)!=s.end();pq++){
if((*pq).v==1){
cnt+=((*pq).r-(*pq).l+1);
}
}
cout<<(cnt);
return 0;
} by wangshengchen @ 2024-12-23 23:26:24
#include<iostream>
using namespace std;
int main()
{
const int N=1e4+10;
int l,m,a[N]={0},ans=0;
cin>>l>>m;
for(int i=0;i<m;i++) {
int u,v;
cin>>u>>v;
a[u]++;
a[v+1]--;
}
for(int i=1;i<=l;i++) a[i]+=a[i-1];
for(int i=0;i<=l;i++) if(!a[i]) ans++;
cout<<ans;
return 0;
}
//例如
//输入10 3
//1 3
//1 9
//2 4
//a{0,2,1,0,-1,-1,0,0,0,0,-1}
//a{0,2,3,3,2,1,1,1,1,0}
//ans+1(2)+1(3)+1(3)+1(2)+1(1)+1(1)+1(1)+1(1)
//ans=8求关
by wangshengchen @ 2024-12-23 23:29:22
@cncnk205634848
//例如
//输入10 3
//1 3
//1 9
//2 4
//a{0,2,1,0,-1,-1,0,0,0,0,-1}
//a{0,2,3,3,2,1,1,1,1,0}
//ans+1(下标0)+1(下标10)
//ans=2by cncnk205634848 @ 2024-12-24 18:52:39
谢谢