[CF301D] Yaroslav and Divisors - 树状数组,离线处理
2021-03-30 06:26
阅读：723
标签：obj line 长度 else signed false out lse pos
Description
给定长度为 \(n\) 的数列，每个数都在 \([1,n]\) 间，回答 \(m\) 个询问，每次给定一个区间 \([l,r]\)，问其中有多少对数间存在倍数关系。
Solution
考虑离线处理，将所有询问区间按右端点排序
用树状数组（单点修改，区间求和）动态维护每个位置的贡献，对于一对数，我们始终将贡献记录在位置靠前的那个数身上，记为 \(f[i]\)
从左到右扫描整个序列，对于当前位置 \(i\) 上的数 \(p_i\)，我们考虑它的所有倍数 \(p_j\)
若 \(j，则 \(f[ j ]+=1\)
若 \(j>i\)，则需要延迟处理，我们对每个位置维护一个无序集合（实现用 vector），遇到这样的情况，就将 \(i\) 加入 \(j\) 的集合中，而每个点被扫描时，则会处理它集合中的所有 \(k\)，将 \(f[k]+=1\)
#include
using namespace std;
#define int long long
const int N = 400005;
int n,m,l,r,p[N],pos[N],ans[N];
vector v[N];
int ar[N]; // index: 1 ~ N
int lowbit(int t)
{
return t & (-t);
}
void add(int i, int v)
{
for (; i 0; s += ar[i], i -= lowbit(i));
return s;
}
int query(int l,int r)
{
return sum(r)-sum(l-1);
}
struct request
{
int l,r,id;
bool operator >n>>m;
for(int i=1;i>p[i], pos[p[i]]=i;
for(int i=1;i>req[i].l>>req[i].r, req[i].id=i;
sort(req+1,req+m+1);
int cur=1;
for(int _i=1;_i [CF301D] Yaroslav and Divisors - 树状数组,离线处理
标签：obj line 长度 else signed false out lse pos
原文地址：https://www.cnblogs.com/mollnn/p/13586560.html
上一篇：39. 逆转数组（二）
下一篇：树状数组241. 楼兰图腾
文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[CF301D] Yaroslav and Divisors - 树状数组,离线处理
文章链接：http://soscw.com/index.php/essay/69866.html
文章标题：[CF301D] Yaroslav and Divisors - 树状数组,离线处理
文章链接：http://soscw.com/index.php/essay/69866.html
评论
亲，登录后才可以留言！