[CF301D] Yaroslav and Divisors - 树状数组,离线处理

2021-03-30 06:26

阅读：670

标签：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 - 树状数组,离线处理

Description

Solution

评论

热门文章

推荐文章

最新文章

置顶文章