大意: n*n棋盘, n个点有怪兽, 求有多少边长为k的正方形内恰好有k只怪兽, 输出k=1,...,n时的答案和.

等价于给定n排列, 对于任意一个长为$k$的区间, 若最大值最小值的差恰好为k, 则产生1贡献, 求贡献和.考虑分治, 问题就转化为如何$O(n)$求出跨越$mid$的贡献, 可以讨论最大值最小值的位置, 双指针求出.

#include <iostream>
#include <algorithm>
#include <cstdio>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
using namespace std;
typedef long long ll; const int N = 1e6+10;
int n, a[N], mx[N], mi[N];
int ff[N<<1], *f=ff+N;
ll ans;
void solve(int l, int r) {
if (l==r) return ++ans,void();
int mid = l+r>>1;
solve(l,mid),solve(mid+1,r);
mx[mid]=mi[mid]=a[mid];
mx[mid+1]=mi[mid+1]=a[mid+1];
REP(i,mid+2,r) mx[i]=max(mx[i-1],a[i]),mi[i]=min(mi[i-1],a[i]);
PER(i,l,mid-1) mx[i]=max(mx[i+1],a[i]),mi[i]=min(mi[i+1],a[i]);
int L = mid, R = mid;
REP(i,mid+1,r) {
int j=i-mx[i]+mi[i];
if (l<=j&&j<=mid&&mx[j]<mx[i]&&mi[j]>mi[i]) ++ans;
while (L>=l&&mx[L]<mx[i]) ++f[mi[L]-L],--L;
while (R>L&&mi[R]>mi[i]) --f[mi[R]-R],--R;
ans += f[mx[i]-i];
}
while (R!=L) --f[mi[R]-R],--R;
L = R = mid+1;
PER(i,l,mid) {
int j=mx[i]-mi[i]+i;
if (mid+1<=j&&j<=r&&mx[j]<mx[i]&&mi[j]>mi[i]) ++ans;
while (R<=r&&mx[R]<mx[i]) ++f[mi[R]+R],++R;
while (L<R&&mi[L]>mi[i]) --f[mi[L]+L],++L;
ans += f[mx[i]+i];
}
while (L!=R) --f[mi[L]+L],++L;
} int main() {
scanf("%d", &n);
REP(i,1,n) {
int x, y;
scanf("%d%d", &x, &y);
a[x] = y;
}
solve(1,n);
printf("%lld\n", ans);
}

最新文章

  1. C# 生成验证码图片时消除锯齿
  2. django 在字符串[str(list)]中精确查找
  3. 使用Java数组实现双色球选号
  4. 夺命雷公狗---Thinkphp----15之遍历出来的栏目页的完成
  5. Deep Learning 初识
  6. Hibernate中save、saveorupdate、persist方法的区别
  7. 微信小程序中发送模版消息注意事项
  8. JVM学习记录-对象已死吗
  9. High Availability手册(1): 环境
  10. 修改帝国cms栏目后,如何更新
  11. Linux下自动清理超过指定大小文件
  12. git的基本用法
  13. golang结构体、接口、反射
  14. Python学习——web框架
  15. Uni2D入门
  16. Installing OpenSSH from the Settings UI on Windows Server 2019 or Windows 10 1809
  17. Android开发之使用DefaultHandler处理XML数据
  18. javascript关于onclick()
  19. mongodb的学习笔记一(集合和文档的增删改查)
  20. ready 事件 DOM(文档对象模型) 已经加载....

热门文章

  1. android 控件获取 获取焦点
  2. P4720 【模板】扩展卢卡斯
  3. Shiro学习笔记 三(认证授权)
  4. 查看kubernets上的image信息
  5. oracle 新建用户
  6. Python 一个抓取糗百的段子的小程序
  7. 【一】php 基础知识
  8. Python 3种运行方式
  9. R 的内部机制
  10. 基于反射实现实体DTO映射