bzoj3489 A simple rmq problem

10268 ワード

kd-tree

http://www.elijahqi.win/2018/01/12/bzoj3489-a-simple-rmq-problem/ Description
OJの問題なので、簡単にしてください.長さnのシーケンスを与え,[l,r]の間にこの区間で一度しか現れない数を見つけ,探すことを要求するこの数をできるだけ大きくするM個の質問を与えた.このような数が見つからない場合は、直接0を出力します.私はいくつかの措置を取ってオンラインを強制します.
Input
第1の挙動は2つの整数N,Mである.Mは問合せ数、Nはシーケンスの長さ(N<=10000000、M<=20000000)
第2の動作N個の整数は、このシーケンス{ai}を記述し、ここですべての1<=ai<=N
さらに下のM行、1行あたり2つの整数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の2行目の最後にスペースを追加しました.
2015.6.24新たにデータを追加し、2016.7.9を40 S、600 Mに入れたが、再測定しなかった.
kd-treeは暴力で殺されなかった
标题:1つの区間を尋ねるたびに、この区間内で一番大きいデータを求めて木のカバーの木だとか?
直接するのはあまりよくないようです.私たちは1つの数がどのようにいくつかの区間に影響を与えるかを考えています.まず、私たちは数ごとに彼の前の数が現れた位置を求めてから、彼の後の数が現れた位置を求めます.これはzhxの巨男の方法によって、私はo(n)の小定数の記録b[]を作ることができます.下の数値を表すこの数が前回現れた位置毎回私の前の数が現れた次は私です今この数私のこの数が前回現れた位置はb[]で、それから求めました次に私たちはこの内容を(i,j,k)に変えました1つの3次元空間の座標の1次元は私の現在のこの数が何次元jにあるのは私のこの数の前に現れたのはどこでkは私のこの数の後に現れたのはどこで1つの質問区間Lに対してで、R私達は私が1つの立方体の内の点の重みの値の最大を求める必要があることを知ることができて、kd-treeは私が範囲がL<=i<=Rで、jRであることを知っています状況の点が満たされる


#include
#include
#define N 110000
#define inf 0x3f3f3f3f
using namespace std;
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0;char ch=gc();
    while(ch<'0'||ch>'9') ch=gc();
    while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=gc();
    return x;
}
int D,L,R,nxt[N],b[N],pre[N],a[N],n,m,ans,root;
struct node1{
    int d[3],v;
    int& operator[](int x) {return d[x];}
    friend bool operatorreturn a[D]int left,right,min[3],max[3],maxv;
}tree[N];
inline void update(int x){
    int l=tree[x].left,r=tree[x].right;
    tree[x].maxv=max(tree[x].maxv,max(tree[l].maxv,tree[r].maxv));
    for (int i=0;i<3;++i) tree[x].min[i]=min(tree[x].min[i],min(tree[l].min[i],tree[r].min[i]));
    for (int i=0;i<3;++i) tree[x].max[i]=max(tree[x].max[i],max(tree[l].max[i],tree[r].max[i]));
}
inline void build(int &x,int l,int r,int dim){
    D=dim;int mid=l+r>>1;x=mid;nth_element(point+l,point+mid,point+r+1);tree[x].maxv=point[mid].v;
    tree[x].x=point[mid];for (int i=0;i<3;++i) tree[x].min[i]=tree[x].max[i]=point[mid][i];
    if (l1,(dim+1)%3);
    if (r>mid) build(tree[x].right,mid+1,r,(dim+1)%3);update(x);
}
inline bool judge(node1 a){
    if (a[0]0]>R) return 0;
    if (a[1]>=L) return 0;if (a[2]<=R) return 0;
    return 1;
}
inline bool judge1(int x){
    if (tree[x].min[0]>R||tree[x].max[0]return 0;
    if (tree[x].min[1]>=L) return 0;if (tree[x].max[2]<=R) return 0;
    return 1;
}
inline void query(int x){
    if (judge(tree[x].x)) if (tree[x].x.v>ans) ans=tree[x].x.v;int ansl=0,ansr=0;
    if (tree[x].left) if (judge1(tree[x].left)) ansl=tree[tree[x].left].maxv;
    if (tree[x].right) if (judge1(tree[x].right)) ansr=tree[tree[x].right].maxv;
    if (ansl>ansr){
        if (ansl>ans) query(tree[x].left);
        if (ansr>ans) query(tree[x].right);
    } else{
        if (ansr>ans) query(tree[x].right);
        if (ansl>ans) query(tree[x].left);
    }
}
int main(){
    freopen("bzoj3489.in","r",stdin);
    n=read();m=read();for (int i=0;i<3;++i) tree[0].min[i]=inf;
    for (int i=1;i<=n;++i) {
        nxt[i]=n+1;a[i]=read();nxt[b[a[i]]]=i;pre[i]=b[a[i]];b[a[i]]=i;
    }
//  for (int i=1;i<=n;++i) printf("%d %d %d
",a[i],pre[i],nxt[i]);
    for (int i=1;i<=n;++i){point[i][0]=i;point[i][1]=pre[i];point[i][2]=nxt[i];point[i].v=a[i];}
    build(root,1,n,0);int last_ans=0;
    for (int i=1;i<=m;++i){
        int x=read(),y=read();
        L=min((x+last_ans)%n+1,(y+last_ans)%n+1);
        R=max((x+last_ans)%n+1,(y+last_ans)%n+1);
        ans=0;query(root);last_ans=ans;printf("%d
",ans);
    }
    return 0;
}

Bandwidthd+Postgresqlデータベース構成ノート

android解析XMLファイルの3つの方法のDOM