【NOIP2015模拟11.5】JZOJ8月5日提高组T2 Lucas的数列

题目

PS：\(n*n*T*T<=10^{18}\)而不是\(10^1*8\)

题解

题意：

给出\(n\)个元素的复杂度和位置

然后每次询问一个区间

每次询问给出\(x,y,z\)

求\(x\)到\(y\)中复杂度小于等于\(z\)的元素的位置按照一定计算过程后的答案（具体见题面）

分析：

看到题目给出的式子十分的繁琐

我们来化简一下

\[K=(\sum_{i=1}^m(x_i-p)^2)*m=(\sum_{i=1}^m((x_i)^2-2x_ip+p^2))*m=(\sum_{i=1}^m(x_i)^2-\sum_{i=1}^m2x_ip+\sum_{i=1}^mp^2)*m
\]
\[=(\sum_{i=1}^m(x_i)^2-\sum_{i=1}^m2x_i\dfrac{\sum_{i=1}^mx_i}{m}+m(\dfrac{\sum_{i=1}^mx_i}{m})^2)*m=m\sum_{i=1}^m(x_i)^2-2({\sum_{i=1}^mx_i})^2+({\sum_{i=1}^mx_i})^2=m\sum_{i=1}^m(x_i)^2-({\sum_{i=1}^mx_i})^2
\]

所以说，\(K\)其实一直都是个整数：\(m\sum_{i=1}^m(x_i)^2-({\sum_{i=1}^mx_i})^2\)

再看，这题并不要求在线

所以可以离线

按照\(w\)和\(z\)为第一关键字排序

然后维护一个\(j\)使得\(1\)~\(j\)内的\(w\)都小于当前的\(z\)

由于\(z\)是单调递增的，所以\(j\)不用清零

然后构造一棵线段树（树状数组）就可以了

Code

#include<cstdio>

#include<algorithm>

using namespace std;

struct node1

{

    long long p,w,id;

}a[400005];

struct node2

{

    long long x,y,z,lixian;

}c[400005];

struct node3

{

    long long sum1,sum2,num;

}tree[1600005];

bool cmp1(node1 x,node1 y)

{

    return x.w<y.w;

}

bool cmp2(node2 x,node2 y)

{

    return x.z<y.z;

}

long long n,m,i,j;

long long s1,s2,s3,ans[400005];

void build(long long now,long long l,long long r,long long pos,long long val)

{

    if (l==r)

    {

        if (l==pos)

        {

            tree[now].num=1;

            tree[now].sum1=val*val;

            tree[now].sum2=val;

        }

        return;

    }

    if (l>pos||r<pos) return;

    long long mid=(l+r)>>1;

    build(now<<1,l,mid,pos,val);

    build(now<<1|1,mid+1,r,pos,val);

    tree[now].num=tree[now<<1].num+tree[now<<1|1].num;

    tree[now].sum1=tree[now<<1].sum1+tree[now<<1|1].sum1;

    tree[now].sum2=tree[now<<1].sum2+tree[now<<1|1].sum2;

}

void query(long long now,long long l,long long r,long long p,long long q)

{

    if (tree[now].num==0) return;

    if (l>q||r<p) return;

    if (l>=p&&r<=q)

    {

        s1+=tree[now].num;

        s2+=tree[now].sum1;

        s3+=tree[now].sum2;

        return;

    }

    long long mid=(l+r)>>1;

    query(now<<1,l,mid,p,q);

    query(now<<1|1,mid+1,r,p,q);

}

int main()

{

    freopen("sequence.in","r",stdin);

    freopen("sequence.out","w",stdout);

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

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

    {

        scanf("%lld%lld",&a[i].w,&a[i].p);

        a[i].id=i;

    }

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

    {

        scanf("%lld%lld%lld",&c[i].x,&c[i].y,&c[i].z);

        c[i].lixian=i;

    }

    sort(a+1,a+n+1,cmp1);

    sort(c+1,c+m+1,cmp2);

    j=1;

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

    {

        while (a[j].w<=c[i].z&&j<=n)

        {

            build(1,1,n,a[j].id,a[j].p);

            j++;

        }

        s1=s2=s3=0;

        query(1,1,n,c[i].x,c[i].y);

        if (s1==0) ans[c[i].lixian]=-1;

        else ans[c[i].lixian]=s1*s2-s3*s3;

    }

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

    {

        if (ans[i]==-1) printf("empty\n");

        else printf("%lld\n",ans[i]);

    }

    fclose(stdin);

    fclose(stdout);

    return 0;

}