2018年长沙理工大学第十三届程序设计竞赛 I连续区间的最大公约数

连续区间的最大公约数

思路：参照BZOJ 4488: [Jsoi2015]最大公约数脑补出的一个\(map\)套\(vector\)的写法，写起来比线段树短，运行时间比线段树快。

代码：

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#pragma GCC optimize(4)

#include<bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define LL long long

#define pb emplace_back

#define pii pair<int, int>

const int N = 1e5 + 5;

int T, n, q, a[N], L[N], R[N], d[N], cnt;

LL ans[N];

vector<int> vc[N], p[N*20];

vector<LL> sum[N*20];

map<int, int> mp, _p, mmp;

int main() {

    scanf("%d", &T);

    for(int cs = 1; cs <= T; ++cs) {

        scanf("%d", &n);

        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);

        scanf("%d", &q);

        for (int i = 1; i <= q; ++i) {

            scanf("%d %d", &L[i], &R[i]);

            vc[R[i]].pb(i);

        }

        cnt = 0;

        for (int i = 1; i <= n; ++i) {

            for (auto it : mp) {

                int g = __gcd(it.fi, a[i]);

                if(_p.find(g) == _p.end()) _p[g] = it.se;

            }

            if(_p.find(a[i]) == _p.end()) _p[a[i]] = i;

            mp = _p;

            _p.clear();

            vector<pii> tmp;

            for (auto it : mp) tmp.pb(it.se, it.fi);

            for (int j = 0; j < tmp.size(); ++j) {

                if(j+1 == tmp.size()) tmp[j].fi = i;

                else tmp[j].fi = tmp[j+1].fi-1;

                int now;

                if(mmp.find(tmp[j].se) == mmp.end()) {

                    mmp[tmp[j].se] = ++cnt;

                    now = cnt;

                }

                else now = mmp[tmp[j].se];

                p[now].pb(tmp[j].fi);

                sum[now].pb(sum[now].size()==0?tmp[j].fi:sum[now].back()+tmp[j].fi);

            }

            for (int x : vc[i]) {

                int l = L[x];

                int t = lower_bound(tmp.begin(), tmp.end(), pii{l, 0})-tmp.begin();

                d[x] = tmp[t].se;

                int pp = mmp[d[x]];

                t = lower_bound(p[pp].begin(), p[pp].end(), l)-p[pp].begin();

                if(t-1>=0) ans[x] = sum[pp].back()-sum[pp][t-1]-(sum[pp].size()-t)*1LL*(l-1);

                else ans[x] = sum[pp].back()-sum[pp].size()*1LL*(l-1);

            }

        }

        printf("Case #%d:\n", cs);

        for (int i = 1; i <= q; ++i) printf("%d %lld\n", d[i], ans[i]);

        for (auto it : mmp) p[it.se].clear(), sum[it.se].clear();

        mmp.clear();

        mp.clear();

        for (int i = 1; i <= n; ++i) vc[i].clear();

    }

    return 0;

}