【Educational Codeforces Round 61 (Rated for Div. 2) C.Painting the Fence】前缀和

C.Painting the Fence

题意

给你$n$个线段，选出其中$n?2$条线段，让他们覆盖的线段最长。

$3\le n,q\le 5000$

做法

首先算出两个前缀和，第一个前缀和为到i为止被覆盖一次的线段有多少，第二个前缀和为到i为止被覆盖一次的线段有多少。之后暴力美剧要删除哪两条线段，我们首先在所有覆盖点中把这两条线段中被覆盖一次的点删除，之后再把两条线段重合部分被覆盖两次的点删除就是答案。

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 3e5+5;
int a[maxn],cnt[maxn];
int l[maxn],r[maxn];
int sum[2][maxn];
int main()
{
    int n,q;scanf("%d%d",&n,&q);for(int i=1;i<=q;i++){
    scanf("%d%d",&l[i],&r[i]);for(int j=l[i];j<=r[i];j++) cnt[j]++;}int ans=0;int tmp=0;for(int i=1;i<=n;i++){
    if(cnt[i]==1) sum[0][i]=sum[0][i-1]+1;else sum[0][i]=sum[0][i-1];if(cnt[i]==2) sum[1][i]=sum[1][i-1]+1;else sum[1][i]=sum[1][i-1];if(cnt[i]) tmp++;}for(int i=1;i<=q;i++){
    for(int j=i+1;j<=q;j++){
    int now=tmp-(sum[0][r[i]]-sum[0][l[i]-1])-(sum[0][r[j]]-sum[0][l[j]-1]);int ll=max(l[i],l[j]);int rr=min(r[i],r[j]);if(ll<=rr) now-=sum[1][rr]-sum[1][ll-1];ans=max(ans,now);}}printf("%d",ans);return 0;
}