首页 > 代码库 > codefroce D. Powerful array[初识块状数组]

codefroce D. Powerful array[初识块状数组]

                             codefroce D. Powerful array[初识块状数组]


因为是初始所以,只能先用别人的分析。囧。。。

题目:

    给定一个数列:A1, A2,……,An,定义Ks为区间(l,r)中s出现的次数。

t个查询,每个查询l,r,对区间内所有a[i],求sigma(K^2*a[i])


离线+分块

将n个数分成sqrt(n)块。

对所有询问进行排序,排序标准:

      1. Q[i].left /block_size < Q[j].left / block_size (块号优先排序)

      2. 如果1相同,则 Q[i].right < Q[j].right (按照查询的右边界排序)


问题求解:

从上一个查询后的结果推出当前查询的结果。(这个看程序中query的部分)

如果一个数已经出现了x次,那么需要累加(2*x+1)*a[i],因为(x+1)^2*a[i] = (x^2 +2*x + 1)*a[i],x^2*a[i]是出现x次的结果,(x+1)^2 * a[i]是出现x+1次的结果。


时间复杂度分析:

排完序后,对于相邻的两个查询,left值之间的差最大为sqrt(n),则相邻两个查询左端点移动的次数<=sqrt(n),总共有t个查询,则复杂度为O(t*sqrt(n))。

又对于相同块内的查询,right端点单调上升,每一块所有操作,右端点最多移动O(n)次,总块数位sqrt(n),则复杂度为O(sqrt(n)*n)。

right和left的复杂度是独立的,因此总的时间复杂度为O(t*sqrt(n)  +  n*sqrt(n))。


#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

typedef long long LL;
const int V = 200000 + 10;
const int MAXN = 1000000 + 10;

struct node{
   int l,r,id;
}query[V];

int n,t,num[V],L,R,sum[MAXN];
LL ans[MAXN],now;

bool cmp(node a,node b){
    int m = sqrt(1.0*n);    //最好的理论值
    if(a.l / m != b.l / m){
        return a.l < b.l;
    }
    return a.r < b.r;
}

void modify(int l,int r){

    while(L < l){ //左区间不包含
        sum[num[L]]--;
        now -= num[L] * (sum[num[L]] << 1 | 1);
        L++;
    }

    while(R > r){  //右区间不包含
        sum[num[R]]--;
        now -= num[R] * (sum[num[R]] << 1 | 1);
        R--;
    }

    while(L > l){  //上一区间的左区间包含在当前区间里
        L--;
        now += num[L] * (sum[num[L]] << 1 | 1);
        sum[num[L]]++;

    }

    while(R < r){  //上一区间的右区间包含在当前区间里
        R++;
        now += num[R] * (sum[num[R]] << 1 | 1);
        sum[num[R]]++;
    }
}

int main()
{
    while(~scanf("%d%d",&n,&t)){
        for(int i = 1;i <= n;++i){
            scanf("%d",&num[i]);
        }

        for(int i = 1;i <= t;++i){
            scanf("%d%d",&query[i].l,&query[i].r);
            query[i].id = i;
        }

        sort(query+1,query + t + 1,cmp);
        now = L = R = 0;
        memset(sum,0,sizeof(sum));

        for(int i = 1;i <= t;++i){
            modify(query[i].l,query[i].r);
            ans[query[i].id] = now;
        }

        for(int i = 1;i <= t;++i){
            printf("%I64d\n",ans[i]);
        }
    }
    return 0;
}



codefroce D. Powerful array[初识块状数组]