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个和第3个区间,交为(2,6),并为(1,7),权值为4*6=24.

分析

显然,在合并过程中对于被包含的区间,对答案一定不产生贡献

先排序去掉那些被包含的区间

发现决策具有单调性,然后就可以通过单调队列优化了

两个指针扫一遍就结束

对于特殊的情况比如

1 5 2 3

用上面的方法求肯定为0,所以我们在去重区间的时候也要更新答案

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;
inline ll read()
{
	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()
{
	n=read();
	rep(i,1,n)l[i]=read(),r[i]=read(),maxlen=max(maxlen,r[i]);
	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;
inline ll read()
{
	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()
{
	n=read();
	rep(i,1,n)a[i].l=read(),a[i].r=read();
	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;

本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr