Skip to content

Instantly share code, notes, and snippets.

@purplesyringa
Last active February 21, 2018 21:18
Show Gist options
  • Save purplesyringa/e01e0436fba768c91ab64eef1e1b17cd to your computer and use it in GitHub Desktop.
Save purplesyringa/e01e0436fba768c91ab64eef1e1b17cd to your computer and use it in GitHub Desktop.
Some code looking like sword
template
<class T>
struct
RMQ{
typedef
vector<
T>V;
typedef
size_t
H;vector
<V >D;vector <H
>G;RMQ(V I){H n=I.size();D.resize
(n); D[0]=I;for (H i
=0;i< n -1 ; i++){for(H j
=0 ;j <n
;j ++)if
(D[i].size
() -j >1
<< i) {D
[i +1 ].
push_back
(min(D[i
][j],D[i
][ j+ (1
<< i) ])
); }} G.
resize(n
+1);for(
H i=0;i<
n;)G[++i
]=O(i);}
H O(H n)
{H P=0;
while(n
/=2)P++;
return P
;}T get(H
l,H r){H
a=G[r-l];
return
min(D[a]
[l],D[a]
[r-(1<<a
)]);
}};
main(){vector<int>v;for(int i=1;i<
30;i++)v.push_back(i);RMQ<int>st(v);for(
int l=0;l<v.size();l++)for(int r=l+1;r<v
.size();r++){int correct=v[l];for(size_t i
=l+1;i<r;i++)correct=min(correct,v[i]);if(
correct!=st(l, r))return 1;}return 0;}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment