首页 > 其他分享 >#10121. 「一本通 4.2 例 3」与众不同

#10121. 「一本通 4.2 例 3」与众不同

时间:2022-11-27 22:35:54浏览次数:63  
标签:last 与众不同 4.2 int stt ans 序列 10121 include

定义合法序列:  含有的元素各不相同

查询[l,r] 有多少合法序列

 

处理出stt[i] 表示以i结尾的合法序列的起点   stt[i] =stt[i-1],last[ a[i] ]+1

stt [ ]单调增,可以找到一个点x  满足stt[i]<L (I<x) ,stt[j]>=L(j>x)

二分查找即可

 

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std ;
 const int N=1e6,M=1e6+10;
 
 int mx[N][20],n,a[N];
 int stt[N],len[N],last[M*2];
 
 void init(){
     int i,j;
     
     for(i=1;i<=n;i++){
         cin>>a[i];
         stt[i]=max(stt[i-1],last[a[i]+M]+1);
         len[i]=i-stt[i]+1;
         
         last[a[i]+M]=i;
     }
     for(i=1;i<=n;i++) mx[i][0]=len[i];
     for(j=1;j<20;j++)
      for(i=1;i+(1<<j)-1<=n;i++){
          mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
      }
 }
 int q(int l,int r){
     int t=log2(r-l+1);
     return max(mx[l][t],mx[r-(1<<t)+1][t]);
 }
 int find(int l,int r){
     int x,y;
     if(stt[l]==r) return l;
     if(stt[r]<l) return r+1;
     
     x=l,y=r;
     while(x<=y){
         int md=(x+y)/2;
         if(stt[md]<l)  x=md+1;
         else y=md-1;
     }
     return x;
 }
 main(){
     int tes;
     int l,r,ans;
     cin>>n>>tes;
     init();
     while(tes--){
         scanf("%d%d",&l,&r); ++l,++r;
         
         int x=find(l,r);
         ans=0;
         if(x>l) ans=x-l;
         if(x<=r){
             ans=max(ans,q(x,r));
         }
         cout<<ans<<endl;
     }
     
 }
 
 

 

标签:last,与众不同,4.2,int,stt,ans,序列,10121,include
From: https://www.cnblogs.com/towboa/p/16930880.html

相关文章

  • 11.24.2
    #include<stdio.h>voidswap(int*pa,int*pb){intt;t=*pa; *pa=*pb;*pb=t;}intmain(){inta,b,*p1,*p2;scanf("%d%d",&a,&b);p1=&a;p2=&b;swa......
  • Newtonsoft的高级玩法,让你的json字符串与众不同
    json一经出现就得到多很多开发员的青睐,数据传输直接取代了之前的xml格式,不过也确实非常好用。关于json的常用操作,可以参考这篇文章。今天要分享的是Newtonsoft这个类库对Js......
  • 4.2词法分析器的设计
    词法分析器的结构  预处理子程序在扫描器的调用下,将源程序输入到输入缓冲区,预处理子程序读取输入缓冲区的字符进行文本的预处理。经过预处理后规范性更好的文本被送......
  • docker安装nacos1.4.2
    1.拉取需要的镜像dockerpullnacos/nacos-server:1.4.22.启动nacosdockerrun--namenacos-test-d-p8848:8848--privileged=true-eMODE=standalonenacos/na......
  • WGCLOUD v3.4.2 配置使用监测 MongoDB 教程
    WGCLOUD是一款高效轻量的运维平台它可以监测各种数据库的运行状态,如果出现连不上的情况,也会及时告警,比如SQLServer、Oracle、MySQL、PostgreSQL、Redis等,我们就看下它怎么......
  • nexus-2.14.2-01-bundle构建maven私服
    nexus-2.14.2-01-bundle构建maven私服一、下载nexus地址:​​https://sonatype-download.global.ssl.fastly.net/repository/repositoryManager/oss/nexus-2.14.8-01-bundle.......
  • 命令行提示:-bash-4.2$ ,原因分析及解决
    Linux普通用户登录后,命令行提示:-bash-4.1$,原因分析及解决有时候在使用用户登陆Linux系统时会发现,命令行提示符成了:-bash-4.2$,不显示用户名,路径信息。 原因:用户家目录......
  • Day14.2:数组的声明及创建
    数组概念相同类型的数据的集合。语法格式://数组类型数组名=数组的值;int[]a=newint[10];//数组a含10个int类型的数据//====================================......
  • linux root切换新用户出现-bash-4.2$
     原因:新用户目录下缺少环境变量文件.bash_profile和.bashrc解决办法:将.bash_profile和.bashrc文件复制到登录的用户目录下登录root用户执行命令,执行完再次切换,切换成......
  • 高绩效人力资源团队与众不同的 5 件事
    对于人力资源部来说,这几年并不容易。在远程和混合工作的突然兴起、大辞职以及现在动荡的经济之间,组织有很多事情要应对。面对如此多的挑战,几乎可以肯定有些团队会达不到要......