以[BZOJ2687]交与并为例给出代码。

#include <bits/stdc++.h>

#define rin(i,a,b) for(register int i=(a);i<=(b);++i)
#define irin(i,a,b) for(register int i=(a);i>=(b);--i)
#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)
#define Size(a) (int)a.size()
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
typedef long long LL;

using std::cerr;
using std::endl;

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

const int MAXN=1000005;

int n,tot;
LL ans;

struct seg{
    int l,r;
    inline friend bool operator < (seg x,seg y){
        return x.l==y.l?x.r>y.r:x.l<y.l;
    }
}a[MAXN],b[MAXN];

inline LL calc(seg x,seg y){
    if(x.r<=y.l)return 0;
    return 1ll*(y.r-x.l)*(x.r-y.l);
}

int bit[MAXN];
inline void ins(int x,int y){for(register int i=x;i<=1e6;i+=lowbit(i))bit[i]=std::max(bit[i],y);}
inline int ask(int x){int ret=0;for(register int i=x;i;i-=lowbit(i))ret=std::max(ret,bit[i]);return ret;}

int hd,tl;

struct Opt{
    int j,l,r;
}q[MAXN];

int main(){
    n=read();
    rin(i,1,n)a[i].l=read(),a[i].r=read();
    std::sort(a+1,a+n+1);
    int maxr=0;
    rin(i,1,n){
        if(a[i].r<=maxr){
            ans=std::max(ans,1ll*(a[i].r-a[i].l)*ask(1e6-a[i].r+1));
            continue;
        }
        maxr=a[i].r;
        b[++tot]=a[i];
        ins(1e6-a[i].r+1,a[i].r-a[i].l);
    }
    n=tot;hd=tl=1;q[1]=(Opt){1,2,n};
    rin(i,2,n){
        int j=q[hd].j;
        ans=std::max(ans,calc(b[j],b[i]));
        ++q[hd].l;if(q[hd].l>q[hd].r)++hd;
        int pos=0;
        while(1){
            if(hd>tl){pos=i+1;break;}// 当队列为空时直接插入
            int jt=q[tl].j,lt=q[tl].l,rt=q[tl].r;
            if(calc(b[i],b[rt])<calc(b[jt],b[rt])){pos=rt+1;break;}// 在q[tl].r处严格劣于队尾决策时插入队尾
            else if(calc(b[i],b[lt])>=calc(b[jt],b[lt])){--tl;continue;}// 在q[tl].l处不劣于队尾决策时删除队尾
            else{
                int l=lt,r=rt;
                while(l<=r){
                    int mid=((l+r)>>1);
                    if(calc(b[i],b[mid])>=calc(b[jt],b[mid]))pos=mid,r=mid-1;// 找到队尾决策所对应区间中第一个不劣于队尾决策的位置
                    else l=mid+1;
                }
                q[tl].r=pos-1;// 更新队尾决策所对应区间的右端点
                break;
            }
        }
        if(pos<=n)q[++tl]=(Opt){i,pos,n};
    }
    printf("%lld\n",ans);
    return 0;
}