首页 > 其他分享 >[ABC305D] Sleep Log题解

[ABC305D] Sleep Log题解

时间:2023-06-13 09:44:05浏览次数:41  
标签:lower int 题解 cin ABC305D bound 睡觉 Sleep ans

题目大意

给 \(N\) 个时刻:

  • 当 \(i\) 为奇数时,\(A_i\) 表示刚刚起床的时刻。
  • 当 \(i\) 为偶数时,\(A_i\) 表示开始睡觉的时刻。

有 \(Q\) 次询问,每次求在 \([l,r]\) 区间内睡了多长时间。

分析

首先我们要考虑处理边界情况。

每一次二分查找第一个大于等于 \(l\) 和 \(r\) 的时刻 \(x\) 和 \(y\)。

分别判断 \(x\) 和 \(y\) 是起床还是开始睡觉。

  • 如果是起床,则说明上一段时间正在睡觉,就记录贡献。
  • 如果是开始睡觉,则说明上一段时间未睡觉,就不用管。

处理完边界条件后就只需要处理中间整段的睡觉时间。

这个用一个前缀和维护即可。

具体细节请看代码。

Code

#include<bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;
int n,Q,a[N];
int p[N];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		p[i]+=p[i-1];//前缀和
		if(i%2==1)p[i]+=a[i]-a[i-1];
	}
	cin>>Q;
	while(Q--){
		int l,r,ans=0;
		cin>>l>>r;
		int x=lower_bound(a,a+n,l)-a;//lower_bound查找下一个时刻
		int y=lower_bound(a,a+n,r)-a;
		if(x%2==1)ans+=a[x]-l;//判断边界贡献
		if(y%2==1)ans+=r-a[y-1];
		ans+=p[y-1]-p[x];//处理中间部分
		cout<<ans<<endl;
	}
	return 0;
}

标签:lower,int,题解,cin,ABC305D,bound,睡觉,Sleep,ans
From: https://www.cnblogs.com/OIerBoy/p/17476630.html

相关文章

  • VM虚拟机模板,克隆或导入后网络不通问题解决办法
    出于工作需要可能需要对VM虚拟机制作模板,并导出为.vof文件,并根据vof模板文件导入为新的虚拟机,但是当导入后会发现网络不通,现将网络问题解决办法进行记录:本次实验OS为Centos7,网卡默认配置文件名为ifcfg-ens331.保留默认网卡网卡目录:/etc/sysconfig/network-scripts/保留默认......
  • CF113B Petr# 题解
    最近在做字符串的题,正好就给我随机了一道这个(题意给你一个字符串\(s\)以及一个开头串\(s_{begin}\)和结尾串\(s_{end}\),问该字符串中有多少个不同的子串,满足以\(s_{begin}\)开头,以\(s_{end}\)结尾。两个子串不同,当且仅当两个子串长度不同,或长度相同但至少有一个位置上......
  • 【P8819 [CSP-S 2022]】 星战 题解(图论 + 哈希)
    图论+哈希。Link.因为实在是太妙了所以写个题解。Solution因为每个点的出度都为\(1\),所以从任意一点出发永远可以走下去,故每次只需判断每个点度数是否为\(1\)即可。然后一三操作显然直接\(O(1)\)维护,\(50\pts\)。考虑二四操作。每次操作显然对点\(u\)的出度......
  • [ABC212E] Safety Journey 题解
    SafetyJourney题目大意给定一张缺少了\(m\)条边的\(n\)个点的完全图和一个正整数\(k\),你需要求出满足以下条件的序列\(A\)的数量:\(A\)的长度为\(k+1\)。\(A_0=A_k=1\)。\(\forall0\lei\lek-1\),点\(A_i\)和点\(A_{i+1}\)之间存在边。思路分析图上计数,考......
  • Codeforces Round 877 (Div.2) 题解 A - D
    A.BlackboardList题目大意起初黑板上有两个数,现在不断选取两个数作出他们俩差的绝对值并写在黑板上,如此往复直到黑板上有\(n\)个数。现在给定这\(n\)个数,问起初两数的其中一个数是多少。解题思路我们分两种可能:要么这两个数有负数,要么没有。有负数的情况,因为每次写下......
  • P1707 刷题比赛 题解
    多少有点混乱邪恶。题意:给出递推式:\[a_1=b_1=c_1=1\\a_2=b_2=c_2=3\\\begin{aligned}a_k&=p\timesa_{k-1}+q\timesa_{k-2}&+b_{k-1}+c_{k-1}&+r(k-2)^2+t(k-2)+1\\b_k&=u\timesb_{k-1}+v\timesb_{k-2}&+a_{k-1}+c_{k-1}&+w^{k-2}\\c......
  • P1306 斐波那契公约数 题解
    请求出\(f_n\)与\(f_m\)的最大公约数,即\(\gcd(f_n,f_m)\),答案对\(10^8\)取模。结论:\(\gcd(f_n,f_m)=f_{\gcd(n,m)}\)证明如下:首先引理1:\[f_{n+m}=f_{n-1}\timesf_{m}+f_{n}\timesf_{m+1}\]运用归纳法,可以简单证明,此处略去。引理2:\[\gcd(f_n,f_......
  • AtCoder Beginner Contest 305 题解
    https://atcoder.jp/contests/abc305/tasks_printE-ArtGalleryonGraph冷知识:md这题赛时没做出来/cy刚看到题:这是什么题啊,\(K,h\)都\(1e5\)能做吗/fn确实能做。考虑类似SPFA的操作。设\(a_x\)表示\(x\)还可以对距离最多为\(a_x\)的点产生贡献,然后就直接......
  • Codeforces Round 876 Div2 A-D题解
    CodeforcesRound876Div2A-D题解A.TheGoodArray这个题就是问你对于\(i\leqn\),要求前面后面至少\(ceil(\frac{i}{k})\)个1那我们就贪心的每k个放一个1,或者直接用数学算一下就好了AC代码#include<bits/stdc++.h>usingnamespacestd;constexprintlimit=(......
  • Java8新特性Stream之list转map及问题解决
    List集合转Map,用到的是Stream中Collectors的toMap方法:Collectors.toMap具体用法实例如下://声明一个List集合Listlist=newArrayList();list.add(newPerson("1001","小A"));list.add(newPerson("1002","小B"));list.add(......