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