[CQOI2015]任务查询系统

首先根据题目要求，我们需要求在第X_i秒时优先级最小的K_i个任务的优先级之和，而这个K_i与之前的答案有关，所以这道题是强行在线的。我也没想过离线怎么做。

离散化优先级，假如我们为每一秒建一棵线段树，存储各个优先级的信息，就可以直接查找了，但是时空都会爆炸。所以问题在于如何建立秒与秒之间的关系，以减少时空开销。

1：假如没有任何任务，那么第 i 秒的情况与第一秒相同。到一般情况，对于任何一段没有新任务的时间段，这些时间所涵盖的信息是相同的。也就是说之后的信息是建立在之前信息之上的，第 i 秒的信息是建立在第 i-1 秒之上的。

2：考虑一个任务（Si，Ei，Pi），这一个任务带来的影响在时间段 [ Si , Ei ] 内是相同的，我们就想到差分了，只需要在第 Si 秒将贡献加上，在第 Ei + 1 秒将贡献移除就可以了。

3：实现采用主席树。

// q.c

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
typedef long long LL;
const int M=100000+10;
struct Node {
	int l,r,lc,rc,size; LL sum;
	Node():l(0),r(0),lc(0),rc(0),size(0),sum(0) {}
};
int f[M];
struct SegmentTree {
	int cnt; Node nd[18*M<<2];
	SegmentTree():cnt(0) {}
	void update(int o) {
		Node &p=nd[o],&lc=nd[nd[o].lc],&rc=nd[nd[o].rc];
		p.size=lc.size+rc.size;
		p.sum=lc.sum+rc.sum;
	}
	void build(int &o,int l,int r) {
		if(!o) o=++cnt; Node &p=nd[o]; p.l=l,p.r=r;
		if(l!=r) {
			int mid=(l+r)>>1;
			build(p.lc,l,mid);
			build(p.rc,mid+1,r);
		}
	}
	void insert(int &o,int po,int x,int k) {
		if(!o) o=++cnt; Node &p=nd[o]; p=nd[po];
		if(p.l==p.r) p.size+=k,p.sum+=(LL)k*f[x];
		else {
			int mid=(p.l+p.r)>>1;
			if(x<=mid) p.lc=0,insert(p.lc,nd[po].lc,x,k);
			else p.rc=0,insert(p.rc,nd[po].rc,x,k);
			update(o);
		}
	}
	LL query(int o,int k) {
		Node p=nd[o]; 
		if(p.l==p.r) return p.sum/p.size*k;
		else if(k<=nd[p.lc].size) return query(p.lc,k);
		else return nd[p.lc].sum+query(p.rc,k-nd[p.lc].size);
	}
}t;
struct Ques { int id,tag; }; vector<Ques> qs[M];
struct Data {
	int x,y;
	bool operator < (const Data &A) const {
		if(x!=A.x) return x<A.x;
		return y<A.y;
	}
}w[M];
int m,n,v[M],root[M],cnt;
int main() {
	freopen("cqoi15_query.in","r",stdin);
	freopen("cqoi15_query.out","w",stdout);
	scanf("%d%d",&m,&n); 
	int a,b,c;
	for(int i=1;i<=m;i++) {
		scanf("%d%d%d",&a,&b,&c);
		w[i].x=c,w[i].y=i;
		qs[a].push_back((Ques){i,1});
		qs[b+1].push_back((Ques){i,-1});
	}
	sort(w+1,w+m+1);
	for(int i=1;i<=m;i++) {
		if(w[i].x!=w[i-1].x) v[w[i].y]=++cnt,f[cnt]=w[i].x;
		else v[w[i].y]=cnt;
	}
	t.build(root[0],1,cnt);
	for(int i=1;i<=n;i++) {
		int sz=qs[i].size();
		root[i]=root[i-1];
		int x=0;
		for(int j=0;j<sz;j++) {
			t.insert(x,root[i],v[qs[i][j].id],qs[i][j].tag);
			root[i]=x; x=0;
		}
	}
	int x,k; LL pre=1;
	for(int i=1;i<=n;i++) {
		scanf("%d%d%d%d",&x,&a,&b,&c);
		k=(int)((a*pre+b)%c)+1; 
		if(k>=t.nd[root[x]].size) pre=t.nd[root[x]].sum;
		else pre=t.query(root[x],k);
		printf("%lld\n",pre);
	}
	return 0;
}

需要注意的是对于同一秒有多个任务开始或结束的情况，这其实牵扯到自己对主席树的理解以及写法，我也不会表达，我采用了一个迭代实现。