vue做普通网站页面跳转,网游手游排行榜前十名,自建网站怎么做推广,宁波公司网站开发区间第k小
金牌导航 整体二分-1
题目大意
给出一个序列#xff0c;有若干查询#xff0c;每次查询给出l,r,k#xff0c;让你求l~r这个区间的第k大
输入样例
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3输出样例
5
6
3数据范围 1⩽n⩽105,1⩽m⩽50000,1⩽∣ai∣⩽1091\leqsla…区间第k小
金牌导航 整体二分-1
题目大意
给出一个序列有若干查询每次查询给出l,r,k让你求l~r这个区间的第k大
输入样例
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3输出样例
5
6
3数据范围
1⩽n⩽105,1⩽m⩽50000,1⩽∣ai∣⩽1091\leqslant n \leqslant 10^5,1\leqslant m\leqslant 50000, 1\leqslant |a_i|\leqslant 10^91⩽n⩽105,1⩽m⩽50000,1⩽∣ai∣⩽109
解题思路
先把原序列按数值排序 然后对于所有查询进行整体二分 对于每一段的二分先将mid左侧的数按原下标存进树状数组然后每个查询判断它查询的区间是否个数大于k 然后继续分治
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 100010
#define M 50010
using namespace std;
int n, m, c[N], ans[N];
struct node
{int v, s;bool operator (const node b) const{return s b.s;}
}s[N];
struct nodee
{int l, r, k, v;
}a[M], b[M];
void add(int x, int y)
{for (; x n; x x -x)c[x] y;return;
}
int ask(int x)
{int sum 0;for (; x; x - x -x)sum c[x];return sum;
}
void solve(int l, int r, int L, int R)
{if (l r){for (int i L; i R; i)ans[a[i].v] s[l].s;//计算结果return;}int mid l r 1, L1 L, R1 R;for (int i l; i mid; i)add(s[i].v, 1);//存数for (int i L; i R; i){int g ask(a[i].r) - ask(a[i].l - 1);if (a[i].k g) b[L1] a[i];//整体二分else{b[R1] a[i];b[R1--].k - g; }}for (int i L; i R; i)a[i] b[i]; for (int i l; i mid; i)add(s[i].v, -1);if (L1 L) solve(l, mid, L, L1 - 1);if (R1 R) solve(mid 1, r, R1 1, R);
}
int main()
{scanf(%d%d, n, m);for (int i 1; i n; i){scanf(%d, s[i].s);s[i].v i;}sort(s 1, s 1 n);for (int i 1; i m; i){scanf(%d%d%d, a[i].l, a[i].r, a[i].k);a[i].v i;}solve(1, n, 1, m);for (int i 1; i m; i)printf(%d\n, ans[i]);return 0;
}
