首页 > 其他分享 >HDU5869 Different GCD Subarray Query 离线查询/区间贡献

HDU5869 Different GCD Subarray Query 离线查询/区间贡献

时间:2022-10-28 10:35:51浏览次数:51  
标签:rt Different last GCD int gcd 离线 now define


题目思路

首先,区间收敛到的时间是,那么用维护区间内不同数字的数目的思路解决。

  • 预处理所有右端点的集合
  • 枚举右端点,加入右端点集合的贡献;如果在加入某个值时发现之前出现过,那么就清掉之前的贡献,然后固定右端点区间查询即可。
  • 区间维护随便用一个结构维护即可,树状数组、线段树都行
#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;
int a[N];

namespace SegTree{
#define ls rt << 1
#define rs rt << 1 | 1
#define lson ls, l,
#define rson rs, mid + 1,

int tree[N << 2];

inline void push_up(int rt){ tree[rt] = tree[ls] + tree[rs]; }

void clear(int rt, int l, int r){
tree[rt] = 0;
if(l == r) return;
int mid = l + r >> 1;
clear(lson), clear(rson);
}

void update(int rt, int l, int r, int pos, int val){
if(l == r) return (void)(tree[rt] += val);
int mid = l + r >> 1;
if(mid >= pos) update(lson, pos, val);
else update(rson, pos, val);
push_up(rt);
}

int query(int rt, int l, int r, int L, int R){
if(l >= L && r <= R) return tree[rt];
int mid = l + r >> 1, ans = 0;
if(mid >= L) ans += query(lson, L, R);
if(mid < R) ans += query(rson, L, R);
return ans;
}
}

struct query{ int l, id; };

#define PII pair<int, int>
#define fir first
#define sec second
#define mkp make_pair

vector<query> qr[N];
vector<PII> v[N];

int ans[N];

#define SEGRG 1, 1,

inline void solve(int n, int q){
SegTree::clear(SEGRG);
for(int i = 1; i <= n + 5; i++) v[i].clear();
for(int i = 1; i <= n + 5; i++) qr[i].clear();
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= q; i++){
int l, r; cin >> l >> r; ans[i] = 0;
qr[r].emplace_back(query{l, i});
}

for(int i = 1; i <= n; i++){
v[i].emplace_back(mkp(a[i], i));
int last_gcd = a[i];
for(auto &pre : v[i - 1]){
int val = pre.fir, ind = pre.sec;
int now_gcd = __gcd(a[i], val);
if(last_gcd != now_gcd) v[i].emplace_back(mkp(now_gcd, ind));
last_gcd = now_gcd;
}
}
unordered_map<int, int> last;
for(int i = 1; i <= n; i++){
for(auto &now : v[i]){
SegTree::update(SEGRG, now.sec, 1);
if(last.count(now.fir)) SegTree::update(SEGRG, last[now.fir], -1);
last[now.fir] = now.sec;
}
for(auto &que : qr[i]){
ans[que.id] = SegTree::query(SEGRG, que.l, i);
}
}

for(int i = 1; i <= q; i++) cout << ans[i] << endl;
}

#undef SEGRG

signed main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout << fixed << setprecision(12);
int n, q;
while(cin >> n >> q) solve(n, q);
return 0;
}


标签:rt,Different,last,GCD,int,gcd,离线,now,define
From: https://blog.51cto.com/u_12372287/5803548

相关文章

  • 11.CF522D Closest Equals 线段树+离线询问
    11.CF522DClosestEquals线段树+离线询问给定序列,查询区间内距离最近的两个相等元素。离线查询,按右端点加入贡献计算答案即可洛谷传送门:​​CF522DClosestEquals-洛谷......
  • ACWing 3548 -- 离线算法
    题目描述双端队列思路参考代码......
  • keras离线官方文档
    keras中文文档:​​​https://keras.io/zh/​​​(官方)​​​http://keras-cn.readthedocs.io/en/latest/​​由于官方文档(更新似乎快点儿)经常访问不了,所以下载查看。步骤1......
  • python制作django批量创建数据离线脚本
    scripts/init_news.pyimportosimportsysimportdjango#准备base_dir=os.path.dirname(os.path.dirname(os.path.abspath(__file__)))sys.path.append(base_dir......
  • docker离线安装
    1、docker离线安装的方式基本就是准备rpm包安装即可。2、准备的rpm包有:container-selinux-2.119.2-1.911c772.el7_8.noarch.rpmcontainerd.io-1.6.8-3.1.el7.x......
  • ntpd离线安装
    软件下载:libopts下载:链接:https://pan.baidu.com/s/1vYphmaJo9Tws-pTm3HRZfw提取码:9mxxntpdate下载:链接:https://pan.baidu.com/s/1F43qUcQeupJ_5kTovfZg7w......
  • 裴蜀定理、Exgcd与乘法逆元
    目录裴蜀定理Exgcd扩展欧几里得算法例题:P5656,exgcd模板题裴蜀定理逆元并非对任何数存在……定理:\(ax+by=c\)有解\(\{x,y\}\)当且仅当\(c\)是\(\gcd(a,b)\)的倍......
  • Cenots7 离线安装部署PostgreSQL
    1PostgreSQL源码包下载并复制1.1 PostgreSQL源码包下载:访问PostgreSQL官网选择所需版本进行下载,本次下载安装版本为v14.51.2 复制源码包至服务器使用SSH终端工具,远......
  • Spark离线项目创建和运行步骤
    一、安装maven  1.解压maven安装包,将加压后的安装包放在没有中文路径的目录下  2.创建仓库文件夹repository(理论上任何位置都是可以的,建议和maven文件夹同级别,这样......
  • Dart SDK的离线安装(适用于不同类型设备)
    前言笔者在armv8架构设备上运行ubuntu20.04系统,安装dart-sdk部署相关服务。网上基本都是照搬的官方文档的说法,经测试不是很好用,寻找版本号有些麻烦,特在此把我离线部署的......