[COCI 2017-2018-2]

garaza(4s256M)

最近，Slavko一直在研究自然数序列。他发现如果序列中所有元素的最大公约数大于1，则这个序列有趣的。

昨天，他在车库里发现了一个由N个自然数组成的序列。因为他很无聊，所以决定通过简单的提问来保持自己的注意力。每个查询可以是两种类型的一种：

改变X位置上的值为V
统计L 到 R区间内有趣子序列的个数。

输入：

第一行两个数N和Q (1 ≤ N, Q ≤ 10⁵ ),表示序列中元素的个数和操作的个数。

接下来一行N个数，表示原始的数序。第i个数用 Ai表示i (1 ≤ Ai ≤ 10⁹ )

接下来Q行，每行表示一个操作。

操作的第一个数值为1或2，表示操作的类型。

对于类型1，后面两个数X和V。X (1 ≤ X ≤ N) and V (1 ≤ V ≤ 10 ⁹ )

对于类型2，后面两个数L和R。(1 ≤ L ≤ R ≤ N)

输出：

对于每一个类型2，输出一行一个数，表示给定区间内连续的有趣子序列的个数。

SAMPLE TESTS

input

5 1

8 4 3 9 1

2 2 5

Output

样例1，区间2，5的元素是(4, 3, 9, 1).连续的有趣子序列为:

[4] 3 9 1,4 [3] 9 1, 4 3 [9] 1, 4 [3，9] 1 中括号内为连续的子序列。

题目大意：

给一段序列，求l,r之间有多少子序列的gcd>1,支持修改

分析：

想到分治，想到可能可以能线段树维护，现在的难点就是怎么合并两段子序列

解决：

我们考虑直接线段树维护区间内答案的个数。l+r 区间内的答案为 l 的答案加上 r 的答案再加上从左区间出发，到达右区间的串的数量。
我们考虑如何维护跨区间答案的数量。
一个子串对答案有贡献,当且仅当串的 GCD 大于 1 。问题转化为维护跨区间的 GCD 大于 1 的有多少个串.
线段树是无法维护跨区间的数据的,对于这种东西,我们可以拆成前缀+后缀的形式。
记录每个区间的前缀GCD 与后缀 GCD ,
打表或思考发现两个数的 GCD 不超过最大数的1/2，且前缀 GCD 单调递减。
所以前缀GCD的种类不超过log个,我们可以开pair记录前缀 GCD 的值与数量。
整个区间的前缀GCD 长度不超过L区间的部分直接继承过来。
超过 L 的部分就是L整段区间的 GCD 和 R中前缀的 GCD的 GCD.
如果前缀 GCD相同,直接数量加到上一个上。
如果前缀 GCD不同,新建一个pair 数值为算出来的 GCD. 数量为R 区间前缀的 GCD 的数量。
后缀 GCD 同理。

然后我们得到合并区间计算答案时,枚举 L 区间的后缀与 R 区间的前缀。我们发现右移 L 区间指针时,其实是去掉了一个数的GCD，所以 R区间的指针也会右移或不动。所以计算时 L R 区间的指针都是单调右移的。
所以可以 two−pointer 快速得到答案.

然后注意合并区间时代码的细节。。一定要对拍。。

主要就是
线段树的维护前后缀维护跨区间信息,观察 GCD性质发现只有log 种不同GCD two−pointer快速得到答案
转至：https://blog.csdn.net/qq_40512553/article/details/79986904
(有人写了，我就不写了)

附上代码：

#include<bits/stdc++.h>
using namespace std;
const long long maxn=1e5+12;
typedef pair<int,int> par;

