洛谷2709 小B的询问

Luogu

算法

莫队。

考虑cnt增加或减少时答案发生了什么。

显然有:

$(k+1)^2=k^2+2k+1$

$(k-1)^2=k^2-2k+1$

所以增加时,答案增加了$2k+1$;减少时,答案减少了$2k-1$。

细节见代码。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int block,cnt[50010];
int ans=0,Ans[50010];
int a[50010];
int n,m,k;

struct query { int l,r,id; } q[50010];

inline bool cmp(query a,query b) {
    return (a.l/block)^(b.l/block)?a.l<b.l:(((a.l/block)&1)?a.r<b.r:a.r>b.r);
}

inline void add(int x) {
    ans+=2*cnt[a[x]]+1;
    cnt[a[x]]++;
}
inline void del(int x) {
    ans-=2*cnt[a[x]]-1;
    cnt[a[x]]--;
}

int main() {
    n=read(),m=read(),k=read();
    block=n/sqrt(m*2.0/3.0);
    for (re int i=1;i<=n;i++) a[i]=read();
    for (re int i=1;i<=m;i++)
        q[i].l=read(),q[i].r=read(),q[i].id=i;
    sort(q+1,q+m+1,cmp);
    re int l=1,r=0;
    for (re int i=1;i<=m;i++) {
        int ql=q[i].l,qr=q[i].r;
        while (l<ql) del(l++);
        while (l>ql) add(--l);
        while (r<qr) add(++r);
        while (r>qr) del(r--);
        Ans[q[i].id]=ans;
    }
    for (re int i=1;i<=m;i++) printf("%d\n",Ans[i]);
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 24 PM

发表评论