洛谷P2709 BZOJ 3781 小B的询问（莫队）

亦凉 2021-12-23 05:53 208阅读 0赞

## 题目描述 ##

小B有一个序列，包含N个1~K之间的整数。他一共有M个询问，每个询问给定一个区间\[L..R\]，求Sigma(c(i)^2)的值,其中i的值从1到K，其中c(i)表示数字i在\[L..R\]中的重复次数。小B请你帮助他回答询问。

## 输入输出格式 ##

输入格式：

第一行，三个整数N、M、K。

第二行，N个整数，表示小B的序列。

接下来的M行，每行两个整数L、R。

输出格式：

M行，每行一个整数，其中第i行的整数表示第i个询问的答案。

## 输入输出样例 ##

输入样例\#1： 复制

6 4 3
    1 3 2 1 1 3
    1 4
    2 6
    3 5
    5 6

输出样例\#1： 复制

6
    9
    5
    2

## 说明 ##

对于全部的数据，1<=N、M、K<=50000

**题解**

**　　**第二次了……打莫队没分块……T飞了……

据说这题模拟可过……

考虑莫队，只要把每一次更改前的次数减掉，再加上更改后的次数就行了

1 //minamoto
     2 #include<iostream>
     3 #include<cstdio>
     4 #include<algorithm>
     5 #include<cmath>
     6 #define ll long long
     7 using namespace std;
     8 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
     9 char buf[1<<21],*p1=buf,*p2=buf;
    10 inline int read(){
    11     #define num ch-'0'
    12     char ch;bool flag=0;int res;
    13     while(!isdigit(ch=getc()))
    14     (ch=='-')&&(flag=true);
    15     for(res=num;isdigit(ch=getc());res=res*10+num);
    16     (flag)&&(res=-res);
    17     #undef num
    18     return res;
    19 }
    20 char sr[1<<21],z[20];int C=-1,Z;
    21 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
    22 inline void print(ll x){
    23     if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    24     while(z[++Z]=x%10+48,x/=10);
    25     while(sr[++C]=z[Z],--Z);sr[++C]='\n';
    26 }
    27 const int N=50005;
    28 int cnt[N],a[N],rt[N],l,r,n,m,k,s;ll ans[N],ansn;
    29 struct node{
    30     int l,r,id;
    31 }q[N];
    32 inline bool cmp(node a,node b){
    33     return rt[a.l]==rt[b.l]?rt[a.l]&1?a.r<b.r:a.r>b.r:a.l<b.l;
    34 }
    35 inline void add(int x){
    36     ansn-=1ll*cnt[x]*cnt[x];
    37     ++cnt[x];
    38     ansn+=1ll*cnt[x]*cnt[x];
    39 }
    40 inline void del(int x){
    41     ansn-=1ll*cnt[x]*cnt[x];
    42     --cnt[x];
    43     ansn+=1ll*cnt[x]*cnt[x];
    44 }
    45 int main(){
    46     //freopen("testdata.in","r",stdin);
    47     n=read(),m=read(),k=read(),s=sqrt(n);
    48     for(int i=1;i<=n;++i) a[i]=read(),rt[i]=(i-1)/s+1;
    49     for(int i=1;i<=m;++i)
    50     q[i].l=read(),q[i].r=read(),q[i].id=i;
    51     sort(q+1,q+1+m,cmp);
    52     l=1,r=0;
    53     for(int i=1;i<=m;++i){
    54         while(l>q[i].l) add(a[--l]);
    55         while(r<q[i].r) add(a[++r]);
    56         while(l<q[i].l) del(a[l++]);
    57         while(r>q[i].r) del(a[r--]);
    58         ans[q[i].id]=ansn; 
    59     }
    60     for(int i=1;i<=m;++i) print(ans[i]);
    61     Ot();
    62     return 0;
    63 }

转载于:https://www.cnblogs.com/bztMinamoto/p/9536913.html