整体二分+决策单调性

这个方法已经忘了...

决策单调性是指dp[i]由dp[1]->dp[i-1]更新,那么当dp[j]比dp[k]优且j>k时,对于i->n j都比k优

通过这个性质我们可以把dp优化到nlogn

具体做法是整体二分

solve(l,r,L,R)表示当前对于l->r的dp决策区间在L->R

那么我们选中(l+r)/2,并且枚举所有L->R满足的决策来更新,solve(l,mid-1,L,p) solve(mid+1,r,p,R)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+;
typedef long long ll;
int n;
int m;
ll ans;
struct data {
ll l, r;
data() {}
data(ll _l, ll _r) : l(_l), r(_r) {}
bool friend operator < (const data &a, const data &b) {
return a.l == b.l ? a.r > b.r : a.l < b.l;
}
} a[N], b[N];
ll calc(int i, int j)
{
return (b[j].r - b[i].l)*(b[i].r - b[j].l);
}
void cdq(int l, int r, int L, int R)
{
if(l > r) return;
int mid = (l+r)>>, lim = min(R, mid-), p=mid;
ll mx=;
for(int i=lim; i>=L; --i)
{
ll tmp = calc(i, mid);
if(tmp > mx)
{
p = i;
mx = tmp;
}
}
ans = max(ans, mx);
cdq(l, mid - , L, p);
cdq(mid + , r, p, R);
}
int main()
{
scanf("%d", &n);
for(int i = ; i <= n; ++i) scanf("%d%d", &a[i].l, &a[i].r);
sort(a + , a + n + );
int p = ;
for(int i = ; i <= n; ++i) if(a[i].r > a[p].r) b[++m] = a[i], p = i;
else ans = max(ans, (a[p].r - a[p].l) * (a[i].r - a[i].l));
cdq(, m, , m);
printf("%lld\n", ans);
return ;
}

最新文章

  1. ABP(现代ASP.NET样板开发框架)系列之1、ABP总体介绍
  2. iOS开发之使用XMPPFramework实现即时通信(一)
  3. HTML5 中的新属性autocomplete=&quot;off&quot;失效的解决方法(兼容firefox,IE,360)
  4. Atitti 图像处理 图像混合 图像叠加&#160;blend 原理与实现
  5. css取消input、select默认样式(手机端)
  6. 设计模式之三:单例模式singleton
  7. Java RMI 框架_远程方法调用(2016-08-16)
  8. 使用jquery-mockjax模拟ajax请求做前台測试
  9. 属性动画之ValueAnimator
  10. IT研发工程师职业规划
  11. MySQL数据库事务及其特性
  12. mvc自定义分页(加页数的)(转)
  13. Matplotlib学习---用matplotlib画面积图(area chart)
  14. Weblogic的安装与卸载
  15. Jmeter安装与配置
  16. tiny4412SDK 1312B 启动ubuntuDsektop
  17. 【附5】springboot之配置文件
  18. ACM大牛的BLOG(转)
  19. Elasticsearch 统计代码例子
  20. MySQL查询操作select

热门文章

  1. Mysql导出大量数据
  2. leetCode(40):Path Sum
  3. Unity光滑与粗糙的材质——相似于生锈的金属表面
  4. Kuebernetes之DaemonSet
  5. Sass编译css/Grunt压缩文件
  6. Linux命令之ln软链接
  7. JS/PHP字符串截取
  8. HDU 6074 Phone Call LCA + 并查集
  9. 【BZOJ4950】lydsy七月月赛 C 二分图最大匹配
  10. Routine Subroutine Coroutine 子程序 协程