@
Description
有一面长为 \(n\) 的墙以及 \(q\) 个工人，第 \(i\) 个工人粉刷 \(l_i\) 到 \(r_i\) 的墙面，现在要去掉两个工人，问剩余 \(q-2\) 个工人最多能粉刷多少墙面。
Solution
注意数据，\(n\le5\times10^3\)，所以可以暴力枚举两个被去掉的工人。
对于被去掉的两个工人，他们的粉刷部分有三种情况：
- 没有相交
- 部分相交
- 完全相交（即小的区间在大的区间内）
可以先对每个工人的粉刷区间进行从左到右的排序，降低分类讨论复杂度。
如果一面墙被这两个人都刷了，那么它至少要刷 3次，才不会被去到，如果只有一个人刷得到，只需刷到2次就不会被去掉。
所以我们记录每一个区间的 \(ans_1,ans_2\)，表示这个区间内刷过次数在一次及以下的墙数（一个人刷过就被去掉）和在两次及以下的墙数（两个人都刷过才会去掉）。
那么每一次用总墙数减去相交部分的 \(ans_2\)，再减去单独部分的 \(ans_1\)，就是剩余的墙数。
考虑如何维护 \(ans_1,ans_2\)。
本质上就是区间查询，用前缀和，树状数组都能做，线段树会因为常数大而被卡掉。
这里给出树状数组做法。
Code
#include<bits/stdc++.h>
using namespace std;
int n,q;
int cnt[5050];
struct node{
int l,r;
}a[5050];
struct tree{
int ans1,ans2;
}tr[5050];
int lowbit(int x){
return x&(-x);
}
void add(int x,int opt){
for(int i=x;i<=n;i+=lowbit(i)){
if(opt==1) tr[i].ans1++;
else tr[i].ans2++;
}
}
int query(int x,int opt){
int ans=0;
for(int i=x;i>=1;i-=lowbit(i)){
if(opt==1) ans+=tr[i].ans1;
else ans+=tr[i].ans2;
}
return ans;
}
void build(){
for(int i=1;i<=n;i++){
if(cnt[i]<=1) add(i,1),add(i,2); //ans2也包括ans1
else if(cnt[i]==2) add(i,2);
}
}
bool cmp(node x,node y){ //对粉刷区间排序
if(x.l==y.l) return x.r<y.r;
return x.l<y.l;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>q;
int tot=0;
for(int i=1;i<=q;i++){
cin>>a[i].l>>a[i].r;
for(int j=a[i].l;j<=a[i].r;j++){
if(!cnt[j]) tot++; //求总墙数
cnt[j]++;
}
}
build();
sort(a+1,a+1+q,cmp);
int maxn=-10;
for(int i=1;i<=q;i++){
for(int j=i+1;j<=q;j++){
int sum=0;
if(a[i].l<=a[j].l&&a[j].r<=a[i].r){ //完全相交，由于已经排过序，所以只有可能是i包含j
if(a[i].l<a[j].l){ //当两个重叠的时候是不计算的
sum+=query(a[j].l-1,1)-query(a[i].l-1,1);
}
if(a[j].r<a[i].r){
sum+=query(a[i].r,1)-query(a[j].r,1);
}
sum+=query(a[j].r,2)-query(a[j].l-1,2);
}else if(a[i].r>=a[j].l){ //部分相交
if(a[i].l<a[j].l){
sum+=query(a[j].l-1,1)-query(a[i].l-1,1);
}
if(a[i].r<a[j].r){
sum+=query(a[j].r,1)-query(a[i].r,1);
}
sum+=query(a[i].r,2)-query(a[j].l-1,2);
}else{ //不相交
sum+=query(a[i].r,1)-query(a[i].l-1,1);
sum+=query(a[j].r,1)-query(a[j].l-1,1);
}
maxn=max(maxn,tot-sum);
}
}
cout<<maxn<<endl;
return 0;
}