소 손님 매일 한 문제 3.25 tokitsukaze and Soldier 가중치 선분 수

우리 가 어떻게 답 을 얻 을 수 있 는 지 를 고려 해 보 자. 만약 에 누군가가 그 를 뽑 았 다 면 답 인원 의 집합 은 반드시 s [i] 보다 작 을 것 이다. 답 에 필요 한 사람의 집합 인원 은 num 이 고 집합 안의 모든 s [i] 의 최소 치 는 반드시 num 보다 작 을 것 이다.위 와 같은 가장 중요 한 점 을 명 확 히 한 후에 알 수 있 습 니 다. 우리 가 만약 에 답 한 사람 이 2 명 이 라면 s [i] > = 2 의 전체 인원 이 앞의 2 개 를 취하 면 답 입 니 다. s [i] < 2 는 우리 에 게 제외 되 었 습 니 다.그러면 문제 풀이 절 차 는 목표 인원 을 num 명 으로 설정 하고 s [i] > = num 을 가 진 사람 중 가중치 가 가장 큰 전 num 개 입 니 다.우 리 는 한 사람 을 선택 하 는 것 부터 매 거 할 수 있 습 니 다. 그리고 지금 num 사람 을 선택 하려 면 s [i] 를 num - 1 로 하 는 사람 을 삭제 할 수 있 습 니 다. 선택 한 사람 이 계속 증가 하기 때문에 이 삭 제 된 점 은 뒤에 도 조건 을 만족 시 킬 수 없습니다.다음 문 제 는 한 무리의 사람들 중에서 가중치 가 가장 큰 앞 k 개 를 빨리 알 면 내 가 사용 하 는 것 은 가중치 라인 트 리 이다.가중치 에 따라 분 산 된 후 처음에는 모든 사람 을 집 어 넣 고 위의 분석 에 따라 사람 을 계속 삭제 하면 된다.가중치 선분 트 리 에서 가장 큰 k 인 을 찾 으 면 노드 유지 인원 과 가중치 의 합 계 를 마음대로 쓸 수 있 습 니 다.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define int long long
#define double long double
using namespace std;
#define PI  3.1415926535898
#define eqs 1e-17
const long long max_ = 2e5 + 7;
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
const long long INF = 1e18;
int read() {
	int s = 0, f = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0'&&ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}
inline void write(int x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}
inline int min(int a, int b) {
	return a < b ? a : b;
}
inline int max(int a, int b) {
	return a > b ? a : b;
}
struct kk{
	int num, val;
}tree_[4 * max_],node[max_];
int yuan[max_],ynn,n;
bool cmp(const kk & t1, const kk & t2) {
	if (t1.num == t2.num)return t1.val > t2.val;
	return t1.num > t2.num;
}
void update(int node, int L, int R, int aim,int no) {
	if (L == R) {
		if (no) {
			tree_[node].num++;
			tree_[node].val += yuan[L];
		}
		else {
			tree_[node].num--;
			tree_[node].val -= yuan[L];
		}
		return;
	}
	int mid = (L + R) >> 1, L_tree = node << 1, R_tree = node << 1 | 1;
	if (mid >= aim)update(L_tree, L, mid, aim,no);
	else update(R_tree, mid + 1, R, aim,no);
	tree_[node].num = tree_[L_tree].num + tree_[R_tree].num;
	tree_[node].val = tree_[L_tree].val + tree_[R_tree].val;
}
int ask(int node, int L, int R, int aim_num) {
	if (aim_num <= 0)return 0;
	if (tree_[node].num == aim_num)return tree_[node].val;
	if (L == R && tree_[node].num >= aim_num) {
		return yuan[L] * aim_num;
	}
	int mid = (L + R) >> 1, L_tree = node << 1, R_tree = node << 1 | 1;
	int t1 = 0, t2 = 0;
	if (tree_[R_tree].num >= aim_num)
		t2 = ask(R_tree, mid + 1, R, aim_num);
	else {
		t1 = ask(L_tree, L, mid , aim_num - tree_[R_tree].num);
		t2 = tree_[R_tree].val;
	}
	return t1 + t2;
}
vector<int> ind[max_];
int bianhao[max_];
signed main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		node[i].val = read();
		node[i].num = read();
		yuan[++ynn] = node[i].val;
		ind[node[i].num].push_back(i);
	}
	sort(yuan + 1, yuan + 1 + ynn);
	ynn = unique(yuan + 1, yuan + 1 + ynn) - yuan - 1;
	
	for (int i = 1; i <= n; i++) {
		int wei = lower_bound(yuan + 1, yuan + 1 + ynn, node[i].val) - yuan; 
		bianhao[i] = wei;
		update(1, 1, ynn, wei,1);
	}
	int ans = ask(1, 1, ynn, 1);
	for (int i = 2; i <= n; i++) {
		for (auto to : ind[i - 1]) {
		update(1, 1, ynn, bianhao[to], 0);
		}
		if (tree_[1].num < i)break;
		int v = ask(1, 1, ynn, i);
		ans = max(v, ans);
	}
	cout << ans;
	return 0;
}