Skip to content

11278: 【原1278】continuous

题目

题目描述

author: syj和Cheezer 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1278

Description

给定一个数字n和大小为n的布尔数组ai,一开始对所有i都有a[i]=true。

给m个询问,第i个询问包含两个参数Li和Ri,请找出aj的每一段连续true的个数,若有r段连续的true,第k段长为b[k],则第i次询问的答案ans[i]为 \( \sum_{k=1}^r (b[k])^2 \) 。并把aj置为false。

比如对于第i个询问,a = {true, true, true, false, true, false, true}, Li=2, Ri=7,由于有3段连续的true,第一段为a[2]到a[3],第二段为a[5]到a[5],第三段为a[7]到a[7],长度分别为2,1,1.则 \( ans[i] = 2^2+1^2+1^2=6 \) 。

请你需要 \( \sum_{i=1}^m ans[i] \) 。

Input Format

第一行为n和m,意义如描述之所示。

接下来m行,每行两个数Li,Ri。

对于40%的数据,n,m<=1000

对于70%的数据,n,m<=50000

对于100%的数据,n,m<=300000,Li<=Ri

Output Format

一行,即答案 \( \sum_{i=1}^m ans[i] \) 。

Sample Input

14 2
4 9
2 12

Sample Output

49

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!