题目思路
首先,区间收敛到
的时间是
,那么用维护区间内不同数字的数目的思路解决。
- 预处理所有右端点的
集合
- 枚举右端点,加入右端点
集合的贡献;如果在加入某个
值时发现之前出现过,那么就清掉之前的贡献,然后固定右端点区间查询即可。
- 区间维护随便用一个结构维护即可,树状数组、线段树都行
#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;
}