一、区间划分
//区间划分+持久化并查集：区间连通情况统计。
inline bool comp(Ask x, Ask y){return x.km == y.km ? x.l > y.l : x.km > y.km ; }
inline void init()//把编号相同的放一起，l从大到小；{
int i ;
ms = sqrt(1.0*n) ; //大小
mg = n/ms ; //块数
mg = mg*ms == n ? mg : mg + ;
for(i = ; i <= n ; i ++) e[i].clear() ;
}
/*********************持久化并查集**********************************/
void solve()//区间划分{
int i = , j, k, l, r ;
sort(ask+, ask++q, comp) ;
while(i <= q) //询问
{
k = ask[i].km ;
for(; i <= q && ask[i].km == k && ask[i].l > (k-)*ms ; i ++) //处理区间小于ms的询问
ans[ask[i].no] = bfAnswer(i) ;
if(i > q || ask[i].km != k ) //全部为小区间
continue ;
r = (k-)*ms ; //最右端
initSet(lp, , r) ; //初始化并查集 ；
for(j = ; j <= r ; j ++) vis[j] = ;
while(i <= q && ask[i].km == k ) //求解第k块的所有大询问；
{
l = ask[i].l ;
for(j = r ; j >= l ; j -- ) //加入顶点j
addVex(lp, j, (k-)*ms) ;
r = j ;
for(; i <= q && ask[i].km == k && ask[i].l == l ; i ++)
//计算所有左端等于l的区间；
{
ans[ask[i].no] = unionRSet(ask[i].no, l, (k-)*ms+, ask[i].r ) ; //右端暴力合并 ；
}
}
}
}
二、2B树：动态区间比x小的数的个数。
void DT_insert(int rt, int x, int s ){
int i = DN, j, p ;
getBinary(x) ;
j = dig[i--] ;
if(root[rt].next[j] == -)
{
root[rt].next[j] = ++ tot ;
pool[tot].set() ;
}
if(!j) root[rt].sum += s ;
p = root[rt].next[j] ;
while(i)
{
j = dig[i--] ;
if(pool[p].next[j] == -)
{
pool[p].next[j] = ++ tot ;
pool[tot].set() ;
}
if(!j)pool[p].sum += s ;
p = pool[p].next[j] ;
}
}
int DT_count(int rt, int x){
int i = DN, j, p, ans = ;
getBinary(x) ;
j = dig[i--] ;
if(j) ans += root[rt].sum ;
if(root[rt].next[j] == -) return ans ;
p = root[rt].next[j] ;
while(i)
{
j = dig[i--] ;
if(j) ans += pool[p].sum ;
if(pool[p].next[j] == -) return ans ;
p = pool[p].next[j] ;
}
return ans ;
}
void DT_build(){
int i, k ;
size = sqrt(double(n)) ;
mg = n/size ;
mg = mg*size == n ? mg : mg+ ;
for(i = ; i <= mg ; i ++) root[i].set() ;
for(i = ; i <= n ; i ++)
{
k = (i-)/size + ;
DT_insert(k, ar[i], ) ;
}
bs = *size ;
bmg = n/bs ;
bmg = bmg*bs == n ? bmg : bmg + ;
for(i = ; i <= bmg+ ; i ++) root[MAXS+i].set() ;
for(i = ; i <= n ; i ++)
{
k = (i-)/bs + ;
DT_insert(MAXS+k, ar[i], ) ;
}
}
int DT_query(int l, int r, int x){
int i, k, ans = , bk ;
k = (l-)/size + ;
k = size*(k-)+ == l ? k : k + ; //前
for(i = l ; i <= r && i < (k-)*size+ ; i ++) ans = ar[i] < x ? ans+ : ans ;
for(; i <= r && r-i+ >= size && (k% != ) ; i += size, k ++) //小块
ans += DT_count(k, x) ;
for(bk = (k-)/+ ; i <= r && r-i+ >= bs ; i += bs, bk ++, k += )
ans += DT_count(MAXS+bk, x) ;//大块
for(; i <= r && r-i+ >= size ; i += size, k ++) //小块
ans += DT_count(k, x) ;
for(; i <= r ; i ++) ans = ar[i] < x ? ans+ : ans ;
return ans ;
}
三、树链剖分
. 树上区间[u, v] 异或 x 的最大值
// 持久化2B树 + 树链剖分（区间可直接合并）
inline void insert(int rt, int x) ； //建一颗空树
inline void addNumber(int pre, int &rt, int id, int x){//持久化
int i = SD, p ;
bool j ;
rt = ++dcnt ; p = rt ;
while(i >= )
{
pool[p] = pool[pre] ;
j = x&(<<i) ;
pool[p].mx[j] = id ;
pool[p].next[j] = ++dcnt ;
p = dcnt ;
pre = pool[pre].next[j] ;
i -- ;
}
pool[p].x = x ;
}
inline int DTcount(int rt,int l,int x)//计算前缀树[1,r]中下标>=l的与x的最大异或值
/*******c******************树链剖分*************************/
void DFS(int u){
int i, to ;
siz[u] = ; son[u] = ;
for(i = head[u] ; i != - ; i = e[i].next )
{
to = e[i].to ;
if(to != fa[u])
{
fa[to] = u ;
dep[to] = dep[u] + ;
DFS(to) ;
if(siz[son[u]] < siz[to]) son[u] = to ;
siz[u] += siz[to] ;
}
}
}
void cutLink(int u, int tp){
w[u] = ++cnt ;
top[u] = tp ;
if(son[u]) cutLink(son[u], tp) ;
for(int i = head[u] ; i != - ; i = e[i].next)
{
int to = e[i].to ;
if(to != fa[u] && to != son[u]) cutLink(to, to) ;
}
}
void buildTree(){
dep[] = ;
cnt = fa[] = siz[] = ;
DFS() ;
cutLink(, ) ;
int i ;
for(i = ; i <= n ; i ++) val[w[i]] = ar[i] ;
pool[].set() ;
dcnt = T[] = ;
for(i = ; i <= cnt ; i ++) insert(T[], val[i]) ;
for(i = ; i <= cnt ; i ++) addNumber(T[i-], T[i], i, val[i]) ;//持久化思
}
int getAns(int u, int v, int x){
int ans = , tu = top[u], tv = top[v], tmp ;
if(u == v) return DTcount(T[w[u]], w[v], x) ; ;
while(tu != tv) //如果不在同一条链上
{
if(dep[tu] < dep[tv]) {swap(tu, tv) ; swap(u, v) ; }
tmp = DTcount(T[w[u]], w[tu], x ) ; //查询从u到tu的父亲的最大值
ans = max(ans, tmp) ;
u = fa[tu] ;
tu = top[u] ;
}
if(dep[u] < dep[v]) swap(u, v) ;
tmp = DTcount(T[w[u]], w[v], x) ;
return max(ans, tmp) ;
}
. BFS实现建树
int leaf[MAXN], ns[MAXN], ct[MAXN];
void BFS(int rt){
int i, h = , t = , l = , r = ;
int u, to ;
que[t++] = rt ;
for(i = ; i <= n ; i ++)
{
siz[i] = ;
ct[i] = ns[i] = son[i] = ;
}
while (h < t) // calculate the dep.
{
u = que[h++] ;
for(i = head[u] ; i != - ; i = e[i].next)
{
to = e[i].to ;
if(to != fa[u])
{
ns[u] ++ ;
fa[to] = u ;
dep[to] = dep[u] + ;
que[t++] = to ;
}
}
}
for(i = ; i <= n ; i ++) if(ns[i] == ) leaf[r++] = i ;
while(l < r)
{
to = leaf[l++] ;
u = fa[to] ;
siz[u] += siz[to] ; ct[u] ++ ;
if(ct[u] == ns[u] && u ) leaf[r++] = u ;
}
h = t = ;
que[t++] = rt ;
siz[] = ;
while (h < t)
{
u = que[h++] ;
for(i = head[u] ; i != - ; i = e[i].next)
{
to = e[i].to ;
if(to != fa[u])
{
if(siz[son[u]] < siz[to]) son[u] = to ;
que[t++] = to ;
}
}
}
}
void BFS_cutLink(int rt, int tp){
int i, u, to, h = , t = ;
que[t++] = rt ;
while (h < t)
{
u = que[h++] ;
w[u] = ++cnt ; top[u] = u ;
to = son[u] ;
while (to)
{
w[to] = ++cnt ; top[to] = u ;
for(i = head[to] ; i != - ; i = e[i].next)
if(e[i].to != fa[to] && e[i].to != son[to]) que[t ++] = e[i].to ;
to = son[to] ;
}
for(i = head[u] ; i != - ; i = e[i].next)
{
to = e[i].to ;
if(to != fa[u] && to != son[u]) que[t++] = to ;
}
}
}
. 非直接合并查询：树上最长上升子序列
/*********************线段树成段更新最长上升子序列*************************/
void Up(int step){
L[step].lx = L[lson].lx + ( (L[lson].lx==L[lson].len && val[L[rson].left] > val[L[lson].right])?L[rson].lx:) ;
L[step].rx = L[rson].rx + ((L[rson].rx==L[rson].len &&val[L[rson].left] > val[L[lson].right])?L[lson].rx:) ;
L[step].mx = max(max(L[lson].mx,L[rson].mx),val[L[rson].left]
> val[L[lson].right]?(L[lson].rx+L[rson].lx):); L[step].dlx = L[lson].dlx + ( (L[lson].dlx == L[lson].len && val[L[rson].left] < val[L[lson].right]) ? L[rson].dlx : );
L[step].drx = L[rson].drx + ((L[rson].drx == L[rson].len && val[L[rson].left] < val[L[lson].right]) ? L[lson].drx : ) ;
L[step].dmx = max(max(L[lson].dmx,L[rson].dmx),val[L[rson].left]
< val[L[lson].right] ? (L[lson].drx+L[rson].dlx) : ) ;
}
void build(int step,int l,int r){
L[step].left=l;
L[step].right=r;
L[step].len = r-l+ ;
L[step].mid=(l+r)/;
if(l==r)
{
L[step].lx = L[step].rx = L[step].mx = ;
L[step].dlx =L[step].drx = L[step].dmx = ;
return ;
}
…… ；
}
inline void unionNode(int l, int r, int ar ){
L[ar].lx = L[l].lx + ((L[l].lx==L[l].len && val[L[r].left]
> val[L[l].right]) ? L[r].lx : ) ;
L[ar].rx = L[r].rx + ((L[r].rx==L[r].len && val[L[r].left]
> val[L[l].right]) ? L[l].rx : ) ;
L[ar].mx = max(max(L[l].mx,L[r].mx),val[L[r].left]
> val[L[l].right]?(L[l].rx+L[r].lx):); L[ar].dlx = L[l].dlx + ((L[l].dlx == L[l].len && val[L[r].left]
< val[L[l].right]) ? L[r].dlx : );
L[ar].drx = L[r].drx + ((L[r].drx == L[r].len && val[L[r].left]
< val[L[l].right]) ? L[l].drx : ) ;
L[ar].dmx = max(max(L[l].dmx,L[r].dmx),val[L[r].left] < val[L[l].right]
? (L[l].drx+L[r].dlx) : ) ;
L[ar].left = L[l].left ;
L[ar].right = L[r].right ;
L[ar].len = L[l].len + L[r].len ;
}
int query(int step,int l,int r){
if(l==L[step].left&&r==L[step].right) return step ;
…… ；
else {
int lt = query(lson,l,L[step].mid);
int rt = query(rson,L[step].mid+,r);
++scnt ;
unionNode(lt, rt, scnt) ;
return scnt ;
}
}
/*************************树链剖分*************************/
inline int unionAns(int l, int r){
int tmp = max(L[l].dmx, L[r].mx), ans ;
if(val[L[l].left] < val[L[r].left]) ans = L[r].lx + L[l].dlx ;
else ans = ;
ans = max(tmp, ans) ;
return ans ;
}
int getAns(int u, int v){
if(u == v) return L[query(, w[u], w[u])].mx ;
int tu = top[u], tv = top[v] ;
int ar, tr, ur, vr ;
scnt = *cnt +;
ar = ++scnt ; ur = - ; vr = - ;
while (tu != tv)
{
if(dep[tu] > dep[tv])//calculate the link tu -> u.
{
tr = query(, w[tu], w[u]) ;
if(ur == -) ur = tr ;
else {
++scnt ;
unionNode(tr, ur, scnt); //tr is left node.
ur = scnt ;
}
u = fa[tu] ; tu = top[u] ;
}
else {
tr = query(, w[tv], w[v]) ;
if(vr == -) vr = tr ;
else {
++scnt ;
unionNode(tr, vr, scnt) ; // tr is left node.
vr = scnt ;
}
v = fa[tv] ; tv = top[v] ;
}
}
if(dep[u] >= dep[v])// v is root.
{
tr = query(, w[v], w[u]) ;
if(ur == -) ur = tr ;
else {
scnt ++ ;
unionNode(tr, ur, scnt) ;
ur = scnt ;
}
u = v ;
}
else {
tr = query(, w[u], w[v]) ;
if(vr == -) vr = tr ;
else {
++scnt ;
unionNode(tr, vr, scnt) ;
vr = scnt ;
}
v = u ;
}
if(ur == -) return L[vr].mx ;
else if(vr == -) return L[ur].dmx ;
return unionAns(ur, vr) ; // calculate the answer of u->v
}
. 树上最大字段和
/*********************线段树最大子段和*************************/
inline void Up(int rt){
sum[rt] = sum[rt<<] + sum[rt<<|] ;
lx[rt] = max(lx[rt<<|], lx[rt<<] + sum[rt<<|]) ;
rx[rt] = max(rx[rt<<], rx[rt<<|] + sum[rt<<]) ;
mx[rt] = max(mx[rt<<], mx[rt<<|]) ;//不合并
mx[rt] = max(mx[rt], lx[rt<<] + rx[rt<<|]) ; //合并
}
inline void Down(int rt, int L, int R){
if(d[rt] != INF)
{
int x = d[rt] ;
int mid = (L+R) >> ;
d[rt] = INF ;
d[rt<<] = d[rt<<|] = x ;
sum[rt<<] = (LL)x*(mid-L+) ;
sum[rt<<|] = (LL)x*(R-mid) ;
lx[rt<<] = rx[rt<<] = mx[rt<<] = x > ? sum[rt<<] : ;
lx[rt<<|] = rx[rt<<|] = mx[rt<<|] = x > ? sum[rt<<|] : ;
}
}
inline void unionNode(int l, int r, int ar ){
sum[ar] = sum[l] + sum[r] ;
lx[ar] = max(lx[r], lx[l]+sum[r]) ;
rx[ar] = max(rx[l], rx[r]+sum[l]) ;
mx[ar] = max(mx[l], mx[r]) ;
mx[ar] = max(mx[ar], lx[l]+rx[r]) ;
}
void build(int rt, int l, int r){
d[rt] = INF ;
if(l == r)
{
sum[rt] = lx[rt] = rx[rt] = mx[rt] = val[l] ;
return ;
}
…… ；
}
void updata(int rt, int L, int R, int l, int r, int x){
if(L == l && r == R)
{
sum[rt] = (R-L+)*x ;
lx[rt] = rx[rt] = mx[rt] = x > ? sum[rt] : ;
d[rt] = x ;
return ;
}
Down(rt, L, R) ;
…… ；
}
int query(int rt, int L, int R, int l, int r){
if(L == l && R == r) return rt ;
Down(rt, L, R) ;
…… ；
else {
int x = query(rt<<, L, mid, l, mid) ;
int y = query(rt<<|, mid+, R, mid+, r) ;
++scnt ;
unionNode(x, y, scnt) ;
return scnt ;
}
}
/*************************树链剖分*************************/
inline void unionAns(int x, int y, int ar){
mx[ar] = max(mx[x], mx[y]) ;
mx[ar] = max(mx[ar], rx[x]+rx[y]) ;
}
int getAns(int u, int v){
if(u == v) return query(, , cnt, w[u], w[u]) ;
int tu = top[u], tv = top[v] ;
int ar, tr, ur, vr ;
scnt = *cnt +;
ar = ++scnt ; ur = - ; vr = - ;
while (tu != tv)
{
if(dep[tu] > dep[tv])//calculate the link tu -> u.
{
tr = query(, , cnt, w[tu], w[u]) ;
if(ur == -) ur = tr ;
else {
++scnt ;
unionNode(tr, ur, scnt); //tr is left node.
ur = scnt ;
}
u = fa[tu] ; tu = top[u] ;
}
else {
tr = query(, , cnt, w[tv], w[v]) ;
if(vr == -) vr = tr ;
else {
++scnt ;
unionNode(tr, vr, scnt) ; // tr is left node.
vr = scnt ;
}
v = fa[tv] ; tv = top[v] ;
}
}
if(dep[u] >= dep[v])
{
tr = query(, , cnt, w[v], w[u]) ;
if(ur == -) ur = tr ;
else {
scnt ++ ;
unionNode(tr, ur, scnt) ;
ur = scnt ;
}
u = v ;
}
else {
tr = query(, , cnt, w[u], w[v]) ;
if(vr == -) vr = tr ;
else {
++scnt ;
unionNode(tr, vr, scnt) ;
vr = scnt ;
}
v = u ;
}
if(ur == -) return vr ;
else if(vr == -) return ur ;
unionAns(ur, vr, ar) ; // calculate the answer of u->v
return ar ;
}
四、持久化线段树
/*******************静态 Kth number ***************************************/
void build(int &rt, int l, int r ){
rt = ++tot ;
sum[rt] = ;
if(l >= r) return ;
…… ；
}
void updata(int &rt, int pre, int l, int r, int i, int v){
rt = ++tot ;
ls[rt] = ls[pre] ; rs[rt] = rs[pre] ; sum[rt] = sum[pre] + v ;
if(l >= r ) return ;
int mid = l+r >> ;
if(mid >= i ) updata(ls[rt], ls[pre], l, mid, i, v) ;
else updata(rs[rt], rs[pre], mid+, r, i, v) ;
}
int query(int R, int L, int l, int r, int k){
if(l >= r) return l ;
int t = sum[ls[R]] - sum[ls[L]] ;
int mid = l+r >> ;
if(t >= k) return query(ls[R], ls[L], l, mid, k) ;
else return query(rs[R], rs[L], mid+, r, k-t) ;
}
/***************************************************************/
void solve(){
sort(ord+, ord++n, comp) ;
cnt = rk[ord[]] = ;
nar[cnt] = ar[ord[]] ;
for(i = ; i <= n ; i ++)
{
if(ar[ord[i]] != ar[ord[i-]])
{
rk[ord[i]] = ++cnt ;
nar[cnt] = ar[ord[i]] ;
}
else rk[ord[i]] = cnt ;
}
tot = ;
build(T[], , cnt) ;
for(i = ; i <= n ; i ++) updata(T[i], T[i-], , cnt, rk[i], ) ;
for(i = ; i <= m ; i ++)
{
scanf("%d %d %d", &l, &r, &k) ;
ans = query(T[r], T[l-], , cnt, k) ;
printf("%d\n", nar[ans]) ;//离散后的数组
}
}
}
五、KD树
#define N 50005
#define MID(x,y) ( (x + y)>>1 )
using namespace std ;
typedef long long LL ;
struct Point{
int x[];
LL dis;
Point(){
for(int i = ; i < ; i++) x[i] = ;
dis = 9223372036854775807LL ;
}
friend bool operator < (const Point &a, const Point &b)
{ return a.dis < b.dis ; }
};
priority_queue <Point, vector<Point> > res ;
LL dist2(const Point &a, const Point &b, int k) {
//距离的平方,开根号很耗时，能不开就不开
LL ans = ;
for (int i = ; i < k; i++)
//一开始这儿写的i < 5，WA了N次。。。原本以为只要初始值设0就无所谓,
ans += (a.x[i] - b.x[i]) * (a.x[i] - b.x[i]);
//但发现Point有个全局变量，在多case下会出错。。。
return ans;
}
int ddiv;
bool cmpX(const Point &a, const Point &b){return a.x[ddiv] < b.x[ddiv];}
struct KDTree {
Point p[N]; //空间内的点
int Div[N];
//记录区间是按什么方式划分（分割线平行于x轴还是y轴, ==1平行y轴切;==0平行x轴切）
int k; //维数
int m; //近邻
int getDiv(int l, int r) { //寻找区间跨度最大的划分方式
map <int, int> ms;
int minx[],maxx[];
for (int i = ; i < k; i++)
{
ddiv = i;
minx[i] = min_element(p + l, p + r + , cmpX)->x[i];
maxx[i] = max_element(p + l, p + r + , cmpX)->x[i];
ms[maxx[i] - minx[i]] = i;
}
map <int ,int>::iterator pm = ms.end();
pm--;
return pm->second;
}
void build(int l, int r) { //记得先把p备份一下。
if (l > r) return;
int mid = MID(l,r);
Div[mid] = getDiv(l,r);
ddiv = Div[mid];
nth_element(p + l, p + mid, p + r + , cmpX);
build(l, mid - );
build(mid + , r);
}
void findk(int l, int r, Point a) {//k(m)近邻，查找k近点的平方距离
if (l > r) return;
int mid = MID(l,r);
LL dist = dist2(a, p[mid], k);
if (dist >= )
{
p[mid].dis = dist;
res.push(p[mid]);
while ((int)res.size() > m)
res.pop();
}
LL d = a.x[Div[mid]] - p[mid].x[Div[mid]];
int l1, l2, r1, r2;
l1 = l , l2 = mid + ;
r1 = mid - , r2 = r;
if (d > )
swap(l1, l2), swap(r1, r2);
findk(l1, r1, a);
if ((int)res.size() < m || d*d < res.top().dis )
findk(l2, r2, a);
}
};
Point pp[N];
KDTree kd;
int solve(){
for (int i = ; i < n; i++)
for (int j = ; j < kd.k; j++)
{
scanf("%d", &pp[i].x[j]);
kd.p[i] = pp[i];
}
kd.build(, n - );
int t = ;
while(t--)
{
Point a;
for (int i = ; i < kd.k; i++)scanf("%d", &a.x[i]);
scanf("%d", &kd.m);
kd.findk(, n - , a);
printf("the closest %d points are:\n", kd.m);
Point ans[];
for (int i = ; !res.empty(); i++)
{
ans[i] = res.top();
res.pop();
}
for (int i = kd.m - ; i >= ; i--)
{
for (int j = ; j < kd.k - ; j++)
printf("%d ", ans[i].x[j]);
printf("%d\n", ans[i].x[kd.k - ]);
}
}
六、最远manhattan距离
int query(int rt, int p, int s) //维护每个状态的最大值、最小值。
void getTable(int pos){//每个点有sta个状态
int i, j, t ;
for(i = ; i < sta ; i ++)
{
t = i ;
tmp[i] = ;
for(j = ; j <= k ; j ++)
{
if(t&) tmp[i] += ar[pos].x[j] ;
else tmp[i] -= ar[pos].x[j] ;
t >>= ;
}
}
}
int solve(){
sta = <<k ; //K维平面
build(, , q) ;//将每个点的sta个状态插入树中
cnt = ;
for(i = ; i <= q ; i ++)
{
if(cnt < ){puts("") ;continue ; }
int ans = ;
for(j = ; j < sta ; j ++)
{
mxs = query(, j, ) ; //查询最大值；
mns = query(, j, ) ; //查询最小值；
ans = ans > mxs - mns ? ans : mxs-mns ;
}
printf("%d\n", ans) ;
}
七、LCA & RMQ & 树状数组
/*****************************LCA*******************************/
struct QNode{
int from, to, next, no ;
}qe[MAXN];
int cnt ;
int qhead[MAXN], pre[MAXN], LCA[MAXN] ;
inline void addQEdge(int a,int b,int c){
qe[++cnt].from = a ;
qe[cnt].to = b ;
qe[cnt].next = qhead[a] ;
qe[cnt].no = c ;
qhead[a] = cnt;
}
int find(int x){
if(x != pre[x]) pre[x]=find(pre[x]);
return pre[x];
}
void tarjan(int u){
int j, v ;
pre[u] = u ;
for(j = qhead[u] ; j != - ; j = qe[j].next)
{
v = qe[j].to;
LCA[qe[j].no] = find(v) ;
}
for(j = head[u] ; j != - ;j = e[j].next)
{
v = e[j].to ;
tarjan(v) ;
pre[v] = u ;
}
}
/*****************************RMQ*******************************/
int mn[MAXN][] ;
void rmq_init(int num){
int i , j ;
for(j = ; j <= num ; j ++ ) mn[j][] = height[j] ;
int m = floor(log((double)num)/log(2.0)) ;
for(i = ; i <= m ; i ++ )
{
for(j = num ; j > ; j -- )
{
mn[j][i] = mn[j][i-] ;
if(j+(<<(i-)) <= num)
mn[j][i] = min( mn[j][i] , mn[j+(<<(i-))][i-]) ;
}
}
}
int rmq(int l,int r){
int m = floor(log((double)(r-l+))/log(2.0)) ;
int a = min(mn[l][m], mn[r-(<<m)+][m] ) ;
return a ;
}
/*****************************树状数组*******************************/
int Lowbit(int t){ //求最小幂2^k
return t&(-t) ;
}
int Sum(int end) { //求前n项和
int sum = ;
while(end > )
{
sum += c[end];
end -= Lowbit(end);
}
return sum;
}
void plus(int pos , int n, int num){ //对某个元素进行加法操作
while(pos <= n)
{
c[pos] += num;
pos += Lowbit(pos);
}
}
八、划分树
int SU[];
int U[][];
int toL[][];
int n,m,a,b,k,t;
inline int cmp(const void *a,const void *b){return *((int *)a) - *((int *)b) ;}
void buildtree(int l,int r,int d){
int i ;
if (l==r) return;
int mid = (l+r)>> , nowl = l , nowr = mid+ , midtol = ;
for (i = mid ;i>=l && SU[i] == SU[mid] ; i--) ++midtol ;
for (i = l ; i <= r ; i++)
{
toL[d][i] = i==l ? : toL[d][i-];
if (U[d][i] < SU[mid])
{
U[d+][nowl++] = U[d][i];
++toL[d][i];
}
else if (U[d][i]==SU[mid] && midtol)
{
U[d+][nowl++] = U[d][i];
++toL[d][i];
--midtol;
}
else U[d+][nowr++] = U[d][i];
}
buildtree(l,mid,d+);
buildtree(mid+,r,d+);
}
int answer(int a,int b,int k){
int l = ,r = n,d = ;
int ls,rs,mid;
while (a != b)
{
ls = a==l ? : toL[d][a-];
rs = toL[d][b];
mid = (l+r)>>;
if (k <= rs - ls)
{
a = l+ls;
b = l+rs-;
r = mid;
}
else {
a = mid++a-l-ls;
b = mid++b-l-rs;
k -= rs-ls;
l = mid+;
}
++d;
}
return U[d][a];
}
int solve(){
for (i=;i<=n;i++)
{
scanf("%d",&t);
SU[i]=U[][i]=t;
}
sort(SU+, SU++n) ;
buildtree( , n , );
printf("%d\n",answer(a, b, k ) );
}