本文写于2022-03-26 14:45:14。原博客地址
算法
(倍增) $O((n+q) \log n)$
为简便,把元素 $(a_i,b_i)$ 称为元素 $i$。
对一个区间 $[l,r]$ 模拟一遍,从空栈开始,头一个元素是“成功的”,然后堵在栈底直到被弹出,这期间入栈的元素不可能是“成功的”,弹出后栈又被清空,又回到了开头情况。所以答案就是整个过程中栈底元素的个数。因为任意元素只会被唯一元素弹出一次,所以可以从 $1$ 到 $n$ 模拟一遍,记 $s_i$ 会被 $s_{nxt_i}$ 弹出,复杂度为 $O(n)$ 。
求解过程转化成代码为:
int ans=1; //首次入栈元素是“成功的”
for(int p=l;p<=r;p=nxt[p]) ans++;
可如果询问区间内每个 $nxt_i$ 都指向 $nxt_{i+1}$,那么相当于一步一弹,和暴力模拟没有区别。
定义 $f_{i,j}$ 为从元素 $i$ 开始弹 $2^j$次后的元素。若没有则为 $0$。在 $f$ 上面转移,一步弹2的幂次元素,就把询问优化到了 $O(\log n)$。$f$ 的预处理复杂度为 $O(n \log n)$。
思想:倍增。
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
//支持负数
template<typename T>
inline void read(T &x)
{
char ch;bool flag = 0;
while(!isdigit(ch=getchar()))
(ch=='-')&&(flag=true);
for(x=ch-'0';isdigit(ch=getchar());x=x*10+ch-'0');
(flag)&&(x=-x);
}
template<typename T>
void print(T x)
{
if(x<0){putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
typedef long long ll;
const int N=5e5+10,K=20;
int n,m,a[N],b[N],stk[N],tt,f[N][K];
inline bool check(int x,int y){return a[x]!=a[y]&&b[x]<b[y];}
int main()
{
// freopen("stack.in","r",stdin);
// freopen("stack.out","w",stdout);
read(n),read(m);
for(int i=1;i<=n;i++) read(a[i]);
for(int i=1;i<=n;i++) read(b[i]);
/init
for(int i=1,tt=0;i<=n;i++) //模拟,预处理f[i][0]
{
while(tt&&!check(i,stk[tt]))
f[stk[tt--]][0]=i;
stk[++tt]=i;
}
//元素i弹2^j次后的元素当然是
//它弹2^(j-1)次后再弹2^(j-1)次后的元素
for(int k=1;k<K;k++) //从后往前转移f
for(int i=n;i>=1;i--)
f[i][k]=f[f[i][k-1]][k-1];
//work
for(int i=1,l,r;i<=m;i++)
{
read(l),read(r);int res=1;
for(int k=K-1;k>=0;k--)
if(f[l][k]<=r&&f[l][k]) //注意要判f[l][k]!=0
{
res+=1<<k;
l=f[l][k]; //一步弹2^k次
}
print(res),putchar('\n');
}
return 0;
}
原文地址:http://www.cnblogs.com/michaellee1112/p/16811472.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性