【洛谷 P3168】 [CQOI2015]任务查询系统（主席树）

题目链接

被自己的sb错误调到自闭。。

主席树的进阶应用。

把\(P_i\)离散化一下，得到每个\(P_i\)的排名，然后建一棵维护\(m\)个位置的主席树，每个结点记录区间总和和正在进行的任务数。

差分一下，主席树维护前缀和，每个时刻一个\(root\)。

然后就是线段树里查前\(k\)小了。

#include <cstdio>

#include <algorithm>

using namespace std;

const int MAXN = 4000010;

struct PT{

	int lc, rc, cnt;

	long long val;

}t[MAXN << 2];

int rk[MAXN];

struct lsh{

	int val, id;

	int operator < (const lsh A) const{

		return val < A.val;

	}

}p[MAXN];

int n, m;

struct Edge{

	int next, to, dis;

}e[MAXN];

int head[MAXN], num;

long long pre = 1;

inline void Add(int from, int to, int dis){

	e[++num].to = to; e[num].next = head[from]; e[num].dis = dis; head[from] = num;

}

inline int read(){

	int s = 0, w = 1;

	char ch = getchar();

	while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar(); }

	while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); }

	return s * w;

}

int a[MAXN], b[MAXN], c[MAXN], root[MAXN], cnt, r, A, B, C, X, K;

inline void pushup(int x){

	t[x].val = t[t[x].lc].val + t[t[x].rc].val;

	t[x].cnt = t[t[x].lc].cnt + t[t[x].rc].cnt;

}

int build(int l, int r){

	if(l == r) return ++cnt;

	int id = ++cnt, mid = (l + r) >> 1;

	t[id].lc = build(l, mid);

	t[id].rc = build(mid + 1, r);

	return id;

}

int update(int q, int l, int r, int x, int y){

	if(l == r){ t[++cnt].val = t[q].val + y; t[cnt].cnt = t[q].cnt + (y > 0 ? 1 : -1); return cnt; }

	int id = ++cnt, mid = (l + r) >> 1;

	t[id] = t[q];

	if(x <= mid) t[id].lc = update(t[q].lc, l, mid, x, y);

	else t[id].rc = update(t[q].rc, mid + 1, r, x, y);

	pushup(id);

	return id;

}

long long query(int q, int l, int r, int x){

	if(l == r) return t[q].val;

	int mid = (l + r) >> 1;

	if(t[t[q].lc].cnt >= x) return query(t[q].lc, l, mid, x);

	else return t[t[q].lc].val + query(t[q].rc, mid + 1, r, x - t[t[q].lc].cnt);

}

int main(){

	m = read(); n = read();

	for(int i = 1; i <= m; ++i){

		a[i] = read(); r = max(r, b[i] = read());

		p[i].id = i; p[i].val = c[i] = read();;

	}

	sort(p + 1, p + m + 1);

	for(int i = 1; i <= m; ++i)

	   rk[p[i].id] = i;

	for(int i = 1; i <= m; ++i){

		Add(  a[i]  , rk[i], c[i]);

		Add(b[i] + 1, rk[i], -c[i]);

	}

	root[0] = build(1, m);

	for(int i = 1; i <= n; ++i){

		int tmp = root[i - 1];

		for(int j = head[i]; j; j = e[j].next)

		   tmp = update(tmp, 1, m, e[j].to, e[j].dis);

		root[i] = tmp;

	}

	for(int i = 1; i <= n; ++i){

		X = read(); A = read(); B = read(); C = read();

		K = ((long long)A * pre + B) % C + 1;

    	printf("%lld\n", pre = query(root[X], 1, m, K));

	}

	return 0;

}

巴特西

【洛谷 P3168】 [CQOI2015]任务查询系统（主席树）

最新文章

热门文章