记录编号	562521	评测结果	EEEEEEEEEE
题目名称	[POJ1741][男人八题]树上的点对	最终得分	0
用户昵称	yrtiop	是否通过	未通过
代码语言	C++	运行时间	0.922 s
提交时间	2021-07-06 10:16:56	内存使用	44.05 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
int n,m;
const int maxn = 500005;
int ls[maxn << 2],rs[maxn << 2];
ll sum[maxn << 2];
ll c[maxn];
int lowbit(int x) {
    return x & -x;
}
void add(int x,ll y) {
    for(;x <= n;x += lowbit(x)) {
        c[x] += y;
    }
    return ;
}
ll ask(int x) {
    ll cnt = 0;
    for(;x;x -= lowbit(x)) {
        cnt += c[x];
    }
    return cnt;
}
ll gcd(ll a,ll b) {
    return b ? gcd(b , a % b) : a;
}
ll a[maxn],b[maxn];
void pushup(int i) {
    sum[i] = gcd(sum[i << 1] , sum[i << 1 | 1]);
    return ;
}
void build(int i,int l,int r) {
    ls[i] = l;
    rs[i] = r;
    if(l == r) {
        sum[i] = b[l];
        return ;
    }
    int mid = l + r >> 1;
    build(i << 1 , l , mid);
    build(i << 1 | 1 , mid + 1 , r);
    pushup(i);
    return ;
}
void update(int i,int pos,int val) {
    if(ls[i] == rs[i]) {
        sum[i] += val;
        return ;
    }
    int mid = ls[i] + rs[i] >> 1;
    if(pos <= mid)update(i << 1 , pos , val);
    else update(i << 1 | 1 , pos , val);
    pushup(i);
    return ;
}
ll query(int i,int l,int r) {
    if(l > r)return 0;
    if(ls[i] >= l&&rs[i] <= r) {
        return sum[i];
    }
    ll s = 0;
    int mid = ls[i] + rs[i] >> 1;
    if(l <= mid)s = gcd(s , query(i << 1 , l , r));
    if(r > mid)s = gcd(s , query(i << 1 | 1 , l , r));
    return s;
}
int main() {
    freopen("interval_gcd.in","r",stdin);
    freopen("interval_gcd.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;++ i) {
        scanf("%lld",&a[i]);
        b[i] = a[i] - a[i - 1];
        add(i , b[i]);
    }
    build(1 , 1 , n);
    for(int i = 1;i <= m;++ i) {
        char c;
        scanf(" %c",&c);
        if(c == 'C') {
            int l,r;
            ll k;
            scanf("%d%d%lld",&l,&r,&k);
            update(1 , l , k);
            if(r < n)update(1 , r + 1 , -k);
            add(l , k);
            if(r < n)add(r + 1 , -k);
        }
        else {
            int l,r;
            scanf("%d%d",&l,&r);
            printf("%lld\n",llabs(gcd(ask(l) , query(1 , l + 1 , r))));
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}