bzoj 3489: A simple rmq problem k-d树思想大暴力

3489: A simple rmq problem

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 551 Solved: 170
[Submit][Status][Discuss]

Description

因为是OJ上的题，就简单点好了。给出一个长度为n的序列，给出M个询问：在[l,r]之间找到一个在这个区间里只出现过一次的数，并且要求找的这个数尽可能大。如果找不到这样的数，则直接输出0。我会采取一些措施强制在线。

Input

第一行为两个整数N,M。M是询问数，N是序列的长度（N<=100000，M<=200000)

第二行为N个整数，描述这个序列{ai}，其中所有1<=ai<=N

再下面M行，每行两个整数x，y，

询问区间[l,r]由下列规则产生（OIER都知道是怎样的吧>_<)：

l=min(（x+lastans)mod n+1,(y+lastans）mod n+1);

r=max(（x+lastans)mod n+1,(y+lastans）mod n+1);

Lastans表示上一个询问的答案，一开始lastans为0

Output

一共M行，每行给出每个询问的答案。

Sample Input

10 10
6 4 9 10 9 10 9 4 10 4
3 8
10 1
3 4
9 4
8 1
7 8
2 9
1 1
7 3
9 9

Sample Output

4
10
10
0
0
10
0
4
0
4

HINT

注意出题人为了方便，input的第二行最后多了个空格。

　　曾经以为这是自己一道原创题啊，直到在bzoj发现了这道题。。。

　　某日学姐问了一道这个问题的离线版，然后说正解是裸裸的O(nlogn)线段树，然后就都不会了，O(nlogn)的解法我还是怀疑不存在的，不过线段树套set到是没啥问题的。

　　然后另一日，hja表示这道题可以出成在线版，问数据范围，n=3*10^5.

　　于是乎hja自己的程序被卡mle了，然而本人蒟蒻，更本不想写主席树套可持久化Treap，于是乎yy出了这个O(n^2)算法。

　　考虑离线询问，按照r排序，对于每一个权值，我们在线段树的对应位置存下它有贡献的区间（即prv[prv[x]]+1到prv[x]）对于一个权值区间，我们存下所有权值所对应的贡献区间的L-min和R-max。对于R确定的询问（L，R）我们只需要在线段树上找到最大的权值，使其区间包含L，于是我们优先递归权值大的一边，找到及退出，如果当前权值区间的(L-min，R-max)已经不可能包含L值了，那么也直接退出，这个和k-d树的find机制非常像。

　　离线我们只需要一个线段树，那么在线的话把线段树换成主席树就ok啦。

　　发现bzoj数据范围只有10^5，一交rank2！！！！加上读入优化1960ms的rank1！！！！

　　爽。。。。暴力虐标程。。。。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define MAXN 100100

#define MAXT MAXN*25

#define INF 0x3f3f3f3f

#define smid ((l+r)>>1)

inline int nextInt()

{

        register char ch;

        register int x=;

        while (ch=getchar(),ch<'' || ch>'');

        while (x=x*+ch-'',ch=getchar(),ch<='' && ch>='');

        return x;

}

struct sgt_node

{

        int lc,rc;

        int mn,mx;

        sgt_node()

        {

                mn=INF;

                mx=-INF;

        }

}sgt[MAXT];

int topt=;

int Modify_sgt(int now,int l,int r,int pos,int v1,int v2)

{

        sgt[++topt]=sgt[now];

        now=topt;

        if (l==r)

        {

                sgt[now].mn=v1;

                sgt[now].mx=v2;

                return now;

        }

        if (pos<=smid)

                sgt[now].lc=Modify_sgt(sgt[now].lc,l,smid,pos,v1,v2);

        else

            sgt[now].rc=Modify_sgt(sgt[now].rc,smid+,r,pos,v1,v2);

        sgt[now].mn=min(sgt[sgt[now].lc].mn,sgt[sgt[now].rc].mn);

        sgt[now].mx=max(sgt[sgt[now].lc].mx,sgt[sgt[now].rc].mx);

        return now;

}

int Query_sgt(int now,int l,int r,int v)

{

        if (l==r)

                return v<=sgt[now].mx && v>=sgt[now].mn?l:;

        int ret=;

        if (sgt[sgt[now].rc].mn<=v && sgt[sgt[now].rc].mx>=v)

        {

                ret=Query_sgt(sgt[now].rc,smid+,r,v);

                if (ret)return ret;

        }

        return Query_sgt(sgt[now].lc,l,smid,v);

}

int a[MAXN];

int tmp[MAXN];

int prv[MAXN];

int root[MAXN];

int main()

{

        //freopen("seq0.in","r",stdin);

        //freopen("seq10.out","w",stdout);

        freopen("input.txt","r",stdin);

        //freopen("output.txt","w",stdout);

        int n,m,x,y,z;

        n=nextInt(),m=nextInt();

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

                a[i]=nextInt();

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

        {

                prv[i]=tmp[a[i]];

                tmp[a[i]]=i;

        }

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

                root[i]=Modify_sgt(root[i-],,n,a[i],prv[i]+,i);

        int lastans=;

        int aa,bb;

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

        {

                aa=nextInt(),bb=nextInt();

                x=min((aa+lastans)%n+,(bb+lastans)%n+);

                y=max((aa+lastans)%n+,(bb+lastans)%n+);

                printf("%d\n",lastans=Query_sgt(root[y],,n,x));

        }

}

秒客网