P7764 [COCI2016-2017#5] Poklon

· · 题解

一道莫队大水题。

跟这道题难度差不多的板子题还有 SP3267 P3901 P2709 等。

总之莫队水题满地跑。

关于莫队的知识

打好板子后，我们只要改这些地方。

因为题目要求恰好出现两次的自然数的数量，所以答案统计 ans 要这么写。

加入一个数字：当加入这个数字前，这个数字的出现次数为 1，答案加一。

当加入这个数字前，这个数字的出现次数为 2，答案减一。

减去一个数字：当减去这个数字前，这个数字的出现次数为 3，答案加一。

当减去这个数字前，这个数字的出现次数为 2，答案减一。

这个结论很好推吧。

另外这题其实不需要离散化也能过（福利）。

#include<bits/stdc++.h>
using namespace std;
struct hhh{
    int l,r,id;
}q[500010];
int n,m,block,a[500010],sum[500010],ans,fans[500010];
bool cmp(hhh a,hhh b){return (a.r/block)==(b.r/block)?a.l<b.l:a.r<b.r;}
void add(int x){
    if(sum[a[x]]==1) ans++;
    if(sum[a[x]]==2) ans--;//改动1
    sum[a[x]]++;
}
void del(int x){
    if(sum[a[x]]==3) ans++;
    if(sum[a[x]]==2) ans--;//改动2
    sum[a[x]]--;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++){
        cin>>q[i].l>>q[i].r;
        q[i].id=i;
    }
    block=n/(sqrt(m*2/3));//玄学优化
    sort(q+1,q+m+1,cmp);
    int l=0,r=0;
    for(int i=1;i<=m;i++){
        int ql=q[i].l,qr=q[i].r;
        while(l<ql) del(l++);
        while(r>qr) del(r--);
        while(l>ql) add(--l);
        while(r<qr) add(++r);
        fans[q[i].id]=ans;
    }
    for(int i=1;i<=m;i++) cout<<fans[i]<<endl;
    return 0;
}