Codeforces Round #361 (Div. 2) D
D - Friends and Subsequences
Description
Mike and !Mike are old childhood rivals, they are opposite in everything they do, except
programming. Today they have a problem they cannot solve on their own, but together
(with you) — who knows?
Every one of them has an integer sequences a and b of length n. Being given a query of
the form of pair of integers (l, r), Mike can instantly tell the value of while !Mike can
instantly tell the value of
.
Now suppose a robot (you!) asks them all possible different queries of pairs of integers
(l, r)(1 ≤ l ≤ r ≤ n) (so he will make exactlyn(n + 1) / 2 queries) and counts how many
times their answers coincide, thus for how many pairs is satisfied.
How many occasions will the robot count?
Input
The first line contains only integer n (1 ≤ n ≤ 200 000).
The second line contains n integer numbers a1, a2, ..., an ( - 109 ≤ ai ≤ 109) — the sequence a.
The third line contains n integer numbers b1, b2, ..., bn ( - 109 ≤ bi ≤ 109) — the sequence b.
Output
Print the only integer number — the number of occasions the robot will count, thus for how
many pairs is satisfied.
Sample Input
6
1 2 3 2 1 4
6 7 1 2 3 2
2
3
3 3 3
1 1 1
0
Hint
The occasions in the first sample case are:
1.l = 4,r = 4 since max{2} = min{2}.
2.l = 4,r = 5 since max{2, 1} = min{2, 3}.
There are no occasions in the second sample case since Mike will answer 3 to any query pair, but !Mike will always answer 1.
题意:
给出两个长为n的序列a和b,问有多少个区间[L,R]满足max<a>[L,R] == min<b>[L,R]。
分析:
枚举左端点,二分找到右端点可行区间的左右边界;二分右端点需要用RMQ(RQM预处理和查询
的相关知识点需要另外了解)。左边界:要是a>=b,左移;否则右移,找到第一个a=b的点;右边界:要
是a>b,左移,否则右移,找到最后一个a=b的点;最后累加右端点可行区间长度;
AC的代码:
#include <iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define LL long long
int rmq[][][];
void RMQ(int n)
{
for(int k = ; (<<k) <= n; ++k)
for(int i = ; i+(<<k) <= n; ++i)
{
rmq[][k][i] = max(rmq[][k-][i],rmq[][k-][i+(<<(k-))]);
rmq[][k][i] = min(rmq[][k-][i],rmq[][k-][i+(<<(k-))]);
}
}
int Search(int pos,int l,int r)
{
int k = log((r-l+)*1.0)/log(2.0);
if(pos) return min(rmq[pos][k][l],rmq[pos][k][r-(<<k)+]);
else return max(rmq[pos][k][l],rmq[pos][k][r-(<<k)+]);
} int main()
{
int n;
scanf("%d",&n);
for(int i=;i<n;i++)
scanf("%d",&rmq[][][i]);
for(int i=;i<n;i++)
scanf("%d",&rmq[][][i]);
RMQ(n);
LL ans=;
int l,r,a,b,s,e;
for(int i=;i<n;i++)
{
l=i;
r=n-;
s=-;
while(l<=r)
{
int mid=(l+r)/;
a=Search(,i,mid);
b=Search(,i,mid);
if(a>=b)
{
if(a==b) s=mid;
r=mid-;
}
else
l=mid+;
}
if(s==-) continue;
l=i;
r=n-;
e=-;
while(l<=r)
{
int mid=(l+r)/;
a=Search(,i,mid);
b=Search(,i,mid); if(a>b) r=mid-;
else
{
e=mid;
l = mid+;
}
}
ans+=(e-s+);
}
printf("%lld\n",ans);
return ;
}
另一种方法:
#include<bits/stdc++.h>
using namespace std;
int n,a[],b[];
long long ans;
deque<int>x,y;
int main()
{
scanf("%d",&n);
for(int i=; i<=n; i++) scanf("%d",&a[i]);
for(int i=; i<=n; i++) scanf("%d",&b[i]);
for(int i=,j=; i<=n; i++)
{
while(!x.empty()&&a[x.back()]<=a[i]) x.pop_back();
while(!y.empty()&&b[y.back()]>=b[i]) y.pop_back();
x.push_back(i);
y.push_back(i);
while(j<=i&&a[x.front()]-b[y.front()]>)
{
j++;
while(!x.empty()&&x.front()<j) x.pop_front();
while(!y.empty()&&y.front()<j) y.pop_front();
}
if(!x.empty()&&!y.empty()&&a[x.front()]==b[y.front()])
{
ans+=min(x.front(),y.front())-j+;
}
}
printf("%lld",ans);
}
最新文章
- Android 控件的显示隐藏上下左右移动动画
- Angular.JS + Require.JS + angular-async-loader 来实现异步加载 angular 模块
- C#之文本操作
- LXC docker
- 用Word收集网页中的内容,用文档结构图整理
- 理解C# Attribute
- 传统IO与NIO区别二
- base64自定义编码表 php版本
- Java创建、重命名、删除文件和文件夹(转)
- Trie/Xor
- HIVE安装配置
- 201521145048 《Java程序设计》第7周学习总结
- Wcf host
- OAuth2.0 授权码理解
- BZOJ5465 APIO2018选圆圈(KD-Tree+堆)
- HDU 6170 dp
- DWZ(JUI) 教程 跨域请求 iframeNavTab
- 调用webservices报错 原因是没有导入commons-logging和commons-discovery
- Django rest_framework 认证源码流程
- 【数据服务中间件】一、HttpServlet
热门文章
- css垂直居中方法盘点
- 《转载》Spring MVC之@RequestBody, @ResponseBody 详解
- iOS 编译时的警告导致无法通过编译
- Uiautomator--Uiselector元素定位
- 基于TXT文本的简单图书管理系统
- Java笔记:文件夹操作
- nodeJS(express4.x)+vue(vue-cli)构建前后端分离详细教程(带跨域)
- FragmentPagerAdapter加载fragment并使用setUserVisibleHint()处理预加载时遇到的坑,给textview赋值时出现的空指针异常
- display:table-cell的应用
- JS监听输入框值变化兼容 onpropertychange、oninput