[BZOJ 2743] 采花

Link:https://www.lydsy.com/JudgeOnline/problem.php?id=2743

Algorithm:

此题询问区间内出现次数超过1个的数字

明显在线做无从下手，无法在区间两端无序的情况下统计符合要求的数字

但可以发现，如果左端递增，是可以用树状数组维护右端数据的

于是我们采取离线方式，将询问排序，左端点不断右移，树状数组随之更新即可

先预处理出next和first数组

每次走过一个数对nxt[i]--，nxt[nxt[i]]++

Code:

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> P;

typedef pair<P,int> PP;

#define F first

#define S second

const int MAXN=;

int dat[MAXN],bit[MAXN],res[MAXN],nxt[MAXN],cur[MAXN],fst[MAXN],n,c,m;

PP op[MAXN];

inline int read()

{

    char ch;int num,f=;

    while(!isdigit(ch=getchar())) f|=(ch=='-');

    num=ch-'';

    while(isdigit(ch=getchar())) num=num*+ch-'';

    return f?-num:num;

}

inline void write(long long x)

{

    if(x<) putchar('-'),x=-x;

    if(x>) write(x/);

    putchar(x%+'');

}

void update(int pos,int x)

{

    while(pos<=n)

    {

        bit[pos]+=x;

        pos+=pos&(-pos);

    }

}

int cal(int pos)

{

    int ret=;

    while(pos)

    {

        ret+=bit[pos];

        pos-=pos&(-pos);

    }

    return ret;

}

int main()

{

    n=read();c=read();m=read();

    fill(nxt,nxt+MAXN,MAXN-);

    for(int i=;i<=n;i++) dat[i]=read();

    for(int i=;i<=m;i++) op[i].F.F=read(),op[i].F.S=read(),op[i].S=i;

    for(int i=;i<=n;i++)  //预处理

    {

        if(!cur[dat[i]]) fst[dat[i]]=i;

        nxt[cur[dat[i]]]=i,cur[dat[i]]=i;

    }

    for(int i=;i<=c;i++) if(nxt[fst[i]]) update(nxt[fst[i]],);

    nxt[]=;op[].F.F=;

    sort(op+,op+m+);

    for(int i=;i<=m;i++)  //离线

    {

        for(int j=op[i-].F.F;j<op[i].F.F;j++)  //更新右端点

            update(nxt[nxt[j]],),update(nxt[j],-);

        res[op[i].S]=cal(op[i].F.S)-cal(op[i].F.F-);

    }

    for(int i=;i<=m;i++) write(res[i]),putchar('\n');

    return ;

}

Review:

1、当数据维护与左端点的单调性有关时

考虑排序后离线解题

2、一般涉及询问出现字符个数的问题

要预处理出nxt数组，滑动窗口来解题