inline int gcd(int a,int b){if(a < b)swap(a,b);while(b){a %= b;swap(a,b);}return a;}
inline int read()
{
    int x = 0;char i = getchar();
    while(!isdigit(i))i = getchar();
    while(isdigit(i))x = x * 10 + i - '0',i = getchar();
    return x;
}
struct Tree
{
    vector<par> pre,sub;
    long long iting;
}tree[maxn<<2];
int N,Q;
inline Tree pushup(Tree l,Tree r)
{
    Tree a;a.pre.clear();a.sub.clear();
    a.pre = l.pre;a.sub = r.sub;
    for(int i = 0;i < r.pre.size();i++)
    {
      int tmp = gcd(r.pre[i].first,l.pre[l.pre.size() - 1].first);
      if(tmp == a.pre[a.pre.size() - 1].first)a.pre[a.pre.size() - 1].second += r.pre[i].second;
      else a.pre.push_back(make_pair(tmp,r.pre[i].second));
    }
    for(int i = 0;i < l.sub.size();i++)
    {
        int tmp = gcd(l.sub[i].first,r.sub[r.sub.size() - 1].first);
        if(tmp == a.sub[a.sub.size() - 1].first)a.sub[a.sub.size() - 1].second += l.sub[i].second;
        else a.sub.push_back(make_pair(tmp,l.sub[i].second));
    }
    a.iting = l.iting+ r.iting;
    int lc = l.sub.size() - 1,rc = 0;long long ls,rs = 0;bool f = 0;
    while(true)
    {
        int tmp = f ? rc - 1 : rc;
        while(lc>0&& gcd(l.sub[lc].first,r.pre[tmp].first) == 1)lc--,f = 0;
        if(lc < 0)break;if(f)lc--;
        ls = l.sub[lc].second;rs;
        while(rc < r.pre.size() && gcd(l.sub[lc].first,r.pre[rc].first) != 1)
        rs += r.pre[rc].second,rc++;
        if(gcd(l.sub[lc].first,r.pre[rc - 1].first) != 1)a.iting += ls * rs;
        if(lc <= 0)break;
        f = 1;
    }
    return a;
}
int a[maxn];
inline void build(int l,int r,int rt)
{
    if(l == r)
    {
      tree[rt].pre.clear();tree[rt].sub.clear();
      tree[rt].sub.push_back(make_pair(a[l],1));
      tree[rt].pre.push_back(make_pair(a[l],1));
      tree[rt].iting = a[l] != 1;
      return;
    }
    int mid = l + r >> 1;
    build(l,mid,rt << 1);
    build(mid + 1,r,rt << 1 | 1);
    tree[rt] = pushup(tree[rt << 1],tree[rt << 1 | 1]);
}
inline void updata(int L,int l,int r,int rt)
{
    if(l == r)
    {
      tree[rt].pre.clear();tree[rt].sub.clear();
      tree[rt].sub.push_back(make_pair(a[l],1));
      tree[rt].pre.push_back(make_pair(a[l],1));
      tree[rt].iting = a[l] != 1;
      return;
    }
    int mid = l + r >> 1;
    if(L <= mid)updata(L,l,mid,rt << 1);
    else updata(L,mid + 1,r,rt << 1 | 1);
    tree[rt] = pushup(tree[rt << 1],tree[rt << 1 | 1]);
}
inline Tree query(int L,int R,int l,int r,int rt)
{
    if(L <= l && r <= R)return tree[rt];
    int mid = l + r >> 1;
    if(L > mid)return query(L,R,mid + 1,r,rt << 1 | 1);
    if(R <= mid)return query(L,R,l,mid,rt << 1);
    return pushup(query(L,R,l,mid,rt << 1),query(L,R,mid + 1,r,rt << 1 | 1));
}

int main()
{
    freopen("garaza.in","r",stdin);
    freopen("garaza.out","w",stdout);
    N=read();Q=read();
    for(int i=1;i<=N;i++) a[i]=read();
    
    build(1,N,1);
    int type,l,r;
    for(int i=1;i<=Q;i++)
    {
        type=read();l=read();r=read();
        if(type==1) a[l]=r,updata(l,1,N,1);
        else printf("%lld
",query(l,r,1,N,1).iting);
    }
    fclose(stdin);
    fclose(stdout);
}

View Code