[Contest20171109]函数(lipshitz)
大M正在学习函数的光滑性并对Lipshitz常数非常感兴趣:当一个定义域为$[l,r]$的函数$f$,对于定义域内的任意$x,y$都有$\left|f(x)-f(y)\right|\leq K\cdot\left|x-y\right|$时,则称$K$的最小值为该函数在$[l,r]$上的Lipshitz常数。
然而大M并不满足于函数,所以他定义:对于一个序列$v_{1\cdots n}$,当$1\leq x\lt y\leq n$且$x,y$均为整数时,同样满足$\left|v_x-v_y\right|\leq K\cdot\left|x-y\right|$,则称$K$的最小整数值为序列$v$的Lipschitz常数。
现在给你一个长度为$n$的序列$v_{1\cdots n}$并给出$q$个询问,对于每对询问$[l,r]$,你需要求出$v_{l\cdots r}$的所有子序列$v_{x\cdots y}(l\leq x\lt y\leq r)$的Lipshitz常数之和。这可难不倒会编程的你。
$n\leq 10^5,q\leq 100$
转换一下,$K=max\left\{\dfrac{\left|v_x-v_y\right|}{\left|x-y\right|}\right\}$
题解给了一个结论:最终的答案一定是某长度为$2$的子序列,还说“这么简单,不予证明”,但还是得证一下的
用归纳法,若(长度为$2\cdots n$的序列的答案)都由长度为$2$的子序列产生,我们将要证明:长度为$n+1$的序列答案也由长度为$2$的子序列产生
设它是$a_{1\cdots n+1}$,若答案为它本身而不是其他子序列,那么$a_1$和$a_{n+1}$一个是最小一个是最大,不妨设$a_1\lt a_{n+1}$
那么这个序列的Lipshitz常数为$\dfrac{a_{n+1}-a_1}n$,因为其他长度的子序列的答案都由长度为$2$的子序列产生,那么对$1\leq i\leq n$,都有$\dfrac{a_{n+1}-a_1}n\gt\left|a_i-a_{i+1}\right|$
把这$n$个不等式加起来,得$a_{n+1}-a_1\gt \left|a_1-a_2\right|+\cdots+\left|a_n-a_{n+1}\right|$
整理,得$a_2+\left|a_2-a_3\right|+\cdots+\left|a_{n-1}-a_n\right|-a_n\lt 0$
移一下绝对值外的,再补上几项,得$a_n-a_{n-1}+\cdots+a_3-a_2\gt\left|a_n-a_{n-1}\right|+\cdots+\left|a_3-a_2\right|$
一个数取绝对值后不会变小,所以这里显然矛盾,原命题得证
因为长度为$2$的序列的答案显然长度为$2$,所以对于任意$n\geq 2$,长度为$n$的序列,答案都由长度为$2$的子序列产生
证完结论,我们来找答案
先处理处所有长度为$2$的子序列的答案:$d_i=\left|v_i-v_{i+1}\right|$
那么$v_{l\cdots r}$的Lipshitz常数为$max\left\{d_{l\cdots r-1}\right\}$
预处理出每个$d_i$向左最远能做哪些区间的最大值($\geq$),向右最远能做哪些区间的最大值($\gt$)(一个大于等于一个大于是为了不重不漏覆盖所有答案),这里用ST表预处理,再二分即可
然后每次询问就$O(n)$统计一下即可
#include<stdio.h> #define ll long long int f[100010][17],log2[100010],right[100010],left[100010]; int abs(int x){return x>0?x:-x;} int max(int a,int b){return a>b?a:b;} int min(int a,int b){return a<b?a:b;} int query(int l,int r){ int k=log2[r-l+1]; return max(f[l][k],f[r-(1<<k)+1][k]); } int main(){ int n,q,i,j,l,r,mid,ans; ll res; scanf("%d%d",&n,&q); for(i=1;i<=n;i++)scanf("%d",f[i]); log2[1]=0; for(i=2;i<=n;i++)log2[i]=log2[i>>1]+1; n--; for(i=1;i<=n;i++)f[i][0]=abs(f[i][0]-f[i+1][0]); for(j=1;j<17;j++){ for(i=1;i<=n;i++){ f[i][j]=f[i][j-1]; if(i+(1<<(j-1))<=n)f[i][j]=max(f[i][j],f[i+(1<<(j-1))][j-1]); } } for(i=1;i<=n;i++){ l=i+1; r=n; ans=i; while(l<=r){ mid=(l+r)>>1; if(query(i+1,mid)<=f[i][0]){ ans=mid; l=mid+1; }else r=mid-1; } right[i]=ans; l=1; r=i-1; ans=i; while(l<=r){ mid=(l+r)>>1; if(query(mid,i-1)<f[i][0]){ ans=mid; r=mid-1; }else l=mid+1; } left[i]=ans; } while(q--){ scanf("%d%d",&l,&r); r--; res=0; for(i=l;i<=r;i++)res+=(i-max(l,left[i])+1)*(ll)(min(r,right[i])-i+1)*(ll)f[i][0]; printf("%lld\n",res); } }
最新文章
- C#与Java在继承静态类上的区别
- sqlite3无法找到
- Linux文件操作 笔记
- IOS SizeClasses 详解
- Linux sort --copy
- 客户端无法tcp连接上本地虚拟机的问题(最后是linux防火墙问题)
- 问题:LVM lvextend增加空间后,df查看还是原来空间
- codeforces 687C - The Values You Can Make 简单dp
- 【Tools】Chrome 控制台不完全指南
- OD: Shellcode Encoding
- Windows消息传递函数SendMessage参数属性
- MFC画二维动态图表[GDI]
- spring中bean的设计模式
- 提高PHP编程效率的方法
- ASP.NET MVC+EF框架+EasyUI实现权限管理系列(12)-实现用户异步登录和T4模板
- assert的基本用法
- 简述C/C++调用lua中实现的自定义函数
- sql xml中 in 的用法
- F - JDG HDU - 2112 (最短路)&;&; E - IGNB HDU - 1242 (dfs)
- shim和polyfill
热门文章
- SICAU-OJ:要我唱几首歌才能够将你捕捉
- eclipse集成mybatis的generater插件
- tengine的安装
- 正式进入搭建OpenStack
- Intelij idea新窗口打开项目设置
- 【Foreign】远行 [LCT]
- [BZOJ3238][Ahoi2013]差异解题报告|后缀数组
- [BZOJ1036][ZJOI2008]树的统计Count 解题报告|树链剖分
- Python爬虫学习 - day1 - 爬取图片
- Atos cannot get symbols from dSYM of archived application