[题目链接]
https://www.lydsy.com/JudgeOnline/problem.php?id=3524
[算法]
首先离线 , 将询问按右端点排序
如果我们知道[l , r]这个区间中[L , mid]中的数有多少个和[mid + 1 , R]中的数有多少个 , 则可以通过二分的方式求出答案
可持久化线段树可以完成这个任务
时间复杂度 : O(NlogN)
[代码]
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + ; struct query
{
int l , r;
int id;
} q[MAXN]; int n , m , idx;
int a[MAXN] , lson[MAXN << ] , rson[MAXN << ] , sum[MAXN << ] , root[MAXN] , tmp[MAXN] , ans[MAXN]; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }
template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }
template <typename T> inline void read(T &x)
{
T f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
}
inline bool cmp(query a , query b)
{
return a.r < b.r;
}
inline void build(int &k , int l , int r)
{
k = ++idx;
if (l == r) return;
int mid = (l + r) >> ;
build(lson[k] , l , mid);
build(rson[k] , mid + , r);
}
inline void modify(int &k , int old , int l , int r , int pos , int value)
{
k = ++idx;
lson[k] = lson[old] , rson[k] = rson[old];
sum[k] = sum[old] + value;
if (l == r) return;
int mid = (l + r) >> ;
if (mid >= pos) modify(lson[k] , lson[k] , l , mid , pos , value);
else modify(rson[k] , rson[k] , mid + , r , pos , value);
}
inline int query(int rt1 , int rt2 , int l , int r , int x)
{
if (l == r) return l;
int mid = (l + r) >> ;
if (sum[lson[rt1]] - sum[lson[rt2]] > x) return query(lson[rt1] , lson[rt2] , l , mid , x);
else if (sum[rson[rt1]] - sum[rson[rt2]] > x) return query(rson[rt1] , rson[rt2] , mid + , r , x);
else return ;
} int main()
{ read(n); read(m);
for (int i = ; i <= n; i++)
{
read(a[i]);
tmp[i] = a[i];
}
sort(tmp + , tmp + n + );
int len = unique(tmp + , tmp + n + ) - tmp - ;
for (int i = ; i <= n; i++) a[i] = lower_bound(tmp + , tmp + len + , a[i]) - tmp;
for (int i = ; i <= m; i++)
{
read(q[i].l);
read(q[i].r);
q[i].id = i;
}
sort(q + , q + m + , cmp);
build(root[] , , len);
int now = ;
for (int i = ; i <= n; i++)
{
modify(root[i] , root[i - ] , , n , a[i] , );
while (now <= m && q[now].r == i) ans[q[now].id] = tmp[query(root[i] , root[q[now].l - ] , , n , (q[now].r - q[now].l + ) / )] , ++now;
}
for (int i = ; i <= m; i++) printf("%d\n" , ans[i]); return ; }