bzoj 2038 莫队入门

http://www.lydsy.com/JudgeOnline/problem.php?id=2038

题意：多次询问区间内取出两个相同颜色的种类数

思路：由于不是在线更新，那么可以进行离线查询，而且当知道了[l,r]的答案，且能在O（1）的条件下得知[l-1,r],[l+1,r],[l,r+1],[l,r-1]的答案，那么就能使用莫队算法了。大致上，将区间分块，由于n=a+b>=a*b，显然将区间开平方根是最优的，我们先将询问保存，按照块序第一优先，再考虑右端点进行排序。再来，使用cnt[]来记录当前颜色出现的次数，当得到[l,r]后，再考虑加入[l-1,r] ,[l,r+1]，对答案\(ans-=cnt[col[l-1]]^2,ans+=(cnt[[col[l-1]]+1)^2 \)如果是缩小区间，那么反之。

/** @Date    : 2016-12-07-21.28

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @Link    : https://github.com/

  * @Version :

  */

#include<bits/stdc++.h>

#define LL long long

#define PII pair

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5+20;

const double eps = 1e-8;

LL col[N];

int blc[N];

int cnt[N];

struct yuu

{

    LL l, r;

    int id;

    LL a, b;

}q[N];

int cmp(yuu a, yuu b)

{

    if(blc[a.l] == blc[b.l])

        return a.r < b.r;

    return a.l < b.l;

}

int cmpi(yuu a, yuu b)

{

    return a.id < b.id;

}

int main()

{

    int n, m;

    scanf("%d%d", &n, &m);

    //{

        MMF(cnt);

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

            scanf("%lld", col + i);

        int ct = sqrt(n);

        for(int i = 1; i <= n; i++)//分块

            blc[i] = (i - 1)/ct + 1;

        for(int i = 1; i <= m; i++)

        {

            scanf("%lld%lld", &q[i].l, &q[i].r);

            q[i].id = i;

        }

        sort(q + 1, q + 1 + m, cmp);

        LL ans = 0;

        LL ll = 1, rr = 0;

        for(int i = 1; i <= m; i++)

        {

            //cout << q[i].l << q[i].r << endl;

            if(ll > q[i].l)

                for(int j = ll; j > q[i].l; j--)

                    ans += (2*cnt[col[j - 1]] + 1), cnt[col[j - 1]]++;

            if(ll < q[i].l)

                for(int j = ll; j < q[i].l; j++)

                    ans -= (2*cnt[col[j]] - 1), cnt[col[j]]--;

            if(rr < q[i].r)

                for(int j = rr; j < q[i].r; j++)

                    ans += (2*cnt[col[j + 1]] + 1), cnt[col[j + 1]]++;

            if(rr > q[i].r)

                for(int j = rr; j > q[i].r; j--)

                    ans -= (2*cnt[col[j]] - 1), cnt[col[j]]--;

            ll = q[i].l;

            rr = q[i].r;

            if(q[i].l == q[i].r)

            {

                q[i].a = 0;

                q[i].b = 1;

                continue;

            }

            q[i].b = (q[i].r - q[i].l) * (q[i].r - q[i].l + 1);

            q[i].a = ans - (q[i].r - q[i].l + 1);

            LL g = __gcd(q[i].b, q[i].a);

            //cout << ans <<endl;

            q[i].a /= g;

            q[i].b /= g;

        }

        sort(q + 1, q + 1 + m, cmpi);

        for(int i = 1; i <= m; i++)

            printf("%lld/%lld\n", q[i].a, q[i].b);

    //}

    return 0;

}

巴特西

bzoj 2038 莫队入门

最新文章

热门文章