問題背景
Zhengxu Sakiko は有名な競技プログラミング選手です。しかし、彼は記憶力が非常に悪いため、学んだアルゴリズムをすぐに忘れてしまいます。
これが、彼がよく過去を追憶する理由です。
問題文
本題の特殊なメモリ制限に注意してください。最初のサブタスクを除き、メモリ制限は 60MB です。
$m$ 個の三つ組 $(l, r, v)$ が与えられます。
$q$ 個のクエリが与えられます。各クエリでは $x, y$ が与えられ、$l \le x \le r$ かつ $v \le y$ を満たす三つ組の中で、$v$ の最大値を求める必要があります。
条件を満たす三つ組が存在しない場合は $0$ を出力してください。
本題はオンラインで処理する必要があります。
入力
1 行目に 2 つの整数 $m, q$ が与えられます。
続く $m$ 行には、各三つ組 $(l, r, v)$ を表す 3 つの整数が与えられます。
続く $q$ 行には、各クエリを表す 2 つの整数 $p, q$ が与えられます。現在のクエリは $x = p \oplus ans, y = q \oplus ans$ を満たします。ここで $\oplus$ は排他的論理和（XOR）を表し、$ans$ は前回のクエリの答えと $2^{21}-1$ とのビットごとの論理積（AND）を表します。初期状態の $ans$ は $0$ です。
出力
各クエリに対して、答えを 1 行ずつ出力してください。
入出力例
入力 1
5 5 3 5 3 4 5 10 3 4 2 1 4 13 1 1 6 1 6 7 11 9 14 2 1 5 14
出力 1
6 13 3 0 10
入力 2
15 15 3 9 9 3 5 10 8 15 10 4 6 4 8 13 6 3 7 0 11 11 11 8 10 11 3 3 14 3 15 13 4 15 9 6 11 7 4 5 12 6 12 10 10 10 14 9 5 1 5 8 11 14 9 8 14 3 11 7 1 4 3 3 1 12 15 9 4 13 15 0 3 13 12 6 13
出力 2
0 0 11 0 13 0 0 0 0 13 9 4 4 7 0
制約
| 子タスク名 | 子タスク番号 | 配点 | 制限 |
|---|---|---|---|
| 足を使った管理 | 1 | 25 | メモリ制限 2048MiB |
| 不労所得 | 2 | 25 | $q \le 3 \times 10^4$ |
| データ構造の達人 | 3 | 25 | $q \le 10^5$ |
| 私は虚像である | 4 | 25 | 特になし |
すべてのデータにおいて：$1 \le m, q \le 10^6, 1 \le l \le r \le 2 \times 10^6, 0 \le v < 2^{31}, 1 \le x \le 2 \times 10^6, 0 \le y < 2^{31}$。
注記
また、小 Z が作成した区間 $k$ 番目に小さい値を求めるコードが、参考になるかもしれません。
#include <bits/stdc++.h>
using namespace std;
constexpr int Spp{1<<20},S2{1<<20};
char buf[Spp],*p1,*p2,buf2[S2],*l2=buf2,_st[22];
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,Spp,stdin),p1==p2)?EOF:*p1++)
#define putchar(c) (l2==buf2+S2&&(fwrite(buf2,1,S2,stdout),l2=buf2),*l2++=(c))
template <typename T>
void read(T &x) {
char c;int f{1};
do x=(c=getchar())^48;
while (!isdigit(c)&&c!='-');
if (x==29) f=-1,x=0;
while (isdigit(c=getchar()))
x=(x*10)+(c^48);
x*=f;
}
template <typename T,typename ...Args>
void read(T& x,Args&... args) {read(x);read(args...);}
template<typename T>
void write(T x,char c='\n') {
if (x<0) putchar('-'),x*=-1;
int tp=0;
do _st[++tp]=x%10; while (x/=10);
while (tp) putchar(_st[tp--]+'0');
putchar(c);
}
struct OI{~OI(){fwrite(buf2,1,l2-buf2,stdout);}}oi;
using LL=unsigned long long;
// wavelet
struct bits {
vector<LL> bl;
vector<int> c;
void resize(int num) {
bl.resize(((num+1)>>6)+1);
c.resize(bl.size());
}
void set(int i,LL val) {bl[i>>6]|=(val<<(i&63));}
void build() {
for (int i=1;i<bl.size();++i)
c[i]=c[i-1]+popcount(bl[i-1]);
}
int rk1(int i) {return c[i>>6]+popcount(bl[i>>6]&((1uLL<<(i&63))-1));}
int rk0(int i) {return i-rk1(i);}
};
struct wavelet {
int h;
vector<bits> B;
vector<int> pos;
void init(vector<int>& v) {
h=__lg(*max_element(v.begin(),v.end()))+1;
B.resize(h);pos.resize(h);
for (int i=0;i<h;++i) {
B[i].resize(v.size());
for (int j=0;j<v.size();++j)
B[i].set(j,(v[j]>>(h-i-1)&1));
B[i].build();
pos[i]=stable_partition(v.begin(),v.end(),[&](int c){
return !(c>>(h-i-1)&1);
})-v.begin();
}
}
int qry(int i,int j,int k,int l,int r,int x) {
if (i==j) return 0;
if (r==l+1) return l;
int mid=l+r>>1;
int L{B[x].rk0(i)},R{B[x].rk0(j)};
if (R-L>=k) return qry(L,R,k,l,mid,x+1);
else return qry(pos[x]+B[x].rk1(i),pos[x]+B[x].rk1(j),k-(R-L),mid,r,x+1);
}
} tr;
int main() {
int n,m;read(n,m);
vector<int> a(n);
for (int i=0;i<n;++i) read(a[i]);
tr.init(a);
while (m--) {
int l,r,k;read(l,r,k);
write(tr.qry(l-1,r,k,0,1<<tr.h,0));
}
return 0;
}