3110: [Zjoi2013]K大数查询
Description
有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c
如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。
Input
第一行N，M
接下来M行，每行形如1 a b c或2 a b c
Output
输出每个询问的结果
Sample Input
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3
Sample Output
2
1
HINT
【样例说明】
第一个操作 后位置 1 的数只有 1 ， 位置 2 的数也只有 1 。 第二个操作 后位置 1
的数有 1 、 2 ，位置 2 的数也有 1 、 2 。 第三次询问 位置 1 到位置 1 第 2 大的数 是
1 。 第四次询问 位置 1 到位置 1 第 1 大的数是 2 。 第五次询问 位置 1 到位置 2 第 3
大的数是 1 。
N,M<=50000,N,M<=50000
a<=b<=N
1操作中abs(c)<=N
2操作中abs(c)<=Maxlongint
整体二分
定义solve(l, r, S)表答案落在[l, r]内或直接影响[l, r]答案的操作集合为S
显然，当 l = r 时，该集合内操作的答案即为r
对于当前答案范围[l, r],我们将其分为[l, mid], [mid + 1, r]两范围
由于我们求的是区间K大数，所以直接影响[mid +1, r]的操作间接影响[l, mid]
所以我们将直接影响[mid + 1, r]的操作施行在数据结构中（线段树 或 树状数组）
维护区间内[mid + 1, r]中数的个数
对于每个询问，在数据结构中求出给定区间内[mid + 1, r]中数的个数res
若 res >= k, 则该区间第k大数在[mid + 1, r]中
若 res < k, 则区间第k大数在[l, mid]中
将操作集合S中的数按答案或直接影响范围排序，然后用操作序列的首尾位置表示集合
递归solve（l, mid, S1）, solve(mid + 1, r, S2)
#include <cstdio>
#include <algorithm>
using namespace std;
const int MaxN = 50010;
const int MaxS = 250010;
int N, M;
struct opt{
int o, l, r, c, key, k;
}p[MaxN], que1[MaxN], que2[MaxN];
int clear[MaxS], ma[MaxS], sum[MaxS];
void Down(int k, int l, int r){
if (l == r) return;
int mid = l + r >> 1;
if (clear[k]) {
clear[k << 1] = clear[(k << 1) + 1] = 1;
ma[k << 1] = ma[(k << 1) + 1] = 0;
sum[k << 1] = sum[(k << 1) + 1] = 0;
clear[k] = 0;
}
if (ma[k]) {
ma[k << 1] += ma[k], ma[(k << 1) + 1] += ma[k];
sum[k << 1] += ma[k] * (mid - l + 1);
sum[(k << 1) + 1] += ma[k] * (r - mid);
ma[k] = 0;
}
}
void Clear(){
clear[1] = 1;
ma[1] = sum[1] = 0;
}
void Insert(int k, int l, int r, int L, int R, int s){
if (l > R || L > r) return;
if (L <= l && r <= R) {
ma[k] += s;
sum[k] += s * (r - l + 1);
return;
}
int mid = l + r >> 1;
Down(k, l, r);
Insert(k << 1, l, mid, L, R, s), Insert((k << 1) + 1, mid + 1, r, L, R, s);
sum[k] = sum[k << 1] + sum[(k << 1) + 1];
}
int Query(int k, int l, int r, int L, int R){
if (l > R || L > r) return 0;
if (L <= l && r <= R) return sum[k];
int mid = l + r >> 1;
int res = 0;
Down(k, l, r);
res += Query(k << 1, l, mid, L, R);
res += Query((k << 1) + 1, mid + 1, r, L ,R);
sum[k] = sum[k << 1] + sum[(k << 1) + 1];
return res;
}
void solve(int l, int r, int pl, int pr){
if (pl > pr) return;
if (l == r) {
for (int i = pl; i <= pr; ++i)
p[i].key = l;
return;
}
int mid = l + r >> 1;
int t1 = 0, t2 = 0;
for (int i = pl; i <= pr; ++i)
if (p[i].o == 1) {
if (mid + 1 <= p[i].c) {
Insert(1, 1, N, p[i].l, p[i].r, 1);
que2[++t2] = p[i];
}
else que1[++t1] = p[i];
}
else {
int res = Query(1, 1, N, p[i].l, p[i].r);
if (res >= p[i].c) que2[++t2] = p[i];
else que1[++t1] = p[i], que1[t1].c -= res;
}
for (int i = 1; i <= t1; ++i) p[pl + i - 1] = que1[i];
for (int i = 1; i <= t2; ++i) p[pl + t1 +i - 1] = que2[i];
Clear();
solve(l, mid, pl, pl + t1 - 1);
solve(mid + 1, r, pl + t1, pr);
}
bool cmp(const opt &a, const opt &b){
return a.k < b.k;
}
int main(){
scanf("%d%d", &N, &M);
for (int i = 1; i <= M; ++i)
scanf("%d%d%d%d", &p[i].o, &p[i].l, &p[i].r, &p[i].c), p[i].k = i;
solve(-N, N, 1, M);
sort(p + 1, p + M + 1, cmp);
for (int i = 1; i <= M; ++i)
if (p[i].o == 2)
printf("%d\n", p[i].key);
}
评论 (0)
