수열과 쿼리 14

TODO: 예쁘게 올리기

#include<stdio.h>

#include<stdlib.h>

#include<map>

#include<algorithm>

#include<vector>

using namespace std;

const int MX = 1<<17;

typedef long long ll;

struct pst_node{

int count, l, r;

}MEM[61200005];int sz = 2;

pst_node make_node(int count, int l, int r){

pst_node t; t.count = count; t.l = l; t.r = r;

return t;

}

struct pst{

int root;

pst(){ root = 1; }

pst(int root):root(root){}

pst update(int x, int d){ return pst(update(root, 0, MX-1, x, d)); }

int find(int x){ return find(root, 0, MX-1, x); }

int update(int root, int s, int e, int x, int d){

if( s == e ){

MEM[sz++].count = MEM[root].count + d;

return sz-1;

}

else{

int m = (s+e) / 2;

int l = MEM[root].l, r = MEM[root].r;

if( x <= m ) l = update(l, s, m, x, d);

else r = update(r, m+1, e, x, d);

MEM[sz++] = make_node(MEM[l].count + MEM[r].count, l, r);

return sz-1;

}

}

int find(int root, int s, int e, int x){

if( !root ) return 0;

int m = (s+e) / 2;

if( s == e ) return MEM[root].count;

if( x <= m ) return MEM[MEM[root].r].count + find(MEM[root].l, s, m, x);

else return find(MEM[root].r, m+1, e, x);

}

} def;

struct TREE{

map<int, pst> list[MX*2];

TREE(){ for(int i = 1; i < MX*2; i++) list[i][0] = def; }

void update(int x, int u, int v){ return update(1, 0, MX-1, x, u, v); }

void update(int ad, int s, int e, int x, int u, int v){

int m = (s+e) / 2;

if( ad != 1 ){

pst t = list[ad].rbegin()->second.update(u, -1).update(v, 1);

list[ad][v] = t;

}

if( s == e ) return;

if( x <= m ) update(ad*2, s, m, x, u, v);

else update(ad*2+1, m+1, e, x, u, v);

}

int read(int l, int r, int k){ return read(1, 0, MX-1, l, r, k); }

int read(int ad, int s, int e, int l, int r, int k){

if( s == e ) return s;

int m = (s+e) / 2, t = 0;

auto it = list[ad*2].upper_bound(r);

if( it != list[ad*2].begin() ) t = (--it)->second.find(l);

else t = 0;

if( t >= k ) return read(ad*2, s, m, l, r, k);

else return read(ad*2+1, m+1, e, l, r, k - t);

}

} tree;

int N, M, a, b, c, d, k;

int A[MX], B[MX], D[MX];

vector<int> X;

int test()

{

pst tr = pst();

scanf("%d", &N);

for(int i = 1; i <= N; i++){

scanf("%d%d%d", &a, &b, &c);

if( a == 1 ) tr = tr.update(b, c);

else printf("%d\n", tr.find(b));

}

return 0;

}

int main()

{

scanf("%d", &N);

for(int i = 1; i <= N; i++) scanf("%d", A+i), X.push_back(A[i]);

sort(X.begin(), X.end());

X.resize(unique(X.begin(), X.end()) - X.begin());

for(int i = 1; i <= N; i++) A[i] = lower_bound(X.begin(), X.end(), A[i]) - X.begin();

for(int i = 1; i <= N; i++){

tree.update(A[i], D[A[i]], i);

D[A[i]] = i;

}

ll ans = 0;

scanf("%d", &M);

for(int i = 1; i <= M; i++){

scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);

int l = (a * max(ans, 0ll) + b ) % N + 1;

int r = (c * max(ans, 0ll) + d ) % N + 1;

if( l > r ) swap(l, r);

// int l, r, k; scanf("%d%d%d", &l, &r, &k);

ans = tree.read(l, r, k);

if( ans == MX-1 ) ans = -1;

else ans = X[ans];

printf("%lld\n", ans);

}

}