就是裸的主席树,差分之后排序插入主席树就行了.

注意主席树查询的时候叶子节点要特判,因为本身是有size的

还有要开longlong

CODE

#include <cctype>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long LL;

char cb[1<<15],*cs=cb,*ct=cb;

#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++)

template<class T>inline void read(T &res) {

    char ch; for(;!isdigit(ch=getc()););

    for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0');

}

const int MAXN = 100005;

const int MAXM = MAXN*60;

struct task { int x, val; }a[MAXN<<1];

inline bool cmp(const task &i, const task &j) { return i.x < j.x; }

int ch[MAXM][2], sz[MAXM], tot, V, rt[MAXN];

int n, m, cur; LL sum[MAXM];

inline int Sign(int x) { return x > 0 ? 1 : -1; }

void modify(int &i, int p, int l, int r, int x, int val) {

	i = ++tot;

	sz[i] = sz[p] + val;

	sum[i] = sum[p] + x*val;

	if(l == r) return;

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

	if(x <= mid) ch[i][1] = ch[p][1], modify(ch[i][0], ch[p][0], l, mid, x, val);

	else ch[i][0] = ch[p][0], modify(ch[i][1], ch[p][1], mid+1, r, x, val);

}

LL query(int i, int l, int r, int x) {

	if(l == r) return 1ll * l * x; //主席树查询叶节点要特判,因为自己有sz

	if(sz[i] == x) return sum[i];

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

	if(sz[ch[i][0]] >= x) return query(ch[i][0], l, mid, x);

	else return sum[ch[i][0]] + query(ch[i][1], mid+1, r, x-sz[ch[i][0]]);

}

int main () {

	read(m), read(n);

	for(int i = 1, s, e, p; i <= m; ++i) {

		read(s), read(e), read(p);

		a[++cur] = (task){ s,  p };

		a[++cur] = (task){ e+1, -p };

		V = max(V, p);

	}

	sort(a + 1, a + cur + 1, cmp);

	int now = 0;

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

		rt[i] = rt[i-1];

		while(now < cur && a[now+1].x == i) {

			++now;

			modify(rt[i], rt[i], 1, V, abs(a[now].val), Sign(a[now].val));

		}

	}

	LL lastans = 1, x, A, B, C, k;

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

		read(x), read(A), read(B), read(C);

		k = (lastans * A + B) % C + 1;

		printf("%lld\n", lastans=query(rt[x], 1, V, min(int(k), sz[rt[x]])));

	}

}

巴特西

BZOJ 3932: [CQOI2015]任务查询系统 (主席树板题)

CODE

最新文章

热门文章