题目 https://codeforces.com/problemset/problem/1132/C

参考了 http://www.pianshen.com/article/4932273340/ 这位巨巨的代码 思路非常清晰,没什么好说的了 自己太菜了 疯狂wa

#include<cstdio> #include<cstring> #include<cmath> #include<string> #include<iostream> #include<vector> #include<map> #include<set> #include<stack> #include<queue> #include<stdlib.h> #include<algorithm> #include<time.h> #define bug1(g) cout<<"test: "<<g<<endl #define bug2(g,i) cout<<"test: "<<g<<" "<<i<<endl #define bug3(g,i,k) cout<<"test: "<<g<<" "<<i<<" "<<k<<endl using namespace std; typedef long long ll; int n,q; int a[5005],l[5005],r[5005]; int s[5][5005],maxx,ans; int get(int l,int r,int i) { return s[i][r]-s[i][l-1]; } int main() { cin>>n>>q; for(int i =1;i<=q;i++) { cin>>l[i]>>r[i]; for(int j=l[i];j<=r[i];j++) { ++a[j]; } } for(int i =1;i<=n;i++) { if(a[i]<=2) for(int j=i;j<=n;j++) s[a[i]][j]++; } for(int i =1;i<=q;i++) { for(int j =i+1;j<=q;j++) { int tmp=n; tmp-=get(1,n,0); tmp-=get(l[i],r[i],1); tmp-=get(l[j],r[j],1); int ll =max(l[i],l[j]),rr=min(r[i],r[j]); if(ll<=rr) { tmp-=get(ll,rr,2); } ans=max(ans,tmp); } } cout<<ans<<endl; return 0; }