# Nemlit 的博客

By a konjac

### 题解 P3527 【[POI2011]MET-Meteors】

posted on 2019-09-01 11:02:42 | under 题解 |

solve(l, mid, L, L + cnt1 - 1), solve(mid + 1, r, L + cnt1, R);

### $Code:$

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define int long long
#define inf 1000000000
re int x = 0, f = 1; re char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
return x * f;
}
#define rep(i, s, t) for(re int i = s; i <= t; ++ i)
#define lb(x) (x)&(-(x))
#define maxn 300005
int n, m, ans[maxn], tr[maxn * 2], T;
struct ques {
int l, r, a, id;
}e[maxn];
struct node {
int ned, id;
}p[maxn], p1[maxn], p2[maxn];
vector<int> q[maxn];
il void add(int x, int v) {
for(re int i = x; i <= 2 * m; i += lb(i)) tr[i] += v;
}
il int query(int x) {
int ans = 0;
for(re int i = x; i; i -= lb(i)) ans += tr[i];
return ans;
}
il int Query(int x) {
int ans = 0;
for(re int i = 0; i < q[p[x].id].size(); ++ i) {
ans += query(q[p[x].id][i]) + query(q[p[x].id][i] + m);
if(ans >= p[x].ned) return ans;
}
return ans;
}
il void solve(int l, int r, int L, int R) {
if(L > R) return;
if(l == r) {
//如果二分到了终点，显然当前操作区间的答案都等于二分的答案
rep(i, L, R) ans[p[i].id] = l;
return;
}
int mid = (l + r) >> 1, cnt1 = 0, cnt2 = 0;
//差分，假设[l, mid]的雨全部下下来
//判断哪些答案大了，那些小了
rep(i, L, R) {
int temp = Query(i);
if(temp >= p[i].ned) p1[++ cnt1] = p[i];
else p[i].ned -= temp, p2[++ cnt2] = p[i];
}
//清空树状数组
//归并排序
rep(i, L, L + cnt1 - 1) p[i] = p1[i - L + 1];
rep(i, L + cnt1, R) p[i] = p2[i - L - cnt1 + 1];
//继续二分
solve(l, mid, L, L + cnt1 - 1), solve(mid + 1, r, L + cnt1, R);
}
signed main() {
}