标签：单调队列
题目
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;
