# BZOJ2687 交与并

Posted by yjjr's blog on January 1, 2018

# 题目

Description 对于一个区间集合{A1,A2……AK}(K>1，Ai<>Aj{i<>j})，我们定义其权值 W=|A1∪A2∪……∪AK|*|A1∩A2∩……AK|当然，如果这些区间没有交集则权值为0。 Input 给你N个（1< N<=10^6）各不相同的区间，请你从中找出若干个区间使其权值最大。 第一行N,接下来N行 l r(1<=l < r<=10^6)

Output 最大权值

Sample Input 4

1 6

4 8

2 7

3 5 Sample Output 24

1 5 2 3

# code

10分暴力（我已经弱到连10分暴力都写了）

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=36,maxl=1e6+6;
int n,book[maxn],ans=0,pos,maxlen=0,tot,t1,t2,cnt;
int l[maxn],r[maxn],markb[maxl],markj[maxl];

bool check(){
tot=0;
rep(i,1,n)
if(book[i]==1)tot++;
if(tot<=1)return 0;
else return 1;
}
int work(){
t1=0,t2=0,cnt=0;
mem(markb,0);mem(markj,0);
rep(i,1,n)
if(book[i]==1)
rep(j,l[i],r[i])markb[j]=1,markj[j]++;
rep(i,1,maxlen){
if(markb[i]==1&&markb[i-1]==0)cnt++;
if(markb[i]==1)t1++;
if(markj[i]==tot)t2++;
}
return max(0,(t1-cnt))*max((t2-1),0);
}

int main()
{
mem(book,0);ans=0;
while(book[n+1]==0){
rep(i,1,n+1)if(book[i]==0){pos=i;break;}
book[pos]=1;rep(i,1,pos-1)book[i]=0;
if(check())ans=max(ans,work());
rep(i,1,n)cout<<book[i];cout<<endl;
cout<<work()<<endl;rep(i,1,100)cout<<markb[i]<<' ';cout<<endl;rep(i,1,100)cout<<markj[i]<<' ';cout<<endl;cout<<tot<<' '<<cnt<<' '<<t1<<' '<<t2<<"E\n";
}
cout<<ans<<endl;
return 0;
}



#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e6+6;
int n,now,mx,l,flag[maxn];
ll ans;
struct node{int l,r;}a[maxn],b[maxn];
inline bool cmp(node a,node b){return a.l==b.r?a.r<b.r:a.l<b.l;}

ll get(int i,int j){
return b[i].r<b[j].l?0:1LL*(b[i].r-b[j].l)*(b[j].r-b[i].l);
}

int main()
{
sort(a+1,a+n+1,cmp);
rep(i,1,n){
if(a[i].r<=now){
flag[i]=mx;
ans=max(ans,1LL*(a[i].r-a[i].l)*(a[mx].r-a[mx].l));
}else flag[i]=0;
if(now<a[i].r)now=a[i].r,mx=i;
}
l=0;
rep(i,1,n)if(!flag[i])b[++l]=a[i];
now=2;
rep(i,1,l-1){
if(now==i)now++;
while(now<=l-1&&get(i,now)<get(i,now+1))now++;
ans=max(ans,get(i,now));
}
cout<<ans<<endl;
return 0;