当前位置: 首页 > news >正文

硝基甲苯之魇

题目链接:https://ac.nowcoder.com/acm/contest/95323/K

题意:

给定一个长度为n的数组,求所有[l,r]区间xor等于区间gcd的个数(l<r)

思路:

不妨固定左端点l,a[l]=x,发现右端点在扩增的时候,区间gcd最多变化logx次,因此可以二分出区间gcd的变化点p

同时用ST表求出区间[p1,p2]gcd大小,设为g,那么区间pre[r] xor pre[l-1] = g => pre[r]= g xor pre[l-1]

(其中r属于[p1,p2]且r不能为l),通过map套vector上二分能求出这段区间中pre[r]的数的个数

int Log[maxn];
void init(){Log[1]=0;for(int i=2;i<=2e5;i++){Log[i] =Log[i/2]+1;}
}void solve(){int n;cin>>n;vector<int>a(n+1);rep(i,1,n)cin>>a[i];vector<vector<int>>f(n+1,vector<int>(27));rep(i,1,n)f[i][0]=a[i];rep(j,1,26){for(int i=1;i+(1ll<<j)-1<=n;i++){f[i][j]=__gcd(f[i][j-1],f[i+(1ll<<j-1)][j-1]);}}auto query =[&](int l,int r)->int{int k=Log[r-l+1];return __gcd(f[l][k],f[r-(1ll<<k)+1][k]);};vector<int>pre(n+1);rep(i,1,n){pre[i]=(pre[i-1]^a[i]);}map<int,vector<int>>cnt;rep(i,1,n)cnt[pre[i]].pb(i);int ans=0;auto cal=[&](int x,int lt,int rt)->int{auto itl=lower_bound(cnt[x].begin(),cnt[x].end(),lt);int left=0;if(itl==cnt[x].end())return 0;else left=lower_bound(cnt[x].begin(),cnt[x].end(),lt)-cnt[x].begin();auto itr=upper_bound(cnt[x].begin(),cnt[x].end(),rt);if(itr==cnt[x].end()){int m=cnt[x].size();return (m-left);}else{int right=upper_bound(cnt[x].begin(),cnt[x].end(),rt)-cnt[x].begin();return (right-left);}};for(int l=1;l<=n;l++){int L=l,R=n;int u=a[l];while(L<=n){int tmp=L;int ed=-1;while(L<=R){int mid = L+R>>1;if(query(l,mid)==u){L=mid+1;ed=mid;}else R=mid-1;}if(ed==-1)break;int x= (pre[l-1]^u);ans += cal(x,max(l+1,tmp),ed);if(ed+1>n)break;u=query(l,ed+1);L=ed+1;R=n;}}cout<<ans<<endl;
}
http://www.hskmm.com/?act=detail&tid=13509

相关文章:

  • day14-Trae之一键换脸APP开发04
  • Linux服务器单网卡如何配置多个的IP地址?
  • 面试常问问题——索引是不是越多越好
  • day38大模型程序开发-GraphRAG实操
  • 关于串口通信(232、485、422)和常见问题,一篇文章就给你说清楚~
  • day13-Trae之一键换脸APP开发03
  • python第一天
  • 摩尔投票法
  • 基于STM32平台的ADS1292心电采集驱动程序
  • ProcessPoolExecutor VS ThreadPoolExecutor 进程池对比线程池
  • 深入解析MS12-020关键漏洞CVE-2012-0002:远程桌面协议的安全风险与缓解方案
  • 鸿蒙项目实战(九):get请求参数的处理
  • allegro17.4 布线鼠标拖动变成了ployline,重启后恢复,记得有地方设置但是一时找不到在哪儿了,有知道的网友吗?
  • 20250806_信安一把梭_test
  • 专业 RAW 图像处理利器!DxO PhotoLab 让你的照片质感飙升
  • mysql时间转字符串,自定义格式将日期时间值转换为字符串
  • 其他与其它的区别
  • 一天一款实用的AI工具,第2期,AI摘要生成工具
  • 邀您参加丨云栖大会中企出海技术分论坛
  • 压测指标和结果分析
  • 指令流水线
  • nuget控制台乱码的解决办法
  • 中文乱码速查表
  • .NET驾驭Word之力:结构化文档元素操作
  • 行稳、致远 | 技术驱动下的思考感悟
  • 在控制台执行这段代码可以列出所有::selection规则
  • JDK从8升级到21的问题集
  • 超前探展!2025 云栖大会朋友圈晒图必备
  • 进程池
  • AutoCAD 2025 CAD 安装包中文永久免费免激活破解版下载及详细安装教程