# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1273704 | lamlamlam | Secret (JOI14_secret) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
const int MN = 1000;
int n,a[MN];
struct Segtree{
struct Node{
vector<int> pre, suf;
Node(int n){
pre.push_back(n);
suf.push_back(n);
}
Node(){}
Node operator + (const Node &o) const{
Node res;
for(auto x:pre) res.pre.push_back(x);
for(auto x:o.pre) res.pre.push_back(Secret(pre.back(),x));
for(auto x:suf) res.suf.push_back(Secret(x,o.suf[0]));
for(auto x:o.suf) res.suf.push_back(x);
return res;
}
} st[MN*4];
void init(int u,int l,int r){
if(l>r) return;
if(l==r) {
st[u] = Node(a[l]);
return;
}
int mid = (l+r)/2;
init(u*2,l,mid);
init(u*2+1,mid+1,r);
st[u] = st[u*2] + st[u*2+1];
}
int query(int u,int l,int r,int x,int y){
if(l==r) return a[l];
int mid = (l+r)/2;
if(y<=mid) return query(u*2,l,mid,x,y);
else if(x>mid) return query(u*2+1,mid+1,r,x,y);
// y>=mid+1 and x<=mid;
// cerr << "GETTING:: " << u << ' ' << l << ' ' << r << ' ' << x << ' ' << y << endl;
return Secret(st[u*2].suf[x-l],st[u*2+1].pre[y-mid-1]);
}
}st;
void Init(int N, int A[]) {
n = N;
for(int i=0; i<N; i++) a[i+1] = A[i];
st.init(1,1,N);
// cerr << "?????????????\n";
}
int Query(int L, int R) {
return st.query(1,1,n,L+1,R+1);
}